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.



import deques, sets, strutils
 
type
 
  Sokoban = object
    destBoard: string
    currBoard: string
    nCols: Natural
    playerX: Natural
    playerY: Natural
 
  Board = tuple[cur, sol: string; x, y: int]
 
 
func initSokoban(board: openArray[string]): Sokoban =
  result.nCols = board[0].len
  for row in 0..board.high:
    for col in 0..<result.nCols:
      let ch = board[row][col]
      result.destBoard.add if ch notin ['$', '@']: ch else: ' '
      result.currBoard.add if ch != '.': ch else: ' '
      if ch == '@':
        result.playerX = col
        result.playerY = row
 
 
func move(sokoban: Sokoban; x, y, dx, dy: int; trialBoard: string): string =
  let newPlayerPos = (y + dy) * sokoban.nCols + x + dx
  if trialBoard[newPlayerPos] != ' ': return
  result = trialBoard
  result[y * sokoban.nCols + x] = ' '
  result[newPlayerPos] = '@'
 
 
func push(sokoban: Sokoban; x, y, dx, dy: int; trialBoard: string): string =
  let newBoxPos = (y + 2 * dy) * sokoban.nCols + x + 2 * dx
  if trialBoard[newBoxPos] != ' ': return
  result = trialBoard
  result[y * sokoban.nCols + x] = ' '
  result[(y + dy) * sokoban.nCols + x + dx] = '@'
  result[newBoxPos] = '$'
 
 
func isSolved(sokoban: Sokoban; trialBoard: string): bool =
  for i in 0..trialBoard.high:
    if (sokoban.destBoard[i] == '.') != (trialBoard[i] == '$'): return false
  result = true
 
 
func solve(sokoban: Sokoban): string =
  var history: HashSet[string]
  history.incl sokoban.currBoard
  const Dirs = [(0, -1, 'u', 'U'), (1, 0, 'r', 'R'), (0, 1, 'd', 'D'), (-1, 0, 'l', 'L')]
  var open: Deque[Board]
  open.addLast (sokoban.currBoard, "", sokoban.playerX, sokoban.playerY)
 
  while open.len != 0:
    let (cur, sol, x, y) = open.popFirst()
    for dir in Dirs:
      var trial = cur
      let dx = dir[0]
      let dy = dir[1]
 
      # Are we standing next to a box?
      if trial[(y + dy) * sokoban.nCols + x + dx] == '$':
        # Can we push it?
        trial = sokoban.push(x, y, dx, dy, trial)
        if trial.len != 0:
          # Or did we already try this one?
          if trial notin history:
            let newSol = sol & dir[3]
            if sokoban.isSolved(trial): return newSol
            open.addLast (trial, newSol, x + dx, y + dy)
            history.incl trial
 
      else:
        # Try to change position.
        trial = sokoban.move(x, y, dx, dy, trial)
        if trial.len != 0 and trial notin history:
          let newSol = sol & dir[2]
          open.addLast (trial, newSol, x + dx, y + dy)
          history.incl trial
 
  result = "no solution"
 
when isMainModule:
 
  const Level = ["#######",
                "#     #",
                "#     #",
                "#. #  #",
                "#. $$ #",
                "#.$$  #",
                "#.#  @#",
                "#######"]
 
  echo Level.join("\n")
  echo()
  echo initSokoban(Level).solve()