Sokoban
You are encouraged to solve this task according to the task description, using any language you may know.
Demonstrate how to find a solution to a given Sokoban level. For the purpose of this task (formally, a PSPACE-complete problem) any method may be used. However a move-optimal or push-optimal (or any other -optimal) solutions is preferred.
Sokoban levels are usually stored as a character array where
- space is an empty square
- # is a wall
- @ is the player
- $ is a box
- . is a goal
- + 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 (left, up, right, down) direction and capital LURD represents a push.
Please state if you use some other format for either the input or output, and why.
For more information, see the Sokoban wiki.
C
Long, long C code. Doesn't output the movement keys, instead it animates the sequence for you. Solution is move optimized. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <unistd.h>
char *glyph = " $@#"; enum { space = 0, box = 1, player = 2, wall = 3};
int (*boxes)[2] = 0, n_boxes = 0, w, h;
typedef struct rec_t rec_t, *rec; struct rec_t { char *board; rec next, parent, p[16]; } rec_root = { 0, 0, 0, {0} }, *current_level, *next_level;
rec make_rec(char *ss) { int c, len = w * h; char *s = ss; rec root = &rec_root; int new = 0; while (len) { c = *s++ * 4; if (--len) c += *s++, --len; if (!root->p[c]) { root->p[c] = calloc(1, sizeof(rec_t)); new = 1; } root = root->p[c]; } if (!new) return 0; root->board = ss; return root; }
char* init_board(char *in) { int i, j, k; char *out = calloc(1, w * h); for (i = 1; i < h + 1; i++) { for (j = 1; j < w + 1; j++) { k = (i - 1) * w + j - 1; switch(in[i * (w + 2) + j]) { case '#': out[k] = wall; continue; case '@': out[k] = player; continue; case '$': out[k] = box; continue; case '.': boxes = realloc(boxes, sizeof(int[2]) * ++n_boxes); boxes[n_boxes-1][0] = j - 1; boxes[n_boxes-1][1] = i - 1;
continue;
case ' ': out[k] = space; continue; } }}
return out; }
void show_board(char *map) { int i, j, k; printf("\033[H"); for (i = w + 2; i >= 0; i--) putchar(i ? '#' : '\n'); for (i = 0; i < h; i++) { putchar('#'); for (j = 0; j < w; j++, map++) { if (*map != space) { putchar(glyph[(int)*map]); continue; } for (k = 0; k < n_boxes; k++) { if (i != boxes[k][1] || j != boxes[k][0]) continue; putchar('.'); break; } if (k == n_boxes) putchar(' '); } puts("#"); } for (i = w + 2; i >= 0; i--) putchar(i ? '#' : '\n'); }
int dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; char* apply_move(char *map, int d) { int i, x, y, x1, y1, x2 = -1, y2; char c, *out; for (i = w * h - 1; map[i] != player; i--); x = i % w; y = i / w;
x1 = x + dirs[d][0]; if (x1 < 0 || x1 >= w) return 0;
y1 = y + dirs[d][1]; if (y1 < 0 || y1 >= h) return 0;
c = map[y1 * w + x1]; if (c == wall) return 0; if (c == box) { x2 = x1 + dirs[d][0]; if (x2 < 0 || x2 >= w) return 0;
y2 = y1 + dirs[d][1]; if (y2 < 0 || y2 >= h) return 0;
if (map[y2 * w + x2] != space) return 0; }
out = malloc(w * h); memcpy(out, map, w * h);
if (x2 >= 0) out[y2 * w + x2] = box; out[y1 * w + x1] = player; out[y * w + x] = space;
return out; }
int solved(rec r) { int i; char *s = r->board; for (i = 0; i < n_boxes; i++) if (s[boxes[i][1] * w + boxes[i][0]] != box) return 0; return 1; }
rec move() { char *next; int d; rec nr; while (current_level) { for (d = 0; d < 4; d++) { next = apply_move(current_level->board, d); if (!next || !(nr = make_rec(next))) continue;
nr->parent = current_level; if (solved(nr)) return nr; nr->next = next_level; next_level = nr; } current_level = current_level->next; } return 0; }
rec solve() { rec r; while (current_level) { putchar('.'); fflush(stdout); if ((r = move())) return r; current_level = next_level; next_level = 0; } return 0; }
void show_moves(rec r) { if (!r) { puts("No solution?"); return; } printf("\033[H\033[J"); if (r->parent) show_moves(r->parent); show_board(r->board); usleep(200000); }
int main() { w = 5, h = 6; rec_root.board = init_board( "#######" "# #" "# #" "#. # #" "#. $$ #" "#.$$ #" "#.# @#" "#######" ); current_level = &rec_root; show_moves(solve()); return 0; }</lang>
C99
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <stdbool.h>
- include <assert.h>
const char *glyphs = " $@#"; enum { SPACE, BOX, PLAYER, WALL };
typedef struct Rec Rec;
struct Rec {
char *board; Rec *next; Rec *parent; Rec *p[16];
};
// global variables int w, h, n_boxes; Rec rec_root; Rec *current_level; Rec *next_level; int (*boxes)[2]; // pointer to int[2]
Rec *make_rec(char *ss) {
int len = w * h; char *s = ss; Rec *root = &rec_root; bool is_new = false;
while (len) {
int c = *s * 4;
s++;
len--;
if (len) {
c += *s;
s++;
len--;
}
if (!root->p[c]) {
root->p[c] = calloc(1, sizeof(Rec));
assert(root->p[c]);
is_new = 1;
}
root = root->p[c];
}
if (!is_new)
return NULL;
root->board = ss;
return root;
}
char *init_board(const char *inb) {
char *result = calloc(1, w * h); assert(result);
for (int i = 1; i < h + 1; i++) {
for (int j = 1; j < w + 1; j++) {
const int k = (i - 1) * w + j - 1;
switch (inb[i * (w + 2) + j]) {
case '#':
result[k] = WALL;
continue;
case '@':
result[k] = PLAYER;
continue;
case '$':
result[k] = BOX;
continue;
case '.':
n_boxes++;
boxes = realloc(boxes, sizeof(int[2]) * n_boxes);
assert(boxes);
boxes[n_boxes - 1][0] = j - 1;
boxes[n_boxes - 1][1] = i - 1;
continue;
case ' ':
result[k] = SPACE;
continue;
default: {}
}
}
}
return result;
}
void show_board(char *map) {
putchar('\n');
for (int i = w + 2; i >= 0; i--)
putchar(i ? '#' : '\n');
for (int i = 0; i < h; i++) {
putchar('#');
for (int j = 0; j < w; j++, map++) {
if (*map != SPACE) {
putchar(glyphs[(int)*map]);
continue;
}
int k;
for (k = 0; k < n_boxes; k++) {
if (i != boxes[k][1] || j != boxes[k][0])
continue;
putchar('.');
break;
}
if (k == n_boxes)
putchar(' ');
}
puts("#");
}
for (int i = w + 2; i >= 0; i--)
putchar(i ? '#' : '\n');
}
const int dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
char *apply_move(const char *map, const int d) {
int i;
for (i = w * h - 1; map[i] != PLAYER; i--) {}
int x = i % w;
int y = i / w;
int x1 = x + dirs[d][0];
if (x1 < 0 || x1 >= w)
return NULL;
int y1 = y + dirs[d][1];
if (y1 < 0 || y1 >= h)
return NULL;
char c = map[y1 * w + x1];
if (c == WALL)
return NULL;
int x2 = -1, y2 = 0;
if (c == BOX) {
x2 = x1 + dirs[d][0];
if (x2 < 0 || x2 >= w)
return NULL;
y2 = y1 + dirs[d][1];
if (y2 < 0 || y2 >= h)
return NULL;
if (map[y2 * w + x2] != SPACE)
return NULL;
}
char *result = malloc(w * h); assert(result); memcpy(result, map, w * h);
if (x2 >= 0)
result[y2 * w + x2] = BOX;
result[y1 * w + x1] = PLAYER;
result[y * w + x] = SPACE;
return result;
}
bool solved(const Rec *r) {
const char *s = r->board;
for (int i = 0; i < n_boxes; i++)
if (s[boxes[i][1] * w + boxes[i][0]] != BOX)
return false;
return true;
}
Rec *move() {
while (current_level) {
for (int d = 0; d < 4; d++) {
char *next = apply_move(current_level->board, d);
if (!next)
continue;
Rec *nr = make_rec(next);
if (!nr)
continue;
nr->parent = current_level;
if (solved(nr))
return nr;
nr->next = next_level;
next_level = nr;
}
current_level = current_level->next; }
return NULL;
}
Rec *solve() {
while (current_level) {
putchar('.');
fflush(stdout);
Rec *r = move();
if (r) {
putchar('\n');
return r;
}
current_level = next_level;
next_level = NULL;
}
putchar('\n');
return NULL;
}
void show_moves(Rec *r) {
if (!r) {
puts("No solution?");
return;
}
if (r->parent)
show_moves(r->parent);
show_board(r->board);
}
int main() {
w = 5, h = 6;
rec_root.board = init_board(
"#######"
"# #"
"# #"
"#. # #"
"#. $$ #"
"#.$$ #"
"#.# @#"
"#######"
);
current_level = &rec_root; show_moves(solve());
return 0;
}</lang>
C++
This heavily abuses the STL, including some of the newer features like regex and tuples.
This performs a breadth-first search by moves, so the results should be a move-optimal solution. <lang cpp>#include <iostream>
- include <string>
- include <vector>
- include <queue>
- include <regex>
- include <tuple>
- include <set>
- include <array>
using namespace std;
class Board { public:
vector<vector<char>> sData, dData; int px, py;
Board(string b)
{
regex pattern("([^\\n]+)\\n?");
sregex_iterator end, iter(b.begin(), b.end(), pattern);
int w = 0;
vector<string> data;
for(; iter != end; ++iter)
{
data.push_back((*iter)[1]);
w = max(w, (*iter)[1].length());
}
for(int v = 0; v < data.size(); ++v)
{
vector<char> sTemp, dTemp;
for(int u = 0; u < w; ++u)
{
if(u > data[v].size())
{
sTemp.push_back(' ');
dTemp.push_back(' ');
}
else
{
char s = ' ', d = ' ', c = data[v][u];
if(c == '#')
s = '#';
else if(c == '.' || c == '*' || c == '+')
s = '.';
if(c == '@' || c == '+')
{
d = '@';
px = u;
py = v;
}
else if(c == '$' || c == '*')
d = '*';
sTemp.push_back(s);
dTemp.push_back(d);
}
}
sData.push_back(sTemp);
dData.push_back(dTemp);
}
}
bool move(int x, int y, int dx, int dy, vector<vector<char>> &data)
{
if(sData[y+dy][x+dx] == '#' || data[y+dy][x+dx] != ' ')
return false;
data[y][x] = ' '; data[y+dy][x+dx] = '@';
return true; }
bool push(int x, int y, int dx, int dy, vector<vector<char>> &data)
{
if(sData[y+2*dy][x+2*dx] == '#' || data[y+2*dy][x+2*dx] != ' ')
return false;
data[y][x] = ' '; data[y+dy][x+dx] = '@'; data[y+2*dy][x+2*dx] = '*';
return true; }
bool isSolved(const vector<vector<char>> &data)
{
for(int v = 0; v < data.size(); ++v)
for(int u = 0; u < data[v].size(); ++u)
if((sData[v][u] == '.') ^ (data[v][u] == '*'))
return false;
return true;
}
string solve()
{
set<vector<vector<char>>> visited;
queue<tuple<vector<vector<char>>, string, int, int>> open;
open.push(make_tuple(dData, "", px, py)); visited.insert(dData);
array<tuple<int, int, char, char>, 4> dirs; dirs[0] = make_tuple(0, -1, 'u', 'U'); dirs[1] = make_tuple(1, 0, 'r', 'R'); dirs[2] = make_tuple(0, 1, 'd', 'D'); dirs[3] = make_tuple(-1, 0, 'l', 'L');
while(open.size() > 0)
{
vector<vector<char>> temp, cur = get<0>(open.front());
string cSol = get<1>(open.front());
int x = get<2>(open.front());
int y = get<3>(open.front());
open.pop();
for(int i = 0; i < 4; ++i)
{
temp = cur;
int dx = get<0>(dirs[i]);
int dy = get<1>(dirs[i]);
if(temp[y+dy][x+dx] == '*')
{
if(push(x, y, dx, dy, temp) && (visited.find(temp) == visited.end()))
{
if(isSolved(temp))
return cSol + get<3>(dirs[i]);
open.push(make_tuple(temp, cSol + get<3>(dirs[i]), x+dx, y+dy));
visited.insert(temp);
}
}
else if(move(x, y, dx, dy, temp) && (visited.find(temp) == visited.end()))
{
if(isSolved(temp))
return cSol + get<2>(dirs[i]);
open.push(make_tuple(temp, cSol + get<2>(dirs[i]), x+dx, y+dy));
visited.insert(temp);
}
}
}
return "No solution"; }
};
int main() {
string level = "#######\n" "# #\n" "# #\n" "#. # #\n" "#. $$ #\n" "#.$$ #\n" "#.# @#\n" "#######";
Board b(level);
cout << level << endl << endl << b.solve() << endl; return 0;
}</lang>
Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Alternative version, about twice faster (about 2.1 seconds runtime), same output. <lang cpp>#include <iostream>
- include <string>
- include <vector>
- include <queue>
- include <tuple>
- include <array>
- include <map>
- include <boost/algorithm/string.hpp>
- include <boost/unordered_set.hpp>
using namespace std;
typedef vector<char> TableRow; typedef vector<TableRow> Table;
struct Board {
Table sData, dData; int px, py;
Board(string b) {
vector<string> data;
boost::split(data, b, boost::is_any_of("\n"));
size_t width = 0;
for (auto &row: data)
width = max(width, row.size());
map<char,char> maps = {{' ',' '}, {'.','.'}, {'@',' '},
{'#','#'}, {'$',' '}},
mapd = {{' ',' '}, {'.',' '}, {'@','@'},
{'#',' '}, {'$','*'}};
for (size_t r = 0; r < data.size(); r++) {
TableRow sTemp, dTemp;
for (size_t c = 0; c < width; c++) {
char ch = c < data[r].size() ? data[r][c] : ' ';
sTemp.push_back(maps[ch]);
dTemp.push_back(mapd[ch]);
if (ch == '@') {
px = c;
py = r;
}
}
sData.push_back(sTemp);
dData.push_back(dTemp);
}
}
bool move(int x, int y, int dx, int dy, Table &data) {
if (sData[y+dy][x+dx] == '#' || data[y+dy][x+dx] != ' ')
return false;
data[y][x] = ' '; data[y+dy][x+dx] = '@'; return true; }
bool push(int x, int y, int dx, int dy, Table &data) {
if (sData[y+2*dy][x+2*dx] == '#' || data[y+2*dy][x+2*dx] != ' ')
return false;
data[y][x] = ' '; data[y+dy][x+dx] = '@'; data[y+2*dy][x+2*dx] = '*'; return true; }
bool isSolved(const Table &data) {
for (size_t r = 0; r < data.size(); r++)
for (size_t c = 0; c < data[r].size(); c++)
if ((sData[r][c] == '.') != (data[r][c] == '*'))
return false;
return true;
}
string solve() {
boost::unordered_set<Table, boost::hash
> visited; visited.insert(dData); queue<tuple<Table, string, int, int>> open; open.push(make_tuple(dData, "", px, py)); vector<tuple<int, int, char, char>> dirs = { make_tuple( 0, -1, 'u', 'U'), make_tuple( 1, 0, 'r', 'R'), make_tuple( 0, 1, 'd', 'D'), make_tuple(-1, 0, 'l', 'L') }; while (open.size() > 0) { Table temp, cur = get<0>(open.front()); string cSol = get<1>(open.front()); int x = get<2>(open.front()); int y = get<3>(open.front()); open.pop(); for (int i = 0; i < 4; ++i) { temp = cur; int dx = get<0>(dirs[i]); int dy = get<1>(dirs[i]); if (temp[y+dy][x+dx] == '*') { if (push(x, y, dx, dy, temp) && visited.find(temp) == visited.end()) { if (isSolved(temp)) return cSol + get<3>(dirs[i]); open.push(make_tuple(temp, cSol + get<3>(dirs[i]), x+dx, y+dy)); visited.insert(temp); } } else if (move(x, y, dx, dy, temp) && visited.find(temp) == visited.end()) { if (isSolved(temp)) return cSol + get<2>(dirs[i]); open.push(make_tuple(temp, cSol + get<2>(dirs[i]), x+dx, y+dy)); visited.insert(temp); } } } return "No solution"; } }; int main() { string level = "#######\n" "# #\n" "# #\n" "#. # #\n" "#. $$ #\n" "#.$$ #\n" "#.# @#\n" "#######"; cout << level << endl << endl; Board board(level); cout << board.solve() << endl; return 0; }</lang>D
<lang d>import std.string, std.typecons, std.exception, std.algorithm;
// No queue in dmd 2.058 Phobos. struct GrowableCircularQueue(T) {
private size_t length, head, tail; private T[] A = [T.init];
void push(immutable T item) pure nothrow {
if (length >= A.length) { // double the queue
const old = A;
A = new T[A.length * 2];
A[0 .. (old.length - head)] = old[head .. $];
if (head)
A[(old.length-head) .. old.length] = old[0 .. head];
head = 0;
tail = length;
}
A[tail] = item;
tail = (tail + 1) % A.length;
length++;
}
T pop() pure {
if (length == 0)
throw new Exception("GrowableCircularQueue is empty.");
immutable oldHead = head;
head = (head + 1) % A.length;
length--;
return A[oldHead];
}
}
immutable struct Board {
enum El : char { floor=' ', wall='#', goal='.',
box='$', player='@', boxOnGoal='*' }
alias string CTable;
immutable size_t ncols;
immutable CTable sData, dData;
immutable int playerx, playery;
this(in string[] board) pure nothrow
in {
foreach (row; board) {
assert(row.length == board[0].length,
"Unequal board rows.");
foreach (c; row)
assert(inPattern(c, " #.$@*"), "Not valid input");
}
} body {
immutable sMap=[' ':' ', '.':'.', '@':' ', '#':'#', '$':' '];
immutable dMap=[' ':' ', '.':' ', '@':'@', '#':' ', '$':'*'];
ncols = board[0].length;
foreach (r, row; board)
foreach (c, ch; row) {
sData ~= sMap[ch];
dData ~= dMap[ch];
if (ch == El.player) {
playerx = c;
playery = r;
}
}
}
bool move(in int x, in int y, in int dx,
in int dy, ref CTable data) const pure /*nothrow*/ {
if (sData[(y+dy) * ncols + x+dx] == El.wall ||
data[(y+dy) * ncols + x+dx] != El.floor)
return false;
auto data2 = data.dup; // not nothrow
data2[y * ncols + x] = El.floor;
data2[(y+dy) * ncols + x+dx] = El.player;
data = assumeUnique(data2); // not enforced
return true;
}
bool push(in int x, in int y, in int dx,
in int dy, ref CTable data) const pure /*nothrow*/ {
if (sData[(y+2*dy) * ncols + x+2*dx] == El.wall ||
data[(y+2*dy) * ncols + x+2*dx] != El.floor)
return false;
auto data2 = data.dup; // not nothrow
data2[y * ncols + x] = El.floor;
data2[(y+dy) * ncols + x+dx] = El.player;
data2[(y+2*dy) * ncols + x+2*dx] = El.boxOnGoal;
data = assumeUnique(data2); // not enforced
return true;
}
bool isSolved(in CTable data) const pure nothrow {
foreach (i, d; data)
if ((sData[i] == El.goal) != (d == El.boxOnGoal))
return false;
return true;
}
string solve() pure {
bool[immutable CTable] visitedSet = [dData: true];
alias Tuple!(CTable, string, int, int) Four;
GrowableCircularQueue!Four open;
open.push(Four(dData, "", playerx, playery));
immutable dirs = [tuple( 0, -1, 'u', 'U'),
tuple( 1, 0, 'r', 'R'),
tuple( 0, 1, 'd', 'D'),
tuple(-1, 0, 'l', 'L')];
while (open.length) {
//immutable (cur, cSol, x, y) = open.pop();
immutable item = open.pop();
immutable CTable cur = item[0];
immutable string cSol = item[1];
immutable int x = item[2];
immutable int y = item[3];
foreach (di; dirs) {
CTable temp = cur;
//immutable (dx, dy) = di[0 .. 2];
immutable int dx = di[0];
immutable int dy = di[1];
if (temp[(y+dy) * ncols + x+dx] == El.boxOnGoal) {
if (push(x, y, dx, dy, temp) && temp !in visitedSet) {
if (isSolved(temp))
return cSol ~ di[3];
open.push(Four(temp, cSol ~ di[3], x+dx, y+dy));
visitedSet[temp] = true;
}
} else if (move(x, y, dx, dy, temp) &&
temp !in visitedSet) {
if (isSolved(temp))
return cSol ~ di[2];
open.push(Four(temp, cSol ~ di[2], x+dx, y+dy));
visitedSet[temp] = true;
}
}
}
return "No solution"; }
}
void main() {
import std.stdio, core.memory; GC.disable(); // Uses about twice the memory immutable level =
"#######
- #
- #
- . # #
- . $$ #
- .$$ #
- .# @#
- ";
immutable b = Board(level.splitLines()); writeln(level, "\n\n", b.solve());
}</lang> Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Runtime: about 0.67 seconds.
OCaml
This uses a breadth-first move search, so will find a move-optimal solution. <lang OCaml>type dir = U | D | L | R type move_t = Move of dir | Push of dir
let letter = function
| Push(U) -> 'U' | Push(D) -> 'D' | Push(L) -> 'L' | Push(R) -> 'R' | Move(U) -> 'u' | Move(D) -> 'd' | Move(L) -> 'l' | Move(R) -> 'r'
let cols = ref 0 let delta = function U -> -(!cols) | D -> !cols | L -> -1 | R -> 1
let store = Hashtbl.create 251 let mark t = Hashtbl.add store t true let marked t = Hashtbl.mem store t
let show ml =
List.iter (fun c -> print_char (letter c)) (List.rev ml); print_newline()
let gen_moves (x,boxes) bd =
let empty i = bd.(i) = ' ' && not (List.mem i boxes) in
let check l dir =
let dx = delta dir in
let x1 = x+dx in
if List.mem x1 boxes then (
if empty (x1+dx) then Push(dir) :: l else l
) else (
if bd.(x1) = ' ' then Move(dir) :: l else l
) in
(List.fold_left check [] [U; L; R; D])
let do_move (x,boxes) = function
| Push(d) -> let dx = delta d in
let x1 = x+dx in let x2 = x1+dx in
let rec shift = function
| [] -> failwith "shift"
| h :: t -> if h = x1 then x2 :: t else h :: shift t in
x1, List.fast_sort compare (shift boxes)
| Move(d) -> (x+(delta d)), boxes
let init_pos bd =
let p = ref 0 in
let q = ref [] in
let check i c =
if c = '$' || c = '*' then q := i::!q
else if c = '@' then p := i in (
Array.iteri check bd;
(!p, List.fast_sort compare !q);
)
let final_box bd =
let check (i,l) c = if c = '.' || c = '*' then (i+1,i::l) else (i+1,l) in List.fast_sort compare (snd (Array.fold_left check (0,[]) bd))
let array_of_input inp =
let r = List.length inp and c = String.length (List.hd inp) in
let a = Array.create (r*c) ' ' in (
for i = 0 to pred r do
let s = List.nth inp i in
for j = 0 to pred c do a.(i*c+j) <- s.[j] done
done;
cols := c; a)
let solve b =
let board = array_of_input b in
let targets = final_box board in
let solved pos = targets = snd pos in
let clear = Array.map (function '#' -> '#' | _ -> ' ') in
let bdc = clear board in
let q = Queue.create () in
let pos1 = init_pos board in
begin
mark pos1;
Queue.add (pos1, []) q;
while not (Queue.is_empty q) do
let curr, mhist = Queue.pop q in
let moves = gen_moves curr bdc in
let check m =
let next = do_move curr m in
if not (marked next) then
if solved next then (show (m::mhist); exit 0)
else (mark next; Queue.add (next,m::mhist) q) in
List.iter check moves
done;
print_endline "No solution"
end;;
let level = ["#######";
"# #";
"# #";
"#. # #";
"#. $$ #";
"#.$$ #";
"#.# @#";
"#######"] in
solve level</lang> Output:
luULLulDDurrrddlULrruLLrrUruLLLulD
PicoLisp
This searches for a solution, without trying for the push-optimal one. The player moves between the pushes, however, are minimized. <lang PicoLisp>(load "@lib/simul.l")
- Display board
(de display ()
(disp *Board NIL
'((This)
(pack
(if2 (== This *Pos) (memq This *Goals)
"+" # Player on goal
"@" # Player elsewhere
(if (: val) "*" ".") # On gloal
(or (: val) " ") ) # Elsewhere
" " ) ) ) )
- Initialize
(de main (Lst)
(mapc
'((B L)
(mapc
'((This C)
(case C
(" ")
("." (push '*Goals This))
("@" (setq *Pos This))
("$" (=: val C) (push '*Boxes This))
(T (=: val C)) ) )
B L ) )
(setq *Board (grid (length (car Lst)) (length Lst)))
(apply mapcar (flip (mapcar chop Lst)) list) )
(display) )
- Generate possible push-moves
(de pushes ()
(make
(for Box *Boxes
(unless (or (; (west Box) val) (; (east Box) val))
(when (moves (east Box))
(link (cons (cons Box (west Box)) *Pos "L" @)) )
(when (moves (west Box))
(link (cons (cons Box (east Box)) *Pos "R" @)) ) )
(unless (or (; (south Box) val) (; (north Box) val))
(when (moves (north Box))
(link (cons (cons Box (south Box)) *Pos "D" @)) )
(when (moves (south Box))
(link (cons (cons Box (north Box)) *Pos "U" @)) ) ) ) ) )
- Moves of player to destination
(de moves (Dst Hist)
(or
(== Dst *Pos)
(mini length
(extract
'((Dir)
(with ((car Dir) Dst)
(cond
((== This *Pos) (cons (cdr Dir)))
((: val))
((memq This Hist))
((moves This (cons Dst Hist))
(cons (cdr Dir) @) ) ) ) )
'((west . "r") (east . "l") (south . "u") (north . "d")) ) ) ) )
- Find solution
(de go (Res)
(unless (idx '*Hist (sort (copy *Boxes)) T) # No repeated state
(if (find '((This) (<> "$" (: val))) *Goals)
(pick
'((Psh)
(setq # Move
*Pos (caar Psh)
*Boxes (cons (cdar Psh) (delq *Pos *Boxes)) )
(put *Pos 'val NIL)
(put (cdar Psh) 'val "$")
(prog1 (go (append (cddr Psh) Res))
(setq # Undo move
*Pos (cadr Psh)
*Boxes (cons (caar Psh) (delq (cdar Psh) *Boxes)) )
(put (cdar Psh) 'val NIL)
(put (caar Psh) 'val "$") ) )
(pushes) )
(display) # Display solution
(pack (flip Res)) ) ) )</lang>
Test: <lang PicoLisp>(main
(quote
"#######"
"# #"
"# #"
"#. # #"
"#. $$ #"
"#.$$ #"
"#.# @#"
"#######" ) )
(prinl) (go)</lang> Output:
8 # # # # # # # 7 # # 6 # # 5 # . # # 4 # . $ $ # 3 # . $ $ # 2 # . # @ # 1 # # # # # # # a b c d e f g 8 # # # # # # # 7 # # 6 # @ # 5 # * # # 4 # * # 3 # * # 2 # * # # 1 # # # # # # # a b c d e f g -> "uuulDLLulDDurrrrddlUruLLLrrddlUruLdLUUdrruulLulD"
Python
<lang python>from array import array from collections import deque import psyco
data = [] nrows = 0 px = py = 0 sdata = "" ddata = ""
def init(board):
global data, nrows, sdata, ddata, px, py data = filter(None, board.splitlines()) nrows = max(len(r) for r in data)
maps = {' ':' ', '.': '.', '@':' ', '#':'#', '$':' '}
mapd = {' ':' ', '.': ' ', '@':'@', '#':' ', '$':'*'}
for r, row in enumerate(data):
for c, ch in enumerate(row):
sdata += maps[ch]
ddata += mapd[ch]
if ch == '@':
px = c
py = r
def push(x, y, dx, dy, data):
if sdata[(y+2*dy) * nrows + x+2*dx] == '#' or \
data[(y+2*dy) * nrows + x+2*dx] != ' ':
return None
data2 = array("c", data)
data2[y * nrows + x] = ' '
data2[(y+dy) * nrows + x+dx] = '@'
data2[(y+2*dy) * nrows + x+2*dx] = '*'
return data2.tostring()
def is_solved(data):
for i in xrange(len(data)):
if (sdata[i] == '.') != (data[i] == '*'):
return False
return True
def solve():
open = deque([(ddata, "", px, py)])
visited = set([ddata])
dirs = ((0, -1, 'u', 'U'), ( 1, 0, 'r', 'R'),
(0, 1, 'd', 'D'), (-1, 0, 'l', 'L'))
lnrows = nrows
while open:
cur, csol, x, y = open.popleft()
for di in dirs:
temp = cur
dx, dy = di[0], di[1]
if temp[(y+dy) * lnrows + x+dx] == '*':
temp = push(x, y, dx, dy, temp)
if temp and temp not in visited:
if is_solved(temp):
return csol + di[3]
open.append((temp, csol + di[3], x+dx, y+dy))
visited.add(temp)
else:
if sdata[(y+dy) * lnrows + x+dx] == '#' or \
temp[(y+dy) * lnrows + x+dx] != ' ':
continue
data2 = array("c", temp)
data2[y * lnrows + x] = ' '
data2[(y+dy) * lnrows + x+dx] = '@'
temp = data2.tostring()
if temp not in visited:
if is_solved(temp):
return csol + di[2]
open.append((temp, csol + di[2], x+dx, y+dy))
visited.add(temp)
return "No solution"
level = """\
- #
- #
- . # #
- . $$ #
- .$$ #
- .# @#
- """
psyco.full() init(level) print level, "\n\n", solve()</lang> Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Runtime: about 0.90 seconds.
Tcl
This code does a breadth-first search so it finds a solution with a minimum number of moves.
<lang tcl>package require Tcl 8.5
proc solveSokoban b {
set cols [string length [lindex $b 0]]
set dxes [list [expr {-$cols}] $cols -1 1]
set i 0
foreach c [split [join $b ""] ""] {
switch $c { " " {lappend bdc " "} "#" {lappend bdc "#"} "@" {lappend bdc " ";set startplayer $i } "$" {lappend bdc " ";lappend startbox $i} "." {lappend bdc " "; lappend targets $i} "+" {lappend bdc " ";set startplayer $i; lappend targets $i} "*" {lappend bdc " ";lappend startbox $i;lappend targets $i} } incr i
}
set q [list [list $startplayer $startbox] {}]
set store([lindex $q 0]) {}
for {set idx 0} {$idx < [llength $q]} {incr idx 2} {
lassign [lindex $q $idx] x boxes foreach dir {U D L R} dx $dxes { if {[set x1 [expr {$x + $dx}]] in $boxes} { if {[lindex $bdc [incr x1 $dx]] ne " " || $x1 in $boxes} { continue } set tmpboxes $boxes set x1 [expr {$x + $dx}] for {set i 0} {$i < [llength $boxes]} {incr i} { if {[lindex $boxes $i] == $x1} { lset tmpboxes $i [expr {$x1 + $dx}] break } } if {$dx == 1 || $dx == -1} { set next [list $x1 $tmpboxes] } else { set next [list $x1 [lsort -integer $tmpboxes]] } if {![info exists store($next)]} { if {$targets eq [lindex $next 1]} { foreach c [lindex $q [expr {$idx + 1}]] { lassign $c ispush olddir if {$ispush} { append solution $olddir } else { append solution [string tolower $olddir] } } return [append solution $dir] } set store($next) {} set nm [lindex $q [expr {$idx + 1}]] lappend q $next lappend q [lappend nm [list 1 $dir]] } } elseif {[lindex $bdc $x1] eq " "} { set next [list [expr {$x + $dx}] $boxes] if {![info exists store($next)]} { set store($next) {} set nm [lindex $q [expr {$idx + 1}]] lappend q $next lappend q [lappend nm [list 0 $dir]] } } }
} error "no solution"
}</lang> Demonstration code: <lang tcl>set level {
"#######" "# #" "# #" "#. # #" "#. $$ #" "#.$$ #" "#.# @#" "#######"
} puts [solveSokoban $level]</lang>
Output:ulULLulDDurrrddlULrruLLrrUruLLLulD
Runtime with stock Tcl 8.5 installation: ≅2.2 seconds