Sokoban: Difference between revisions
m (wordliness) |
(Added second C++0x version) |
||
Line 206: | Line 206: | ||
ulULLulDDurrrddlULrruLLrrUruLLLulD |
ulULLulDDurrrddlULrruLLrrUruLLLulD |
||
</pre> |
</pre> |
||
{{works with|C++0x}} |
|||
{{works with|Boost}} |
|||
{{works with|GCC 4.6}} |
|||
Alternative version, about twice faster (about 2.1 seconds runtime), same output. |
|||
<lang c++>#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; |
|||
}</lang> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
Revision as of 22:07, 7 July 2011
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 c++>#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>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"