Sokoban: Difference between revisions

* + is the player on a goal

* * is a box on a goal

 

Sokoban solutions are usually stored in the LURD format, where lowercase l, u, r and d represent a move in that ('''l'''eft, '''u'''p, '''r'''ight, '''d'''own) direction and capital LURD represents a push.

 

For more information, see [http://www.sokobano.de/wiki/index.php?title=Main_Page the Sokoban wiki].

 

=={{header|C}}==

Long, long, long C99 code (plus GNU C nested functions). Doesn't output the movement keys, instead it animates the sequence for you. Solution is move optimized. For an even longer solution, see [[Sokoban/C]].

#include <stdlib.h>

#include <string.h>

 

return 0;

 

=={{header|C++}}==

 

This performs a breadth-first search by moves, so the results should be a move-optimal solution.

#include <string>

#include <vector>

int w = 0;

vector<string> data;

data.push_back((*iter)[1]);

w = max(w, (*iter)[1].length());

}

 

vector<char> sTemp, dTemp;

sTemp.push_back(' ');

dTemp.push_back(' ');

char s = ' ', d = ' ', c = data[v][u];

 

s = '.';

 

d = '@';

px = u;

py = v;

d = '*';

 

dirs[3] = make_tuple(-1, 0, 'l', 'L');

 

vector<vector<char>> temp, cur = get<0>(open.front());

string cSol = get<1>(open.front());

open.pop();

 

temp = cur;

int dx = get<0>(dirs[i]);

int dy = get<1>(dirs[i]);

 

if(isSolved(temp))

return cSol + get<3>(dirs[i]);

visited.insert(temp);

}

if(isSolved(temp))

return cSol + get<2>(dirs[i]);

cout << level << endl << endl << b.solve() << endl;

return 0;

 

Output:

 

ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>

===Unordered Set-based Version===

{{works with|C++11}}

{{works with|GCC 4.6}}

Alternative version, about twice faster (about 2.1 seconds runtime), same output.

#include <string>

#include <vector>

cout << board.solve() << endl;

return 0;

 

=={{header|D}}==

{{trans|C++}}

This version uses the queue defined in the Queue/Usage task.

import queue_usage2; // No queue in Phobos 2.064.

 

private immutable int playerx, playery;

 

in {

foreach (const row; board) {

}

} body {

ncols = board[0].length;

 

private bool move(in int x, in int y, in int dx,

in int dy, ref CTable data)

return false;

 

data2[y * ncols + x] = El.floor;

data2[(y + dy) * ncols + x + dx] = El.player;

private bool push(in int x, in int y, in int dx,

in int dy, ref CTable data)

return false;

 

data2[y * ncols + x] = El.floor;

data2[(y + dy) * ncols + x + dx] = El.player;

data = data2.assumeUnique; // Not enforced.

return true;

}

 

foreach (immutable i, immutable d; data)

if ((sData[i] == El.goal) != (d == El.boxOnGoal))

}

 

bool[immutable CTable] visitedSet = [dData: true];

 

open.push(Four(dData, "", playerx, playery));

 

 

//immutable (cur, cSol, x, y) = open.pop;

immutable item = open.pop;

if (isSolved(temp))

return cSol ~ di[3];

visitedSet[temp] = true;

}

if (isSolved(temp))

return cSol ~ di[2];

visitedSet[temp] = true;

}

void main() {

import std.stdio, core.memory;

 

immutable level =

#######";

 

writeln(level, "\n\n", b.solve);

{{out}}

<pre>#######

 

ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>

 

===Faster Version===

{{trans|C}}

This code is not idiomatic D, it retains most of the style of the C version.

import core.stdc.stdlib: malloc, calloc, realloc, free, alloca, exit;

 

CellIndex[0] c_;

 

return c_.ptr[i];

}

 

c_.ptr[i] = v;

}

 

return c_.ptr[i .. j];

}

 

 

return cast(State*)(cast(ubyte*)s + stateSize);

}

 

 

p.next = blockHead;

blockHead = p;

 

/// Mark up positions where a box definitely should not be.

immutable y = c / w;

immutable x = c % w;

 

 

auto ptr = cast(T*)calloc(n, T.sizeof);

if (ptr == null)

 

/// K&R hash function.

