Maze solving

Maze solving 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.

For a maze generated by this task, write a function that finds (and displays) the shortest path between two cells. Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths, and a simple depth-first tree search can be used.

PicoLisp

<lang PicoLisp>(de shortestPath (This Goal Maze)

  (let (Path NIL  Best NIL)
     (recur (This Path)
        (unless (or (flg? This) (: mark))
           (push 'Path This)
           (if (== Goal This)
              (unless (and Best (>= (length Path) (length Best)))
                 (setq Best Path) )
              (let Cell (val This)
                 (=: mark T)
                 (recurse (caar Cell) Path)
                 (recurse (cdar Cell) Path)
                 (recurse (cadr Cell) Path)
                 (recurse (cddr Cell) Path)
                 (=: mark NIL) ) ) ) )
     (disp Maze 0
        '((This) (if (memq This Best) " # " "   ")) ) ) )</lang>

Using the maze produced in Maze generation#PicoLisp, this finds the shortest path from the top-left cell 'a12' to the bottom-righ exit 'p1':

: (shortestPath 'a12 'p1 (maze 16 12))
    +   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 12 | # | #   #   # | #   #   # | #   #   #   # |         #   #   # |
    +   +   +   +   +   +---+   +   +---+---+   +   +---+   +---+   +
 11 | #   # |   | #   # |   | #   # |   | #   # |   | #   # | #   # |
    +   +---+   +---+---+   +---+---+   +   +---+---+   +---+   +---+
 10 |   |   |   |           | #   # | #   # |     #   # | #   # |   |
    +   +   +   +---+   +   +   +   +   +---+---+   +---+   +---+   +
  9 |       |       |   |   | # | #   # | #   # | # | #   # | #   # |
    +   +---+---+   +   +---+   +---+---+   +   +   +   +---+   +   +
  8 |   |       |   | #   #   # |         # | #   # | # |     # | # |
    +   +   +   +   +   +---+---+   +---+   +---+---+   +---+   +   +
  7 |   |   |       | #   #   # |       | #   # | #   # | #   # | # |
    +---+   +---+---+---+---+   +---+   +---+   +   +---+   +---+   +
  6 |   |       |           | # |       |   | # | #   #   # |   | # |
    +   +---+   +---+   +---+   +   +---+   +   +---+---+---+   +   +
  5 |       |       |     #   # |           | # |               | # |
    +---+   +---+   +---+   +---+   +---+---+   +   +---+   +---+   +
  4 |   |       |       | #   # |   | #   # | # |       |   | #   # |
    +   +---+   +---+   +---+   +---+   +   +   +---+---+   +   +---+
  3 |       |       |   |   | #   #   # | # | #   #   # |   | #   # |
    +   +---+---+   +   +   +---+---+---+   +---+   +   +   +---+   +
  2 |       |       |   |   |           | #   # |   | # | #   #   # |
    +   +   +   +---+   +   +   +---+   +---+   +---+   +   +---+---+
  1 |   |               |           |         #   #   # | #   #   #  
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
      a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   p