Sokoban

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, 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. <lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <string.h>
3. include <unistd.h>
4. include <stdint.h>
5. include <assert.h>
6. include <stdbool.h>

int w, h, n_boxes; uint8_t *board, *goals, *live;

typedef uint16_t cidx_t; typedef uint32_t hash_t;

/* board configuration is represented by an array of cell indices

  of player and boxes */

typedef struct state_t state_t;

struct state_t { // variable length hash_t h; state_t *prev, *next, *qnext; cidx_t c[]; };

size_t state_size, block_size = 32; state_t *block_root, *block_head;

inline state_t* newstate(state_t *parent) { inline state_t* next_of(state_t *s) { return (void*)((uint8_t*)s + state_size); }

state_t *ptr; if (!block_head) { block_size *= 2; state_t *p = malloc(block_size * state_size); assert(p); p->next = block_root; block_root = p; ptr = (void*)((uint8_t*)p + state_size * block_size); p = block_head = next_of(p); state_t *q; for (q = next_of(p); q < ptr; p = q, q = next_of(q)) p->next = q; p->next = NULL; }

ptr = block_head; block_head = block_head->next;

ptr->prev = parent; ptr->h = 0; return ptr; }

inline void unnewstate(state_t *p) { p->next = block_head; block_head = p; }

enum { space, wall, player, box };

1. define E "\033["

const char * const glyph1[] = { " ", "#", E"31m@"E"m", E"33m$"E"m"}; const char * const glyph2[] = { E"32m."E"m", "#", E"32m@"E"m", E"32m$"E"m"};

1. undef E

// mark up positions where a box definitely should not be void mark_live(const int c) { const int y = c / w, x = c % w; if (live[c]) return;

live[c] = 1; if (y > 1 && board[c - w] != wall && board[c - w * 2] != wall) mark_live(c - w); if (y < h - 2 && board[c + w] != wall && board[c + w * 2] != wall) mark_live(c + w); if (x > 1 && board[c - 1] != wall && board[c - 2] != wall) mark_live(c - 1); if (x < w - 2 && board[c + 1] != wall && board[c + 2] != wall) mark_live(c + 1); }

