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

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")

1. 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
           " " ) ) ) )

1. 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) )

1. 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" @)) ) ) ) ) )

1. 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")) ) ) ) )

1. 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"