Sokoban: Difference between revisions
(→{{header|C}}: greatly improved speed and memory behavior; can solve some fairly large puzzles now.) |
(→{{header|C}}: bugs R us) |
||
Line 50: | Line 50: | ||
enum { space, wall, player, box }; |
enum { space, wall, player, box }; |
||
#define E "\033[" |
#define E "\033[" |
||
char *glyph1[] = { " ", "#", E"31m@"E"m", E" |
char *glyph1[] = { " ", "#", E"31m@"E"m", E"33m$"E"m"}; |
||
char *glyph2[] = { E" |
char *glyph2[] = { E"32m."E"m", "#", E"32m@"E"m", E"32m$"E"m"}; |
||
#undef E |
#undef E |
||
Line 102: | Line 102: | ||
for (int i = 0, j = 0; i < w * h; i++) { |
for (int i = 0, j = 0; i < w * h; i++) { |
||
if (goals[i]) mark_live(i); |
if (goals[i]) mark_live(i); |
||
if (s[i] == '$' || s[i] == ' |
if (s[i] == '$' || s[i] == '*') |
||
state->c[++j] = i; |
state->c[++j] = i; |
||
else if (s[i] == '@' || s[i] == '+') |
else if (s[i] == '@' || s[i] == '+') |
||
Line 142: | Line 142: | ||
state_t **buckets = 0; |
state_t **buckets = 0; |
||
hash_t hash_size = 0, fill_limit = 0, filled = 0; |
hash_t hash_size = 0, fill_limit = 0, filled = 0; |
||
void status_report() |
|||
{ |
|||
printf("hash size %d, used %d\n", hash_size, filled); |
|||
int cnt[100] = {0}; |
|||
for (int i = 0; i < hash_size; i++) { |
|||
state_t *head = buckets[i]; |
|||
int j; |
|||
for (j = 0; j < 99 && head; j++) |
|||
⚫ | |||
cnt[j]++; |
|||
} |
|||
printf("chain lengths:\n"); |
|||
for (int i = 0; i < 100; i++) |
|||
if (cnt[i]) printf("%d %d\n", i, cnt[i]); |
|||
} |
|||
void extend_table() |
void extend_table() |
||
{ |
{ |
||
int old_size = hash_size; |
int old_size = hash_size; |
||
if (!old_size) { |
if (!old_size) { |
||
hash_size = 1 << 20; |
hash_size = 1 << 20; |
||
Line 151: | Line 168: | ||
fill_limit = hash_size * 3 / 4; /* .75 load factor */ |
fill_limit = hash_size * 3 / 4; /* .75 load factor */ |
||
} else |
} else |
||
hash_size *= |
hash_size *= 4, fill_limit *= 4; |
||
hash_t bits = hash_size - 1; |
hash_t bits = hash_size - 1; |
||
Line 178: | Line 195: | ||
hash(s); |
hash(s); |
||
state_t *f = buckets[s->h & (hash_size - 1)]; |
|||
f; |
|||
⚫ | |||
for (; f; f = f->next) { |
|||
if ((f->h == s->h) |
|||
&& !memcmp(s->c, f->c, sizeof(cidx_t) * (1 + n_boxes))) |
&& !memcmp(s->c, f->c, sizeof(cidx_t) * (1 + n_boxes))) |
||
break; |
|||
} |
|||
return |
return f; |
||
} |
} |
||
Line 272: | Line 291: | ||
if (success(s)) { |
if (success(s)) { |
||
puts(" |
puts("\nSuccessful!"); |
||
done = s; |
done = s; |
||
return 1; |
return 1; |
||
Line 301: | Line 320: | ||
{ |
{ |
||
state_t *s = parse_board( |
state_t *s = parse_board( |
||
#define BIG |
#define BIG 1 |
||
#if |
#if BIG == 0 |
||
8, 7, |
8, 7, |
||
"#######" |
"#######" |
||
Line 312: | Line 331: | ||
"#.# @#" |
"#.# @#" |
||
"#######" |
"#######" |
||
#elif BIG == 1 |
|||
5, 13, |
|||
"#############" |
|||
"# # #" |
|||
"# $$$$$$$ @#" |
|||
"#....... #" |
|||
"#############" |
|||
#else |
#else |
||
11, 19, |
11, 19, |
||
Line 328: | Line 354: | ||
); |
); |
||
show_board(s); |
|||
queue_move(s); |
queue_move(s); |
||
for (int i = 0; !done; i++) { |
for (int i = 0; !done; i++) { |
||
Line 335: | Line 362: | ||
for (next_level = 0; head && !done; head = head->qnext) |
for (next_level = 0; head && !done; head = head->qnext) |
||
do_move(head, i); |
do_move(head, i); |
||
if (!next_level) { |
|||
puts("no solution?"); |
|||
return 1; |
|||
} |
|||
} |
} |
||
Revision as of 03:45, 6 May 2012
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. 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>
- include <stdint.h>
- include <ctype.h>
int w, h, n_boxes; unsigned char *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 { hash_t h; state_t *prev, *next, *qnext; cidx_t c[]; };
size_t state_size; inline state_t* newstate() { state_t *s = malloc(state_size); s->h = 0; return s; }
enum { space, wall, player, box };
- define E "\033["
char *glyph1[] = { " ", "#", E"31m@"E"m", E"33m$"E"m"}; char *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(int c) { 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(int y, int x, char *s) { w = x, h = y; board = calloc(w * h, sizeof(uint8_t)); goals = calloc(w * h, sizeof(uint8_t)); live = calloc(w * h, sizeof(uint8_t));
n_boxes = 0; for (int i = 0; s[i]; i++) { switch(s[i]) { case '#': board[i] = wall; continue;
case '.': case '+': goals[i] = 1; case '@': continue;
case '*': goals[i] = 1; case '$': n_boxes++; continue; } }
int is = sizeof(int); state_size = (sizeof(state_t) + (1 + n_boxes) * sizeof(cidx_t) + is - 1) / is * is;
state_t *state = newstate();
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(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 */ hash_t hash(state_t *s) { hash_t h = s->h; if (!h) { cidx_t *p = s->c; for (int i = 0; i <= n_boxes; i++) h = p[i] + 31 * h; s->h = h; } return h; }
state_t **buckets = 0; hash_t hash_size = 0, fill_limit = 0, filled = 0;
void status_report() { printf("hash size %d, used %d\n", hash_size, filled); int cnt[100] = {0}; for (int i = 0; i < hash_size; i++) { state_t *head = buckets[i]; int j; for (j = 0; j < 99 && head; j++) head = head->next; cnt[j]++; } printf("chain lengths:\n"); for (int i = 0; i < 100; i++) if (cnt[i]) printf("%d %d\n", i, cnt[i]); }
void extend_table() { int old_size = hash_size;
if (!old_size) { hash_size = 1 << 20; filled = 0; fill_limit = hash_size * 3 / 4; /* .75 load factor */ } else hash_size *= 4, fill_limit *= 4;
hash_t bits = hash_size - 1; buckets = realloc(buckets, state_size * hash_size);
/* rehash */ memset(buckets + old_size, 0, sizeof(state_t*) * old_size);
for (int i = 0; i < old_size; i++) { state_t *head = buckets[i]; buckets[i] = 0;
while (head) { hash_t j = head->h & bits; state_t *next = head->next; head->next = buckets[j]; buckets[j] = head; head = next; } } }
state_t *lookup(state_t *s) { if (!hash_size) return 0; 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; }
int add_to_table(state_t *s) { hash(s); if (lookup(s)) return 0;
if (filled++ >= fill_limit) extend_table();
hash_t i = s->h & (hash_size - 1);
s->next = buckets[i]; buckets[i] = s; return 1; }
int success(state_t *s) { for (int i = 1; i <= n_boxes; i++) if (!goals[s->c[i]]) return 0; return 1; }
state_t* move_me(state_t *s, int dy, int dx) { int y = s->c[0] / w, x = s->c[0] % w; int y1 = y + dy, x1 = x + dx; int c1 = y1 * w + x1, c2;
if (y1 < 0 || y1 > h || x1 < 0 || x1 > w || board[c1] == wall) return 0;
int at_box = 0; for (int i = 1; i <= n_boxes; i++) { if (s->c[i] != c1) continue; at_box = i; break; }
if (at_box) { c2 = c1 + dy * w + dx; if (board[c2] == wall) return 0; for (int i = 1; i <= n_boxes; i++) if (s->c[i] == c2) return 0; }
state_t *n = newstate(); n->prev = s; n->next = 0; memcpy(n->c, s->c, sizeof(cidx_t) * (1 + 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; ) { int t = 0; for (int j = 1; j < i; j++) { if (p[j] < p[j + 1]) continue; cidx_t tmp = p[j]; p[j] = p[j + 1]; p[j + 1] = tmp; t = 1; } if (!t) break; } return n; }
state_t *current_level = 0, *next_level = 0, *done = 0;
int queue_move(state_t *s) { /* even bad configs gets added to lookup table */ if (!s || !add_to_table(s)) return 0;
/* but won't get queued */ for (int i = 1; i <= n_boxes; i++) if (!live[ s->c[i] ]) return 0;
if (success(s)) { puts("\nSuccessful!"); done = s; return 1; }
s->qnext = next_level; next_level = s; return 0; }
int do_move(state_t *s, int d) { 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(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 1
- if BIG == 0
8, 7, "#######" "# #" "# #" "#. # #" "#. $$ #" "#.$$ #" "#.# @#" "#######"
- elif BIG == 1
5, 13, "#############" "# # #" "# $$$$$$$ @#" "#....... #" "#############"
- else
11, 19, " ##### " " # # " " # $ # " " ### # ## " " # # " "### #$## # ######" "# # ## ##### .#" "# $ $ ..#" "##### ### #@## .#" " # #########" " ####### "
- endif
);
show_board(s); queue_move(s); for (int i = 0; !done; i++) { printf("depth %d\r", i); fflush(stdout); state_t *head = next_level; for (next_level = 0; head && !done; head = head->qnext) do_move(head, i); 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);
return 0; }</lang>
C++
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. <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
Unordered Set-based Version
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
Simpler Version
<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 =
"#######
- #
- #
- . # #
- . $$ #
- .$$ #
- .# @#
- ";
immutable b = Board(level.splitLines()); writeln(level, "\n\n", b.solve());
}</lang>
- Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Faster Version
Similar code, with a memory pool to speed up the allocations of boards. The output is the same. <lang d>import std.string, std.typecons, std.exception, std.algorithm;
pure nothrow extern(C) {
void* malloc(size_t size); void* calloc(size_t num, size_t size); void exit(int status); void free(void* ptr);
}
// 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 nothrow { if (length == 0) exit(1); // GrowableCircularQueue is empty immutable oldHead = head; head = (head + 1) % A.length; length--; return A[oldHead]; }
}
struct MemoryPool(T, int MAX_BLOCK_BYTES=1 << 17) {
static assert(!is(T == class), "MemoryPool is designed for native data."); static assert(MAX_BLOCK_BYTES >= 1, "MemoryPool: MAX_BLOCK_BYTES must be >= 1 bytes.");
static struct Block { static assert(MAX_BLOCK_BYTES >= T.sizeof, "MemoryPool: MAX_BLOCK_BYTES must be" ~ " bigger than a T."); static if ((T.sizeof * 5) > MAX_BLOCK_BYTES) pragma(msg, "MemoryPool: Block is very small.");
T[(MAX_BLOCK_BYTES / T.sizeof)] items; }
__gshared static Block*[] blocks;
__gshared static T* nextFree, lastFree;
static T* newItem() nothrow { if (nextFree >= lastFree) { blocks ~= cast(Block*)calloc(1, Block.sizeof); if (blocks[$ - 1] == null) exit(2); // calloc failed nextFree = blocks[$ - 1].items.ptr; lastFree = nextFree + Block.items.length; }
return nextFree++; }
static void freeAll() nothrow { foreach (block_ptr; blocks) free(block_ptr); blocks.length = 0; nextFree = null; lastFree = null; }
}
immutable struct Board(size_t boardSize) {
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; } } if (sData.length != boardSize) exit(3); // Error in actual board size }
private static char[] myDup(in CTable table) nothrow { static MemoryPool!(char[boardSize]) boardsPool; char[boardSize]* newBoard = boardsPool.newItem(); (*newBoard)[0 .. boardSize] = table[]; return (*newBoard)[]; }
private bool move(in int x, in int y, in int dx, in int dy, ref CTable data) const nothrow { if (sData[(y+dy) * ncols + x+dx] == El.wall || data[(y+dy) * ncols + x+dx] != El.floor) return false;
auto data2 = myDup(data); 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 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 = myDup(data); 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() nothrow { 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(); enum level =
"#######
- #
- #
- . # #
- . $$ #
- .$$ #
- .# @#
- ";
enum size_t boardSize = level.splitLines().join().length; immutable b = Board!boardSize(level.splitLines()); writeln(level, "\n\n", b.solve());
}</lang> Run-time first version about 0.66 seconds with DMD compiler, second version about 0.51 seconds (C version about 0.43 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