state_t *parse_board(const int y, const int x, const char *s) { w = x, h = y; board = calloc(w * h, sizeof(uint8_t)); assert(board); goals = calloc(w * h, sizeof(uint8_t)); assert(goals); live = calloc(w * h, sizeof(uint8_t)); assert(live);

n_boxes = 0; for (int i = 0; s[i]; i++) { switch(s[i]) { case '#': board[i] = wall; continue;

case '.': // fallthrough case '+': goals[i] = 1; // fallthrough case '@': continue;

case '*': goals[i] = 1; // fallthrough case '$': n_boxes++; continue; default: continue; } }

const int is = sizeof(int); state_size = (sizeof(state_t) + (1 + n_boxes) * sizeof(cidx_t) + is - 1) / is * is;

state_t *state = newstate(NULL);

for (int i = 0, j = 0; i < w * h; i++) { if (goals[i]) mark_live(i); if (s[i] == '$' || s[i] == '*') state->c[++j] = i; else if (s[i] == '@' || s[i] == '+') state->c[0] = i; }

return state; }

void show_board(const state_t *s) { unsigned char b[w * h]; memcpy(b, board, w * h);

b[ s->c[0] ] = player; for (int i = 1; i <= n_boxes; i++) b[ s->c[i] ] = box;

for (int i = 0; i < w * h; i++) { printf((goals[i] ? glyph2 : glyph1)[ b[i] ]); if (! ((1 + i) % w)) putchar('\n'); } }

// K&R hash function inline void hash(state_t *s) { if (!s->h) { register hash_t ha = 0; cidx_t *p = s->c; for (int i = 0; i <= n_boxes; i++) ha = p[i] + 31 * ha; s->h = ha; } }

state_t **buckets; hash_t hash_size, fill_limit, filled;

void extend_table() { int old_size = hash_size;

if (!old_size) { hash_size = 1024; filled = 0; fill_limit = hash_size * 3 / 4; // 0.75 load factor } else { hash_size *= 2; fill_limit *= 2; }

buckets = realloc(buckets, sizeof(state_t*) * hash_size); assert(buckets);

// rehash memset(buckets + old_size, 0, sizeof(state_t*) * (hash_size - old_size));

const hash_t bits = hash_size - 1; for (int i = 0; i < old_size; i++) { state_t *head = buckets[i]; buckets[i] = NULL; while (head) { state_t *next = head->next; const int j = head->h & bits; head->next = buckets[j]; buckets[j] = head; head = next; } } }

state_t *lookup(state_t *s) { hash(s); state_t *f = buckets[s->h & (hash_size - 1)]; for (; f; f = f->next) { if (//(f->h == s->h) && !memcmp(s->c, f->c, sizeof(cidx_t) * (1 + n_boxes))) break; }

return f; }

bool add_to_table(state_t *s) { if (lookup(s)) { unnewstate(s); return false; }

if (filled++ >= fill_limit) extend_table();

hash_t i = s->h & (hash_size - 1);

s->next = buckets[i]; buckets[i] = s; return true; }

bool success(const state_t *s) { for (int i = 1; i <= n_boxes; i++) if (!goals[s->c[i]]) return false; return true; }

state_t *move_me(state_t *s, const int dy, const int dx) { const int y = s->c[0] / w; const int x = s->c[0] % w; const int y1 = y + dy; const int x1 = x + dx; const int c1 = y1 * w + x1;

if (y1 < 0 || y1 > h || x1 < 0 || x1 > w || board[c1] == wall) return NULL;

int at_box = 0; for (int i = 1; i <= n_boxes; i++) { if (s->c[i] == c1) { at_box = i; break; } }

int c2; if (at_box) { c2 = c1 + dy * w + dx; if (board[c2] == wall || !live[c2]) return NULL; for (int i = 1; i <= n_boxes; i++) if (s->c[i] == c2) return NULL; }

state_t *n = newstate(s); memcpy(n->c + 1, s->c + 1, sizeof(cidx_t) * n_boxes);

cidx_t *p = n->c; p[0] = c1;

if (at_box) p[at_box] = c2;

// leet bubble sort for (int i = n_boxes; --i; ) { cidx_t t = 0; for (int j = 1; j < i; j++) { if (p[j] > p[j + 1]) t = p[j], p[j] = p[j+1], p[j+1] = t; } if (!t) break; }

return n; }

state_t *next_level, *done;

bool queue_move(state_t *s) { if (!s || !add_to_table(s)) return false;

if (success(s)) { puts("\nSuccess!"); done = s; return true; }

s->qnext = next_level; next_level = s; return false; }

bool do_move(state_t *s) { return queue_move(move_me(s, 1, 0)) || queue_move(move_me(s, -1, 0)) || queue_move(move_me(s, 0, 1)) || queue_move(move_me(s, 0, -1)); }

void show_moves(const state_t *s) { if (s->prev) show_moves(s->prev); usleep(200000); printf("\033[H"); show_board(s); }

int main() { state_t *s = parse_board(

1. define BIG 0

1. if BIG == 0

8, 7, "#######" "# #" "# #" "#. # #" "#. $$ #" "#.$$ #" "#.# @#" "#######"

1. elif BIG == 1

5, 13, "#############" "# # #" "# $$$$$$$ @#" "#....... #" "#############"

1. elif BIG == 2

5, 13, "#############" "#... # #" "#.$$$$$$$ @#" "#... #" "#############"

1. else

11, 19, " ##### " " # # " " # # " " ### #$## " " # # " "### #$## # ######" "# # ## ##### .#" "# $ $ ..#" "##### ### #@## .#" " # #########" " ####### "

1. endif

);

show_board(s); extend_table(); queue_move(s); for (int i = 0; !done; i++) { printf("depth %d\r", i); fflush(stdout);

state_t *head = next_level; for (next_level = NULL; head && !done; head = head->qnext) do_move(head);

if (!next_level) { puts("no solution?"); return 1; } }

printf("press any key to see moves\n"); getchar(), puts("\033[H\033[J"); show_moves(done);

1. if 0

free(buckets); free(board); free(goals); free(live);

while (block_root) { void *tmp = block_root->next; free(block_root); block_root = tmp; }

1. endif

return 0; }</lang>

C++

Set-based Version

Works with: C++11

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>

1. include <string>
2. include <vector>
3. include <queue>
4. include <regex>
5. include <tuple>
6. include <set>
7. 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

Unordered Set-based Version

Works with: C++11

Works with: Boost

Works with: GCC 4.6

Alternative version, about twice faster (about 2.1 seconds runtime), same output. <lang cpp>#include <iostream>

1. include <string>
2. include <vector>
3. include <queue>
4. include <tuple>
5. include <array>
6. include <map>
7. include <boost/algorithm/string.hpp>
8. 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

Shorter Version

Translation of: C++

<lang d>import std.string, std.typecons, std.exception, std.algorithm;

// No queue in dmd 2.059 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 {

   private enum El : char { floor=' ', wall='#', goal='.',
                            box='$', player='@', boxOnGoal='*' }
   private alias string CTable;
   private immutable size_t ncols;
   private immutable CTable sData, dData;
   private 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(c.inPattern(" #.$@*"), "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;
               }
           }
   }

   private 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;
   }

   private 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;
   }

   private 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 =

"#######

1. #
2. #
3. . # #
4. . $$ #
5. .$$ #
6. .# @#
   1. 1. 1. 1. 1. 1. ";

   immutable b = Board(level.splitLines());
   writeln(level, "\n\n", b.solve());

}</lang>

