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.

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++

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>

1. include <string>
2. include <vector>
3. include <queue>
4. include <regex>
5. include <tuple>
6. include <set>
7. 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