Demonstrate how to find a solution to a given Sokoban level. For the purpose of this task (formally, a PSPACE-complete problem) any method may be used. However a move-optimal or push-optimal (or any other -optimal) solutions is 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.



[String] data
V nrows = 0
V px = 0
V py = 0
V sdata = ‘’
V ddata = ‘’
 
F init(board)
   :data = board.split("\n")
   :nrows = max(:data.map(r -> r.len))
 
   V maps = [‘ ’ = ‘ ’, ‘.’ = ‘.’, ‘@’ = ‘ ’, ‘#’ = ‘#’, ‘$’ = ‘ ’]
   V mapd = [‘ ’ = ‘ ’, ‘.’ = ‘ ’, ‘@’ = ‘@’, ‘#’ = ‘ ’, ‘$’ = ‘*’]
 
   L(row) :data
      V r = L.index
      L(ch) row
         V c = L.index
         :sdata ‘’= maps[ch]
         :ddata ‘’= mapd[ch]
         I ch == ‘@’
            :px = c
            :py = r
 
F push(x, y, dx, dy, &data)
   I :sdata[(y + 2 * dy) * :nrows + x + 2 * dx] == ‘#’
     | data[(y + 2 * dy) * :nrows + x + 2 * dx] != ‘ ’
      data = ‘’
      R
 
   data[y * :nrows + x] = ‘ ’
   data[(y + dy) * :nrows + x + dx] = ‘@’
   data[(y + 2 * dy) * :nrows + x + 2 * dx] = ‘*’
 
F is_solved(data)
   L(i) 0 .< data.len
      I (:sdata[i] == ‘.’) != (data[i] == ‘*’)
         R 0B
   R 1B
 
F solve()
   V open = Deque([(:ddata, ‘’, :px, :py)])
   V visited = Set([:ddata])
   V dirs = ((0, -1, ‘u’, ‘U’), ( 1, 0, ‘r’, ‘R’),
             (0,  1, ‘d’, ‘D’), (-1, 0, ‘l’, ‘L’))
 
   L !open.empty
      V (cur, csol, x, y) = open.pop_left()
 
      L(di) dirs
         V temp = copy(cur)
         V (dx, dy) = (di[0], di[1])
 
         I temp[(y + dy) * :nrows + x + dx] == ‘*’
            push(x, y, dx, dy, &temp)
            I temp != ‘’ & temp !C visited
               I is_solved(temp)
                  R csol‘’di[3]
               open.append((temp, csol‘’di[3], x + dx, y + dy))
               visited.add(temp)
         E
            I :sdata[(y + dy) * :nrows + x + dx] == ‘#’ | temp[(y + dy) * :nrows + x + dx] != ‘ ’
               L.continue
 
            temp[y * :nrows + x] = ‘ ’
            temp[(y + dy) * :nrows + x + dx] = ‘@’
 
            I temp !C visited
               I is_solved(temp)
                  R csol‘’di[2]
               open.append((temp, csol‘’di[2], x + dx, y + dy))
               visited.add(temp)
 
   R ‘No solution’
 
V level =
|‘#######
  #     #
  #     #
  #. #  #
  #. $$ #
  #.$$  #
  #.#  @#
  #######’
 
init(level)
print(level"\n\n"solve())