Output:

#######
#     #
#     #
#. #  #
#. $$ #
#.$$  #
#.#  @#
#######

ulULLulDDurrrddlULrruLLrrUruLLLulD

Run-time about 0.66 seconds with DMD compiler.

Faster Version

Translation of: C

This code is not idiomatic D, it retains most of the style of the C version it's based on. <lang d>import core.stdc.stdio: printf, puts, fflush, stdout, putchar; import core.stdc.stdlib: malloc, calloc, realloc, free, alloca, exit; import core.stdc.string: memcpy, memset, memcmp;

alias ushort cidx_t; alias uint hash_t;

// Board configuration is represented by an array of cell // indices of player and boxes. struct State {

   hash_t h;
   State* prev, next, qnext;
   cidx_t[0] c;

}

__gshared int w, h, n_boxes; __gshared ubyte* board, goals, live; __gshared size_t state_size, block_size = 32; __gshared State* block_root, block_head;

State* newState(State* parent) nothrow {

   static State* next_of(State *s) nothrow {
       return cast(State*)(cast(ubyte*)s + state_size);
   }

   State *ptr;
   if (!block_head) {
       block_size *= 2;
       State* p = cast(State*)malloc(block_size * state_size);
       if (p == null) exit(1);
       State* q;
       p.next = block_root;
       block_root = p;
       ptr = cast(State*)(cast(ubyte*)p + state_size * block_size);
       p = block_head = next_of(p);
       for (q = next_of(p); q < ptr; p = q, q = next_of(q))
           p.next = q;
       p.next = null;
   }

   ptr = block_head;
   block_head = block_head.next;

   ptr.prev = parent;
   ptr.h = 0;
   return ptr;

}

void unNewState(State* p) nothrow {

   p.next = block_head;
   block_head = p;

}

enum Cell { space, wall, player, box }

// mark up positions where a box definitely should not be void markLive(in int c) nothrow {

   immutable int y = c / w;
   immutable int x = c % w;
   if (live[c])
       return;

   live[c] = 1;
   if (y > 1 && board[c - w] != Cell.wall &&
       board[c - w * 2] != Cell.wall)
       markLive(c - w);
   if (y < h - 2 && board[c + w] != Cell.wall &&
       board[c + w * 2] != Cell.wall)
       markLive(c + w);
   if (x > 1 && board[c - 1] != Cell.wall &&
       board[c - 2] != Cell.wall)
       markLive(c - 1);
   if (x < w - 2 && board[c + 1] != Cell.wall &&
       board[c + 2] != Cell.wall)
       markLive(c + 1);

}

