Sokoban
Sokoban is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Demonstrate how to find a solution to a given Sokoban level. For the purpose of this task, any method may be used with the code. However a move-optimal or push-optimal (or any other -optimal) solutions may be 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++
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;
}</lang>
Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Alternative version, about twice faster (about 2.1 seconds runtime), same output. <lang cpp>#include <iostream>
- include <string>
- include <vector>
- include <queue>
- include <tuple>
- include <array>
- include <map>
- include <boost/algorithm/string.hpp>
- include <boost/unordered_set.hpp>
using namespace std;
typedef vector<char> TableRow; typedef vector<TableRow> Table;
struct Board {
Table sData, dData; int px, py;
Board(string b) {
vector<string> data;
boost::split(data, b, boost::is_any_of("\n"));
size_t width = 0;
for (auto &row: data)
width = max(width, row.size());
map<char,char> maps = {{' ',' '}, {'.','.'}, {'@',' '},
{'#','#'}, {'$',' '}},
mapd = {{' ',' '}, {'.',' '}, {'@','@'},
{'#',' '}, {'$','*'}};
for (size_t r = 0; r < data.size(); r++) {
TableRow sTemp, dTemp;
for (size_t c = 0; c < width; c++) {
char ch = c < data[r].size() ? data[r][c] : ' ';
sTemp.push_back(maps[ch]);
dTemp.push_back(mapd[ch]);
if (ch == '@') {
px = c;
py = r;
}
}
sData.push_back(sTemp);
dData.push_back(dTemp);
}
}
bool move(int x, int y, int dx, int dy, Table &data) {
if (sData[y+dy][x+dx] == '#' || data[y+dy][x+dx] != ' ')
return false;
data[y][x] = ' '; data[y+dy][x+dx] = '@'; return true; }
bool push(int x, int y, int dx, int dy, Table &data) {
if (sData[y+2*dy][x+2*dx] == '#' || data[y+2*dy][x+2*dx] != ' ')
return false;
data[y][x] = ' '; data[y+dy][x+dx] = '@'; data[y+2*dy][x+2*dx] = '*'; return true; }
bool isSolved(const Table &data) {
for (size_t r = 0; r < data.size(); r++)
for (size_t c = 0; c < data[r].size(); c++)
if ((sData[r][c] == '.') != (data[r][c] == '*'))
return false;
return true;
}
string solve() {
boost::unordered_set<Table, boost::hash
> visited; visited.insert(dData); queue<tuple<Table, string, int, int>> open; open.push(make_tuple(dData, "", px, py)); vector<tuple<int, int, char, char>> dirs = { make_tuple( 0, -1, 'u', 'U'), make_tuple( 1, 0, 'r', 'R'), make_tuple( 0, 1, 'd', 'D'), make_tuple(-1, 0, 'l', 'L') }; while (open.size() > 0) { Table temp, cur = get<0>(open.front()); string cSol = get<1>(open.front()); int x = get<2>(open.front()); int y = get<3>(open.front()); open.pop(); for (int i = 0; i < 4; ++i) { temp = cur; int dx = get<0>(dirs[i]); int dy = get<1>(dirs[i]); if (temp[y+dy][x+dx] == '*') { if (push(x, y, dx, dy, temp) && visited.find(temp) == visited.end()) { if (isSolved(temp)) return cSol + get<3>(dirs[i]); open.push(make_tuple(temp, cSol + get<3>(dirs[i]), x+dx, y+dy)); visited.insert(temp); } } else if (move(x, y, dx, dy, temp) && visited.find(temp) == visited.end()) { if (isSolved(temp)) return cSol + get<2>(dirs[i]); open.push(make_tuple(temp, cSol + get<2>(dirs[i]), x+dx, y+dy)); visited.insert(temp); } } } return "No solution"; } }; int main() { string level = "#######\n" "# #\n" "# #\n" "#. # #\n" "#. $$ #\n" "#.$$ #\n" "#.# @#\n" "#######"; cout << level << endl << endl; Board board(level); cout << board.solve() << endl; }</lang>D
<lang d>import std.stdio, std.typecons, std.string, std.algorithm,
std.array;
// To be removed when Phobos has a queue. final class GrowableCircularQueue(T) {
private size_t length; private size_t head, tail; private T[] A;
this() {
A.length = 1;
}
void push(T item) {
if (length >= A.length) { // double the queue
auto 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() {
if (length == 0)
throw new Exception("CircularQueue is empty");
auto oldHead = head;
head = (head + 1) % A.length;
length--;
return A[oldHead];
}
}
alias char[][] CTable;
string tableStr(CTable table) { // str.string.join
auto result = new char[table.length * table[0].length];
int pos = 0;
foreach (row; table)
foreach (ch; row)
result[pos++] = ch;
return cast(string)result;
}
CTable tableDup(CTable table) {
return array(map!q{ a.dup }(table));
}
struct Board {
CTable sData, dData; int px, py;
this(string board) {
auto data = array(filter!q{ a.length }(board.splitLines()));
size_t width = reduce!max(map!q{ a.length }(data));
sData = new CTable(data.length, width);
dData = new CTable(data.length, width);
auto maps = [' ':' ', '.': '.', '@':' ', '#':'#', '$':' '];
auto mapd = [' ':' ', '.': ' ', '@':'@', '#':' ', '$':'*'];
foreach (r, row; data)
foreach (c, ch; row) {
sData[r][c] = maps[ch];
dData[r][c] = mapd[ch];
if (ch == '@') {
px = c;
py = r;
}
}
}
bool move(int x, int y, int dx, int dy, CTable 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, CTable 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(CTable data) {
foreach (r; 0 .. data.length)
foreach (c; 0 .. data[r].length)
if ((sData[r][c] == '.') != (data[r][c] == '*'))
return false;
return true;
}
string solve() {
bool[string] visited; // A set
visited[tableStr(dData)] = true;
auto open = new GrowableCircularQueue!(
Tuple!(CTable, string, int, int));
open.push(tuple(tableDup(dData), "", px, py));
const Tuple!(int, int, char, char)[4] dirs = [
tuple( 0, -1, 'u', 'U'),
tuple( 1, 0, 'r', 'R'),
tuple( 0, 1, 'd', 'D'),
tuple(-1, 0, 'l', 'L')];
while (open.length) {
auto item = open.pop();
CTable cur = item[0];
string cSol = item[1];
int x = item[2];
int y = item[3];
foreach (i; 0 .. 4) {
auto temp = tableDup(cur);
int dx = dirs[i][0];
int dy = dirs[i][1];
if (temp[y+dy][x+dx] == '*') {
if (push(x, y, dx, dy, temp) &&
tableStr(temp) !in visited) {
if (isSolved(temp))
return cSol ~ dirs[i][3];
open.push(tuple(tableDup(temp),
cSol ~ dirs[i][3], x+dx, y+dy));
visited[tableStr(temp)] = true;
}
} else if (move(x, y, dx, dy, temp) &&
tableStr(temp) !in visited) {
if (isSolved(temp))
return cSol ~ dirs[i][2];
open.push(tuple(tableDup(temp),
cSol ~ dirs[i][2], x+dx, y+dy));
visited[tableStr(temp)] = true;
}
}
}
return "No solution"; }
}
void main() {
string level =
"#######
- #
- #
- . # #
- . $$ #
- .$$ #
- .# @#
- ";
auto b = Board(level); writeln(level, "\n\n", b.solve());
}</lang> Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Runtime: about 3.2 seconds.
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
def tab_to_str(tab):
return "".join(arr.tostring() for arr in tab)
def copy_tab(tab):
return [arr.__copy__() for arr in tab]
class Board(object):
def __init__(self, board):
data = filter(None, board.splitlines())
width = max(len(r) for r in data)
xld = xrange(len(data))
self.sdata = [array("c", " ") * width for _ in xld]
self.ddata = [array("c", " ") * width for _ in xld]
maps = {' ':' ', '.': '.', '@':' ', '#':'#', '$':' '}
mapd = {' ':' ', '.': ' ', '@':'@', '#':' ', '$':'*'}
for r, row in enumerate(data):
for c, ch in enumerate(row):
self.sdata[r][c] = maps[ch]
self.ddata[r][c] = mapd[ch]
if ch == '@':
self.px = c
self.py = r
def move(self, x, y, dx, dy, data):
if self.sdata[y+dy][x+dx] == '#' or data[y+dy][x+dx] != ' ':
return False
data[y][x] = ' '
data[y+dy][x+dx] = '@'
return True
def push(self, x, y, dx, dy, data):
if self.sdata[y+2*dy][x+2*dx] == '#' or \
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
def is_solved(self, data):
for v in xrange(len(data)):
for u in xrange(len(data[v])):
if (self.sdata[v][u] == '.') != (data[v][u] == '*'):
return False
return True
def solve(self):
visited = set()
open = deque()
open.append((copy_tab(self.ddata), "", self.px, self.py))
visited.add(tab_to_str(self.ddata))
dirs = ((0, -1, 'u', 'U'), ( 1, 0, 'r', 'R'),
(0, 1, 'd', 'D'), (-1, 0, 'l', 'L'))
while open:
cur, csol, x, y = open.popleft()
for i in xrange(4):
temp = copy_tab(cur)
dx, dy = dirs[i][0], dirs[i][1]
if temp[y+dy][x+dx] == '*':
if self.push(x, y, dx, dy, temp) and \
tab_to_str(temp) not in visited:
if self.is_solved(temp):
return csol + dirs[i][3]
open.append((copy_tab(temp),
csol + dirs[i][3], x+dx, y+dy))
visited.add(tab_to_str(temp))
elif self.move(x, y, dx, dy, temp) and \
tab_to_str(temp) not in visited:
if self.is_solved(temp):
return csol + dirs[i][2]
open.append((copy_tab(temp),
csol + dirs[i][2], x+dx, y+dy))
visited.add(tab_to_str(temp))
return "No solution"
level = """\
- #
- #
- . # #
- . $$ #
- .$$ #
- .# @#
- """
psyco.full() print level, "\n" b = Board(level) print b.solve()</lang> Output:
####### # # # # #. # # #. $$ # #.$$ # #.# @# ####### ulULLulDDurrrddlULrruLLrrUruLLLulD
Runtime: about 8.9 seconds.