if (!s.h) {

Thash ha = 0;

 

 

int oldSize = hashSize;

 

 

 

s.hash(nBoxes);

auto f = buckets[s.h & (hashSize - 1)];

 

 

if (s.lookup) {

s.unNewState;

 

 

foreach (immutable i; 1 .. nBoxes + 1)

if (!goals[s.get(i)])

 

 

immutable int y = s.get(0) / w;

immutable int x = s.get(0) % w;

 

 

if (!s || !s.addToTable)

return false;

 

 

return s.moveMe( 1, 0).queueMove ||

s.moveMe(-1, 0).queueMove ||

 

 

static immutable glyphs1 = " #@$", glyphs2 = ".#@$";

 

 

 

if (s.prev)

s.prev.showMoves;

}

 

 

enum uint problem = 0;

 

static if (problem == 0) {

"#######"~

"# #"~

"#.$$ #"~

"#.# @#"~

 

} else static if (problem == 1) {

"#############"~

"# # #"~

"# $$$$$$$ @#"~

"#....... #"

 

} else static if (problem == 2) {

" ##### "~

" # # "~

"##### ### #@## .#"~

" # #########"~

} else {

asset(0, "Not present problem.");

 

return 0;

 

=={{header|Go}}==

{{trans|C++}}

Well, it started as a C++ translation, but turned out different. It's still the breadth-first set-based algorithm, but I dropped the sdata/ddata optimization and just maintained a single string as the board representation. Also dropped the code to handle non-rectangular boards, and probably some other stuff too.

 

import (

}

return string(buffer)

{{out}}

<pre>

ulULLulDDurrrddlULrruLLrrUruLLLulD

</pre>

 

=={{header|OCaml}}==

{{trans|Python}}

This uses a breadth-first move search, so will find a move-optimal solution.

type move_t = Move of dir | Push of dir

 

 

let store = Hashtbl.create 251

let marked t = Hashtbl.mem store t

 

"#.# @#";

"#######"] in

Output:

<pre>luULLulDDurrrddlULrruLLrrUruLLLulD</pre>

=={{header|Perl}}==

This performs simultaneous breadth first searches, starting from the initial state

would still be a valid solution. I could fix it, but at the cost of speed and memory.

 

use strict;

use warnings qw(FATAL all);

}

__END__

{{out}}

<pre>Solution found!

Although my code doesn't print out the actual final board, it would be easy enough

to compute from the move list.

#######

# #

#.# @#

#######

 

 

 

 

{{out}}

 

=={{header|PicoLisp}}==

This searches for a solution, without trying for the push-optimal one. The player moves between the pushes, however, are minimized.

 

# Display board

(pushes) )

(display) # Display solution

Test:

(quote

"#######"

"#######" ) )

(prinl)

Output:

<pre> 8 # # # # # # #

{{works with|Psyco}}

{{works with|Python 2.6}}

from collections import deque

import psyco

psyco.full()

init(level)

Output:

<pre>#######

This was originally inspired by PicoLisp's solution. Modified to use a priority queue as mentioned on the Sokoban wiki for the main breadth first search on pushes but just a plain queue for the move bfs. This uses personal libraries. Vector2 isn't strictly needed but the math/array library is not currently optimized for untyped Racket. push! is comparable to lisp's, awhen is anaphoric when, ret uses the bound value as the result of its expression, and tstruct is short for struct with the #:transparent option.

 

#lang racket

(require data/heap

(pushes s clear))

(bfs)])))

 

{{out}}

"uuulDLLrrrddllUdrruulLrrdLuuulldlDDuuurrrddlLrrddlULrruLdlUUdrruulLulD"

</pre>

 

=={{header|Tcl}}==

This code does a breadth-first search so it finds a solution with a minimum number of moves.

{{trans|OCaml}}<!-- the big difference is that this is all in one procedure for speed as it reduces the amount of packing/unpacking of tuples/lists, and the queue isn't shortened as that's significantly slower for these sorts of board sizes -->

 

proc solveSokoban b {

}

error "no solution"

Demonstration code:

"#######"

"# #"

"#######"

}

Output: <pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>

Runtime with stock Tcl 8.5 installation: ≅2.2 seconds<!-- on what is now a fairly old machine -->