State* parseBoard(in int y, in int x, const char* s) nothrow {

   w = x, h = y;
   board = cast(ubyte*)calloc(w * h, ubyte.sizeof);
   if (board == null) exit(2);
   goals = cast(ubyte*)calloc(w * h, ubyte.sizeof);
   if (goals == null) exit(3);
   live = cast(ubyte*)calloc(w * h, ubyte.sizeof);
   if (live == null) exit(4);

   n_boxes = 0;
   for (int i = 0; s[i]; i++) {
       switch(s[i]) {
           case '#':
               board[i] = Cell.wall;
               continue;
           case '.', '+':
               goals[i] = 1;
               goto case;
           case '@':
               continue;
           case '*':
               goals[i] = 1;
               goto case;
           case '$':
               n_boxes++;
               continue;
           default:
               continue;
       }
   }

   enum int int_size = int.sizeof;
   state_size = (State.sizeof +
                 (1 + n_boxes) * cidx_t.sizeof +
                 int_size - 1)
                / int_size * int_size;

   State* state = newState(null);

   for (cidx_t i = 0, j = 0; i < w * h; i++) {
       if (goals[i])
           markLive(i);
       if (s[i] == '$' || s[i] == '*')
           (cast(cidx_t*)&state.c)[++j] = i;
       else if (s[i] == '@' || s[i] == '+')
           (cast(cidx_t*)&state.c)[0] = i;
   }

   return state;

}

void showBoard(const State* s) nothrow {

   static immutable char*[] glyph1 = [" ", "#", "@", "$"];
   static immutable char*[] glyph2 = [".", "#", "@", "$"];

   auto ptr = cast(char*)alloca(w * h * char.sizeof);
   if (ptr == null) exit(5);
   auto b = ptr[0 .. w * h];

   memcpy(b.ptr, board, w * h);

   b[(cast(cidx_t*)&s.c)[0]] = Cell.player;
   for (int i = 1; i <= n_boxes; i++)
       b[(cast(cidx_t*)&s.c)[i]] = Cell.box;

   for (int i = 0; i < w * h; i++) {
       printf((goals[i] ? glyph2 : glyph1)[b[i]]);
       if (!((1 + i) % w))
           putchar('\n');
   }

}

// K&R hash function void hash(State* s) nothrow {

   if (!s.h) {
       hash_t ha = 0;
       cidx_t* p = cast(cidx_t*)&s.c;
       for (int i = 0; i <= n_boxes; i++)
           ha = p[i] + 31 * ha;
       s.h = ha;
   }

}

__gshared State** buckets; __gshared hash_t hash_size, fill_limit, filled;

void extendTable() nothrow {

   int old_size = hash_size;

   if (!old_size) {
       hash_size = 1024;
       filled = 0;
       fill_limit = hash_size * 3 / 4; // 0.75 load factor
   } else {
       hash_size *= 2;
       fill_limit *= 2;
   }

   buckets = cast(State**)realloc(buckets,
                                  (State*).sizeof * hash_size);
   if (buckets == null) exit(6);

   // rehash
   memset(buckets + old_size,
          0,
          (State*).sizeof * (hash_size - old_size));

   immutable hash_t bits = hash_size - 1;
   for (int i = 0; i < old_size; i++) {
       State *head = buckets[i];
       buckets[i] = null;
       while (head) {
           State* next = head.next;
           immutable int j = head.h & bits;
           head.next = buckets[j];
           buckets[j] = head;
           head = next;
       }
   }

}

State* lookup(State *s) nothrow {

   hash(s);
   State *f = buckets[s.h & (hash_size - 1)];
   for (; f; f = f.next) {
       if (!memcmp((cast(cidx_t*)&s.c), (cast(cidx_t*)&f.c),
                   cidx_t.sizeof * (1 + n_boxes)))
           break;
   }

   return f;

}

bool addToTable(State* s) nothrow {

   if (lookup(s)) {
       unNewState(s);
       return false;
   }

   if (filled++ >= fill_limit)
       extendTable();

   immutable hash_t i = s.h & (hash_size - 1);

   s.next = buckets[i];
   buckets[i] = s;
   return true;

}

bool success(const State* s) nothrow {

   for (int i = 1; i <= n_boxes; i++)
       if (!goals[(cast(cidx_t*)&s.c)[i]])
           return false;
   return true;

}

