Sokoban: Difference between revisions
m (Don't need both commas and parentheses) |
No edit summary |
||
Line 17: | Line 17: | ||
For more information, see [http://www.sokobano.de/wiki/index.php?title=Main_Page the Sokoban wiki]. |
For more information, see [http://www.sokobano.de/wiki/index.php?title=Main_Page the Sokoban wiki]. |
||
=={{header|C++}}== |
|||
{{works with|C++0x}} |
|||
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> |
Revision as of 08:29, 29 May 2011
Find a solution to a given Sokoban level. While move-optimal or push-optimal (or any other -optimal) solutions are better, this task only requires finding a solution.
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>