Sokoban
From Rosetta Code
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.
Contents |
[edit] 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <assert.h>
#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 };
#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"};
#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(
#define BIG 0
#if BIG == 0
8, 7,
"#######"
"# #"
"# #"
"#. # #"
"#. $$ #"
"#.$$ #"
"#.# @#"
"#######"
#elif BIG == 1
5, 13,
"#############"
"# # #"
"# $$$$$$$ @#"
"#....... #"
"#############"
#elif BIG == 2
5, 13,
"#############"
"#... # #"
"#.$$$$$$$ @#"
"#... #"
"#############"
#else
11, 19,
" ##### "
" # # "
" # # "
" ### #$## "
" # # "
"### #$## # ######"
"# # ## ##### .#"
"# $ $ ..#"
"##### ### #@## .#"
" # #########"
" ####### "
#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);
#if 0
free(buckets);
free(board);
free(goals);
free(live);
while (block_root) {
void *tmp = block_root->next;
free(block_root);
block_root = tmp;
}
#endif
return 0;
}
[edit] C++
[edit] Set-based Version
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.
#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;
}
Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
[edit] Unordered Set-based Version
Alternative version, about twice faster (about 2.1 seconds runtime), same output.
#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<Table>> 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;
}
[edit] D
[edit] Shorter Version
This version uses the queue defined in the Queue/Usage task.
import std.string, std.typecons, std.exception, std.algorithm;
import queue_usage2; // No queue in DMD 2.061 Phobos.
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 =
"#######
# #
# #
#. # #
#. $$ #
#.$$ #
#.# @#
#######";
immutable b = Board(level.splitLines());
writeln(level, "\n\n", b.solve());
}
- Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Run-time about 0.61 seconds with DMD compiler.
[edit] Faster Version
This code is not idiomatic D, it retains most of the style of the C version it's based on.
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;
}
[edit] Go
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.
package main
import (
"fmt"
"strings"
)
func main() {
level := `
#######
# #
# #
#. # #
#. $$ #
#.$$ #
#.# @#
#######`
fmt.Printf("level:%s\n", level)
fmt.Printf("solution:\n%s\n", solve(level))
}
func solve(board string) string {
buffer = make([]byte, len(board))
width := strings.Index(board[1:], "\n") + 1
dirs := []struct {
move, push string
dPos int
}{
{"u", "U", -width},
{"r", "R", 1},
{"d", "D", width},
{"l", "L", -1},
}
visited := map[string]bool{board: true}
open := []state{state{board, "", strings.Index(board, "@")}}
for len(open) > 0 {
s1 := &open[0]
open = open[1:]
for _, dir := range dirs {
var newBoard, newSol string
newPos := s1.pos + dir.dPos
switch s1.board[newPos] {
case '$', '*':
newBoard = s1.push(dir.dPos)
if newBoard == "" || visited[newBoard] {
continue
}
newSol = s1.cSol + dir.push
if strings.IndexAny(newBoard, ".+") < 0 {
return newSol
}
case ' ', '.':
newBoard = s1.move(dir.dPos)
if visited[newBoard] {
continue
}
newSol = s1.cSol + dir.move
default:
continue
}
open = append(open, state{newBoard, newSol, newPos})
visited[newBoard] = true
}
}
return "No solution"
}
type state struct {
board string
cSol string
pos int
}
var buffer []byte
func (s *state) move(dPos int) string {
copy(buffer, s.board)
if buffer[s.pos] == '@' {
buffer[s.pos] = ' '
} else {
buffer[s.pos] = '.'
}
newPos := s.pos + dPos
if buffer[newPos] == ' ' {
buffer[newPos] = '@'
} else {
buffer[newPos] = '+'
}
return string(buffer)
}
func (s *state) push(dPos int) string {
newPos := s.pos + dPos
boxPos := newPos + dPos
switch s.board[boxPos] {
case ' ', '.':
default:
return ""
}
copy(buffer, s.board)
if buffer[s.pos] == '@' {
buffer[s.pos] = ' '
} else {
buffer[s.pos] = '.'
}
if buffer[newPos] == '$' {
buffer[newPos] = '@'
} else {
buffer[newPos] = '+'
}
if buffer[boxPos] == ' ' {
buffer[boxPos] = '$'
} else {
buffer[boxPos] = '*'
}
return string(buffer)
}
- Output:
level: ####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### solution: ulULLulDDurrrddlULrruLLrrUruLLLulD
[edit] OCaml
This uses a breadth-first move search, so will find a move-optimal solution.
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
Output:
luULLulDDurrrddlULrruLLrrUruLLLulD
[edit] PicoLisp
This searches for a solution, without trying for the push-optimal one. The player moves between the pushes, however, are minimized.
(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)) ) ) )
Test:
(main
(quote
"#######"
"# #"
"# #"
"#. # #"
"#. $$ #"
"#.$$ #"
"#.# @#"
"#######" ) )
(prinl)
(go)
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"
[edit] 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()
Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Runtime: about 0.90 seconds.
[edit] Tcl
This code does a breadth-first search so it finds a solution with a minimum number of moves.
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"
}
Demonstration code:
set level {Output:
"#######"
"# #"
"# #"
"#. # #"
"#. $$ #"
"#.$$ #"
"#.# @#"
"#######"
}
puts [solveSokoban $level]
ulULLulDDurrrddlULrruLLrrUruLLLulD
Runtime with stock Tcl 8.5 installation: ≅2.2 seconds