State* moveMe(State* s, int dy, int dx) nothrow {

   immutable int y = (cast(cidx_t*)&s.c)[0] / w;
   immutable int x = (cast(cidx_t*)&s.c)[0] % w;
   immutable int y1 = y + dy;
   immutable int x1 = x + dx;
   immutable int c1 = y1 * w + x1;

   if (y1 < 0 || y1 > h || x1 < 0 || x1 > w || board[c1] == Cell.wall)
       return null;

   int at_box = 0;
   for (int i = 1; i <= n_boxes; i++) {
       if ((cast(cidx_t*)&s.c)[i] == c1) {
           at_box = i;
           break;
       }
   }

   int c2;
   if (at_box) {
       c2 = c1 + dy * w + dx;
       if (board[c2] == Cell.wall || !live[c2])
           return null;
       for (int i = 1; i <= n_boxes; i++)
           if ((cast(cidx_t*)&s.c)[i] == c2)
               return null;
   }

   State* n = newState(s);
   memcpy((cast(cidx_t*)&n.c) + 1,
          (cast(cidx_t*)&s.c) + 1,
          cidx_t.sizeof * n_boxes);

   cidx_t* p = (cast(cidx_t*)&n.c);
   p[0] = cast(cidx_t)c1;

   if (at_box)
       p[at_box] = cast(cidx_t)c2;

   // Bubble sort
   for (int i = n_boxes; --i; ) {
       cidx_t t = 0;
       for (int j = 1; j < i; j++) {
           if (p[j] > p[j + 1])
               t = p[j], p[j] = p[j+1], p[j+1] = t;
       }
       if (!t)
           break;
   }

   return n;

}

__gshared State* next_level, done;

bool queueMove(State *s) nothrow {

   if (!s || !addToTable(s))
       return false;

   if (success(s)) {
       puts("\nSuccess!");
       done = s;
       return true;
   }

   s.qnext = next_level;
   next_level = s;
   return false;

}

bool do_move(State* s) nothrow {

   return queueMove(moveMe(s,  1,  0)) ||
          queueMove(moveMe(s, -1,  0)) ||
          queueMove(moveMe(s,  0,  1)) ||
          queueMove(moveMe(s,  0, -1));

}

void showMoves(in State* s) nothrow {

   if (s.prev)
       showMoves(s.prev);
   printf("\n");
   showBoard(s);

}

int main() nothrow {

   enum BIG = 0;

   static if (BIG == 0) {
       State* s = parseBoard(8, 7,
       "#######"~
       "#     #"~
       "#     #"~
       "#. #  #"~
       "#. $$ #"~
       "#.$$  #"~
       "#.#  @#"~
       "#######");

   } else static if (BIG == 1) {
       State* s = parseBoard(5, 13,
       "#############"~
       "#  #        #"~
       "# $$$$$$$  @#"~
       "#.......    #"
       "#############");

   } else {
       State* s = parseBoard(11, 19,
       "    #####          "~
       "    #   #          "~
       "    #   #          "~
       "  ### #$##         "~
       "  #      #         "~
       "### #$## #   ######"~
       "#   # ## #####   .#"~
       "# $   $         ..#"~
       "##### ### #@##   .#"~
       "    #     #########"~
       "    #######        ");
   }

   showBoard(s);
   extendTable();
   queueMove(s);
   for (int i = 0; !done; i++) {
       printf("depth %d\r", i);
       fflush(stdout);

       State *head = next_level;
       for (next_level = null; head && !done; head = head.qnext)
           do_move(head);

       if (!next_level) {
           puts("No solution?");
           return 1;
       }
   }

   showMoves(done);

   version (none) {
       free(buckets);
       free(board);
       free(goals);
       free(live);

       while (block_root) {
           auto tmp = block_root.next;
           free(block_root);
           block_root = tmp;
       }
   }

   return 0;

}</lang>

OCaml

Translation of: Python

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")

1. 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
           " " ) ) ) )

1. 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) )

1. 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" @)) ) ) ) ) )

1. 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")) ) ) ) )

1. 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

Translation of: D

Works with: Psyco

Works with: Python 2.6

<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 = """\

2. #
3. #
4. . # #
5. . $$ #
6. .$$ #
7. .# @#
   1. 1. 1. 1. 1. 1. """

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.

Translation of: OCaml

<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