Maze solving: Difference between revisions

Content added Content deleted

Inline

Revision as of 21:39, 6 March 2013

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.

Ada

The maze is read from the standard input. The size of the maze is hardwired into the program (see the constants X_Size and Y_Size).

<lang Ada>with Ada.Text_IO;

procedure Maze_Solver is

  X_Size: constant Natural := 45;
  Y_Size: constant Natural := 17;

  subtype X_Range is Natural range 1 .. X_Size;
  subtype Y_Range is Natural range 1 .. Y_Size;

  East:  constant X_Range := 2;
  South: constant Y_Range := 1;

  X_Start: constant X_Range  := 3; -- start at the upper left
  Y_Start: constant Y_Range  := 1;
  X_Finish: constant X_Range := X_Size-East; -- go to the lower right
  Y_Finish: constant Y_Range := Y_Size;

  type Maze_Type is array (Y_Range) of String(X_Range);

  function Solved(X: X_Range; Y: Y_Range) return Boolean is
  begin
     return (X = X_Finish) and (Y = Y_Finish);
  end Solved;

  procedure Output_Maze(M: Maze_Type; Message: String := "") is
  begin
     if Message /= "" then
        Ada.Text_IO.Put_Line(Message);
     end if;
     for I in M'Range loop
        Ada.Text_IO.Put_Line(M(I));
     end loop;
  end Output_Maze;

  procedure Search(M: in out Maze_Type; X: X_Range; Y:Y_Range) is
  begin
     M(Y)(X) := '*';
     if Solved(X, Y) then
        Output_Maze(M, "Solution found!");
     else
        if Integer(Y)-South >= 1 and then M(Y-South)(X) = ' ' then
           Search(M, X, Y-South);
        end if;
        if Integer(Y)+South <= Y_Size and then M(Y+South)(X) = ' ' then
           Search(M, X, Y+South);
        end if;
        if Integer(X)-East >= 1 and then M(Y)(X-East) = ' ' then
           Search(M, X-East, Y);
        end if;
        if Integer(Y)+East <= Y_Size and then M(Y)(X+East) = ' ' then
           Search(M, X+East, Y);
        end if;
     end if;
     M(Y)(X) := ' ';
  end Search;

  Maze: Maze_Type;
  X: X_Range := X_Start;
  Y: Y_Range := Y_Start;

begin

  for I in 1 .. Y_Size loop
     Maze(I) := Ada.Text_IO.Get_Line;
  end loop;
  Maze(Y_Start)(X_Start)   := ' '; -- Start from
  Maze(Y_Finish)(X_Finish) := ' '; -- Go_To
  Output_Maze(Maze, "The Maze:");
  Ada.Text_IO.New_Line;

  Search(Maze, X, Y) ; -- Will output *all* Solutions.
                       -- If there is no output, there is no solution.

end Maze_Solver;</lang>

Example output (using a maze generated by the Ada implementation of the maze generation task as the input):

> ./maze_solver < maze.txt 
The Maze:
+- -+---+---+---+---+---+---+---+---+---+---+
|                                       |   |
+   +   +---+---+---+---+---+---+---+   +   +
|   |           |       |               |   |
+   +---+---+   +---+   +   +---+---+---+   +
|   |           |       |   |   |           |
+---+   +---+---+   +---+   +   +   +---+   +
|       |           |       |   |   |       |
+   +---+   +---+---+   +---+   +   +   +---+
|       |   |           |           |       |
+---+---+   +   +---+---+---+---+   +---+   +
|           |       |           |       |   |
+   +   +---+---+   +---+   +   +---+---+   +
|   |           |           |               |
+   +---+   +---+---+---+---+---+---+---+   +
|       |                                   |
+---+---+---+---+---+---+---+---+---+---+- -+

Solution found!
+-*-+---+---+---+---+---+---+---+---+---+---+
| * * * * * * * * * * * * * * * * * * * |   |
+   +   +---+---+---+---+---+---+---+ * +   +
|   |           |       | * * * * * * * |   |
+   +---+---+   +---+   + * +---+---+---+   +
|   |           |       | * |   |           |
+---+   +---+---+   +---+ * +   +   +---+   +
|       |           | * * * |   |   |       |
+   +---+   +---+---+ * +---+   +   +   +---+
|       |   | * * * * * |           |       |
+---+---+   + * +---+---+---+---+   +---+   +
|           | * * * |     * * * |       |   |
+   +   +---+---+ * +---+ * + * +---+---+   +
|   |           | * * * * * | * * * * * * * |
+   +---+   +---+---+---+---+---+---+---+ * +
|       |                                 * |
+---+---+---+---+---+---+---+---+---+---+-*-+

BBC BASIC

Works with: BBC BASIC for Windows

Maze generation code also included. <lang bbcbasic> MazeWidth% = 11

     MazeHeight% = 9
     MazeCell% = 50
     
     VDU 23,22,MazeWidth%*MazeCell%/2+3;MazeHeight%*MazeCell%/2+3;8,16,16,128
     VDU 23,23,3;0;0;0; : REM Line thickness
     OFF
     PROCgeneratemaze(Maze&(), MazeWidth%, MazeHeight%, MazeCell%)
     PROCsolvemaze(Path{()}, Maze&(), 0, MazeHeight%-1, MazeWidth%-1, 0, MazeCell%)
     END
     
     DEF PROCsolvemaze(RETURN s{()}, m&(), x%, y%, dstx%, dsty%, s%)
     LOCAL h%, i%, n%, p%, q%, w%
     w% = DIM(m&(),1)
     h% = DIM(m&(),2)
     DIM s{(w%*h%) x%,y%}
     GCOL 3,14
     m&(x%,y%) OR= &80
     REPEAT
       FOR i% = 0 TO 3
         CASE i% OF
           WHEN 0: p% = x%-1 : q% = y%
           WHEN 1: p% = x%+1 : q% = y%
           WHEN 2: p% = x% : q% = y%-1
           WHEN 3: p% = x% : q% = y%+1
         ENDCASE
         IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &80 THEN
           IF p% > x% IF m&(p%,q%) AND 1 EXIT FOR
           IF q% > y% IF m&(p%,q%) AND 2 EXIT FOR
           IF x% > p% IF m&(x%,y%) AND 1 EXIT FOR
           IF y% > q% IF m&(x%,y%) AND 2 EXIT FOR
         ENDIF
       NEXT
       IF i% < 4 THEN
         m&(p%,q%) OR= &80
         s{(n%)}.x% = x%
         s{(n%)}.y% = y%
         n% += 1
       ELSE
         IF n% > 0 THEN
           n% -= 1
           p% = s{(n%)}.x%
           q% = s{(n%)}.y%
         ENDIF
       ENDIF
       LINE (x%+0.5)*s%,(y%+0.5)*s%,(p%+0.5)*s%,(q%+0.5)*s%
       x% = p%
       y% = q%
     UNTIL x%=dstx% AND y%=dsty%
     s{(n%)}.x% = x%
     s{(n%)}.y% = y%
     ENDPROC
     
     DEF PROCgeneratemaze(RETURN m&(), w%, h%, s%)
     LOCAL x%, y%
     DIM m&(w%, h%)
     FOR y% = 0 TO h%
       LINE 0,y%*s%,w%*s%,y%*s%
     NEXT
     FOR x% = 0 TO w%
       LINE x%*s%,0,x%*s%,h%*s%
     NEXT
     GCOL 15
     PROCcell(m&(), RND(w%)-1, y% = RND(h%)-1, w%, h%, s%)
     ENDPROC
     
     DEF PROCcell(m&(), x%, y%, w%, h%, s%)
     LOCAL i%, p%, q%, r%
     m&(x%,y%) OR= &40 : REM Mark visited
     r% = RND(4)
     FOR i% = r% TO r%+3
       CASE i% MOD 4 OF
         WHEN 0: p% = x%-1 : q% = y%
         WHEN 1: p% = x%+1 : q% = y%
         WHEN 2: p% = x% : q% = y%-1
         WHEN 3: p% = x% : q% = y%+1
       ENDCASE
       IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &40 THEN
         IF p% > x% m&(p%,q%) OR= 1 : LINE p%*s%,y%*s%+4,p%*s%,(y%+1)*s%-4
         IF q% > y% m&(p%,q%) OR= 2 : LINE x%*s%+4,q%*s%,(x%+1)*s%-4,q%*s%
         IF x% > p% m&(x%,y%) OR= 1 : LINE x%*s%,y%*s%+4,x%*s%,(y%+1)*s%-4
         IF y% > q% m&(x%,y%) OR= 2 : LINE x%*s%+4,y%*s%,(x%+1)*s%-4,y%*s%
         PROCcell(m&(), p%, q%, w%, h%, s%)
       ENDIF
     NEXT
     ENDPROC</lang>

C

See Maze generation for combined gen/solve code.

D

This entry reads a maze generated by http://rosettacode.org/wiki/Maze_generation#D and chooses two random start-end points. <lang d>import std.stdio, std.random, std.string, std.array, std.algorithm,

      std.traits;

enum int cx = 4; // Cell size x. enum int cy = 2; // Cell size y. enum int cx2 = cx / 2; enum int cy2 = cy / 2; enum char pathSymbol = '.'; struct V2 { int x, y; }

bool solveMaze(char[][] maze, in V2 s, in V2 end) pure nothrow {

   if (s == end)
       return true;

   foreach (d; [V2(0, -cy), V2(+cx, 0), V2(0, +cy), V2(-cx, 0)])
       if (maze[s.y + (d.y / 2)][s.x + (d.x / 2)] == ' ' &&
           maze[s.y + d.y][s.x + d.x] == ' ') {
           maze[s.y + d.y][s.x + d.x] = pathSymbol;
           if (solveMaze(maze, V2(s.x + d.x, s.y + d.y), end))
               return true;
           maze[s.y + d.y][s.x + d.x] = ' ';
       }

   return false;

}

void main() {

   auto maze = File("maze.txt")
               .byLine()
               .map!(r => r.strip().dup)()
               .filter!(r => !r.empty)()
               .array();

   immutable int h = (maze.length - 1) / cy;
   assert (h > 0);
   immutable int w = (maze[0].length - 1) / cx;

   immutable start = V2(cx2 + cx * uniform(0, w),
                        cy2 + cy * uniform(0, h));
   immutable end = V2(cx2 + cx * uniform(0, w),
                      cy2 + cy * uniform(0, h));

   maze[start.y][start.x] = pathSymbol;
   if (solveMaze(maze, start, end)) {
       maze[start.y][start.x] = 'S';
       maze[end.y][end.x] = 'E';
       writefln("%-(%s\n%)", maze);
   } else
       writeln("No solution path found.");

}</lang>

Output:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |               |           | . . . . . . . . .     |
+   +   +---+---+   +   +---+   + . +---+---+---+ . +   +
|               |           |   | . . . |       | . |   |
+---+---+---+---+---+---+---+   +---+ . +---+   + . +---+
|                   |       |       | . . . . . | E     |
+   +---+---+---+   +   +   +---+   +---+---+ . +---+---+
|       | . . . |   |   |               |   | . . . |   |
+---+   + . + . +   +   +---+---+---+   +   +---+ . +   +
|       | . | . |       | . . . |           | . . . |   |
+   +---+ . + . +---+---+ . + . +---+---+---+ . +---+   +
| . . . . . | . | . . . . . | . . . . . . . | . . . . . |
+ . +---+---+ . + . +---+---+---+---+---+ . +---+---+ . +
| . . . |   | . . . |   |               | .         | . |
+---+ . +   +---+---+   +   +---+   +   + . +---+---+ . +
|   | . . . . . . . |       |       |   | . | . . . . . |
+   +---+---+---+ . +   +---+   +---+   + . + . +---+---+
|   | . . . . . . . |   |       |   |   | . . . |       |
+   + . +---+---+---+---+   +---+   +   +---+---+   +   +
|     . . . . . . S         |                       |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

EGL

<lang EGL>program MazeGenAndSolve

   // First and last columns/rows are "dead" cells. Makes generating
   // a maze with border walls much easier. Therefore, a visible
   // 20x20 maze has a maze size of 22. 	
   mazeSize int = 22;

   south boolean[][];
   west boolean[][];
   visited boolean[][];

   // Solution variables
   solution Dictionary;
   done boolean;
   startingRow, startingCol, endingRow, endingCol int;

   function main()
       initMaze();
       generateMaze();
       drawMaze(false); // Draw maze without solution

       solveMaze();
       drawMaze(true); // Draw maze with solution
   end

   private function initMaze()

       visited = createBooleanArray(mazeSize, mazeSize, false);

       // Initialize border cells as already visited
       for(col int from 1 to mazeSize)
           visited[col][1] = true;
           visited[col][mazeSize] = true;
       end
       for(row int from 1 to mazeSize)
           visited[1][row] = true;
           visited[mazeSize][row] = true;
       end

       // Initialize all walls as present
       south = createBooleanArray(mazeSize, mazeSize, true);
       west = createBooleanArray(mazeSize, mazeSize, true);
   
   end

   private function createBooleanArray(col int in, row int in, initialState boolean in) returns(boolean[][])

       newArray boolean[][] = new boolean[0][0];

       for(i int from 1 to col)
           innerArray boolean[] = new boolean[0];
           for(j int from 1 to row)
               innerArray.appendElement(initialState);
           end
           newArray.appendElement(innerArray);
       end

       return(newArray);

end

   private function createIntegerArray(col int in, row int in, initialValue int in) returns(int[][])

       newArray int[][] = new int[0][0];

       for(i int from 1 to col)
           innerArray int[] = new int[0];
           for(j int from 1 to row)
               innerArray.appendElement(initialValue);
           end
           newArray.appendElement(innerArray);
       end

       return(newArray);

end

   private function generate(col int in, row int in)

// Mark cell as visited

       visited[col][row] = true;

       // Keep going as long as there is an unvisited neighbor
       while(!visited[col][row + 1] || !visited[col + 1][row] ||
               !visited[col][row - 1] || !visited[col - 1][row])

           while(true)
               r float = MathLib.random(); // Choose a random direction
               
               case
                   when(r < 0.25 && !visited[col][row + 1]) // Go south
                       south[col][row] = false; // South wall down
                       generate(col, row + 1);
                       exit while;
                   when(r >= 0.25 && r < 0.50 && !visited[col + 1][row]) // Go east 
                       west[col + 1][row] = false; // West wall of neighbor to the east down
                       generate(col + 1, row);
                       exit while;
                   when(r >= 0.5 && r < 0.75 && !visited[col][row - 1]) // Go north
                       south[col][row - 1] = false; // South wall of neighbor to the north down
                       generate(col, row - 1);
                       exit while;
                   when(r >= 0.75 && r < 1.00 && !visited[col - 1][row]) // Go west
                       west[col][row] = false; // West wall down
                       generate(col - 1, row);
                       exit while;
               end
           end
       end

end

   private function generateMaze()

   	// Pick random start position (within the visible maze space)
       randomStartCol int = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2);
       randomStartRow int = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2);

       generate(randomStartCol, randomStartRow);

end

   private function drawMaze(solve boolean in)

       line string;

       // Iterate over wall arrays (skipping dead border cells as required). 
       // Construct a row at a time and output to console.
       for(row int from 1 to mazeSize - 1)

           if(row > 1)
               line = "";
               for(col int from 2 to mazeSize)
                   if(west[col][row])
                       line ::= cellTest(col, row, solve);
                   else
                       line ::= cellTest(col, row, solve);
                   end
               end
               Syslib.writeStdout(line);
           end

           line = "";
           for(col int from 2 to mazeSize - 1)
               if(south[col][row])
                   line ::= "+---";
               else
                   line ::= "+   ";
               end
           end
           line ::= "+";
           SysLib.writeStdout(line);

end

end

   private function cellTest(col int in, row int in, solve boolean in) returns(string)

       wall string;

       // Determine cell wall structure. If in solve mode, show start, end and
       // solution markers.
       if(!solve)
           if(west[col][row])
               wall = "|   ";
           else
               wall = "    ";
           end
       else
           if(west[col][row])

               case
                   when(col == startingCol and row == startingRow)
                       wall = "| S ";
                   when(col == endingCol and row == endingRow)
                       wall = "| E ";
                   when(solution.containsKey("x=" + col + "y=" + row))
                       wall = "| * ";
                   otherwise
                       wall = "|   ";
               end

           else
               case
                   when(col == startingCol and row == startingRow)
                       wall = "  S ";
                   when(col == endingCol and row == endingRow)
                       wall = "  E ";
                   when(solution.containsKey("x=" + col + "y=" + row))
                       wall = "  * ";
                   otherwise
                       wall = "    ";
               end
           end
       end

       return(wall);
   end

   private function solve(col int in, row int in)

       if(col == 1 || row == 1 || col == mazeSize || row == mazeSize)
           return;
       end

       if(done || visited[col][row])
           return;
       end

       visited[col][row] = true;

       solution["x=" + col + "y=" + row] = true;

       // Reached the end point
       if(col == endingCol && row == endingRow)
           done = true;
       end

       if(!south[col][row]) // Go South
           solve(col, row + 1);
       end
       if(!west[col + 1][row]) // Go East
           solve(col + 1, row);
       end
       if(!south[col][row - 1]) // Go North
           solve(col, row - 1);
       end
       if(!west[col][row]) // Go West
           solve(col - 1, row);
       end

       if(done)
           return;
       end

       solution.removeElement("x=" + col + "y=" + row);

end

   private function solveMaze()
       for(col int from 1 to mazeSize)
           for(row int from 1 to mazeSize)
               visited[col][row] = false;
           end
       end

       solution = new Dictionary(false, OrderingKind.byInsertion);
       done = false;

       // Pick random start position on first visible row
       startingCol = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2);
       startingRow = 2;

       // Pick random end position on last visible row
       endingCol = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2);
       endingRow = mazeSize - 1;

       solve(startingCol, startingRow);
   end

end</lang>

Output example (for 10x10 maze):

+---+---+---+---+---+---+---+---+---+---+
|       |               |       |       |   
+   +---+   +---+---+   +   +   +---+   +
|       |   |       |       |   |   |   |   
+---+   +   +---+   +---+---+   +   +   +
|       |       |       |   |       |   |   
+   +---+---+   +   +   +   +---+---+   +
|   |       |   |   |               |   |   
+   +   +   +   +   +---+---+---+   +   +
|       |       |   |       |       |   |   
+   +---+---+---+   +   +---+   +---+   +
|       |           |   |       |       |   
+---+   +---+   +---+   +   +---+   +   +
|   |   |       |           |       |   |   
+   +   +   +---+   +---+---+---+---+   +
|   |   |   |   |                   |   |   
+   +   +   +   +---+---+---+---+   +   +
|   |   |   |           |       |   |   |   
+   +   +   +   +---+---+   +   +   +   +
|           |               |           |   
+---+---+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+---+---+
|       | *   *   S     |       |       |   
+   +---+   +---+---+   +   +   +---+   +
|       | * |       |       |   |   |   |   
+---+   +   +---+   +---+---+   +   +   +
|       | *   * | *   * |   |       |   |   
+   +---+---+   +   +   +   +---+---+   +
|   | *   * | * | * | *   *   *   * |   |   
+   +   +   +   +   +---+---+---+   +   +
| *   * | *   * | * |       | *   * |   |   
+   +---+---+---+   +   +---+   +---+   +
| *   * |     *   * |   | *   * |       |   
+---+   +---+   +---+   +   +---+   +   +
|   | * | *   * | *   *   * |       |   |   
+   +   +   +---+   +---+---+---+---+   +
|   | * | * |   | *   *   *   *   * |   |   
+   +   +   +   +---+---+---+---+   +   +
|   | * | * |           | *   * | * |   |   
+   +   +   +   +---+---+   +   +   +   +
|     *   * |             E | *   *     |   
+---+---+---+---+---+---+---+---+---+---+

Frege

Translation of: Haskell

Works with: Frege version 3.20.113

On standard input, takes a maze made up of "+", "|", and "---" (i. e. each cell is two lines high and four characters wide), such as produced by the Haskell or Java generators.

<lang frege>module MazeSolver where

import frege.IO import Data.Maybe

-- given two points, returns the average of them average :: (Int, Int) -> (Int, Int) -> (Int, Int) average (x, y) (x', y') = ((x + x') `div` 2, (y + y') `div` 2)

-- given a maze and a tuple of position and wall position, returns -- true if the wall position is not blocked (first position is unused) notBlocked :: [String] -> ((Int, Int), (Int, Int)) -> Bool notBlocked maze (_, (x, y)) = (' ' == String.charAt (maze !! y) x)

-- given a list, a position, and an element, returns a new list -- with the new element substituted at the position substitute :: [a] -> Int -> a -> [a] substitute orig pos el =

 let (before, after) = splitAt pos orig
 in before ++ [el] ++ tail after

-- like above, but for strings, since Frege strings are not -- lists of characters substituteString :: String -> Int -> String -> String substituteString orig pos el =

 let before = substr orig 0 pos
     after = strtail orig (pos + 1)
 in before ++ el ++ after

-- given a maze and a position, draw a '*' at that position in the maze draw :: [String] -> (Int, Int) -> [String] draw maze (x,y) = substitute maze y $ substituteString row x "*"

 where row = maze !! y

-- given a maze, a previous position, and a list of tuples of potential -- new positions and their wall positions, returns the solved maze, or -- None if it cannot be solved tryMoves :: [String] -> (Int, Int) -> [((Int, Int), (Int, Int))] -> Maybe [String] tryMoves _ _ [] = Nothing tryMoves maze prevPos ((newPos,wallPos):more) =

 case solve' maze newPos prevPos
      of Nothing -> tryMoves maze prevPos more
         Just maze' -> Just $ foldl draw maze' [newPos, wallPos]

-- given a maze, a new position, and a previous position, returns -- the solved maze, or None if it cannot be solved -- (assumes goal is upper-left corner of maze) solve' :: [String] -> (Int, Int) -> (Int, Int) -> Maybe [String] solve' maze (2, 1) _ = Just maze solve' maze (x, y) prevPos =

 let newPositions = [(x, y - 2), (x + 4, y), (x, y + 2), (x - 4, y)]
     notPrev pos' = pos' /= prevPos
     newPositions' = filter notPrev newPositions
     wallPositions = map (average (x,y)) newPositions'
     zipped = zip newPositions' wallPositions
     legalMoves = filter (notBlocked maze) zipped
 in tryMoves maze (x,y) legalMoves

-- given a maze, returns a solved maze, or None if it cannot be solved -- (starts at lower right corner and goes to upper left corner) solve :: [String] -> Maybe [String] solve maze = solve' (draw maze start) start (-1, -1)

 where startx = (length $ head maze) - 3
       starty = (length maze) - 2
       start = (startx, starty)

-- takes unsolved maze on standard input, prints solved maze on standard output main _ = do

 isin  <- stdin
 isrin <- InputStreamReader.new isin
 brin  <- BufferedReader.fromISR isrin
 lns <- BufferedReader.getlines brin
 printStr $ unlines $ fromMaybe ["can't solve"] $ solve lns</lang>

Output:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| * |         * * * * * |       |       |                   |       |       |
+ * +---+---+ * +---+ * +---+   +   +   +   +---+---+---+   +   +   +   +   +
| * | * * * * * |   | * |       |   |       | * * * * * |       |       |   |
+ * + * +---+---+   + * +   +---+   +---+---+ * +---+ * +   +---+---+---+   +
| * * * |       |   | * |   |       | * * * * * | * * * |   | * * * * * |   |
+---+---+   +   +   + * +   +   +---+ * +---+---+ * +---+---+ * +---+ * +   +
|           |       | * |       |   | * |   | * * * | * * * * * | * * * |   |
+   +   +---+---+---+ * +   +---+   + * +   + * +---+ * +---+---+ * +---+   +
|   |   | * * * * * * * |           | * |     * * * * * |       | * * * * * |
+   +   + * +---+---+---+---+---+---+ * +---+---+---+---+   +   +---+---+ * +
|   |   | * * * | * * * * * | * * * | * * * | * * * |       |           | * |
+   +---+---+ * + * +---+ * + * + * +---+ * + * + * +---+   +---+   +   + * +
|   |       | * | * | * * * | * | * * * | * * * | * * * |   |   |   |   | * |
+   +   +   + * + * + * +---+ * +---+ * +---+---+---+ * +   +   +   +---+ * +
|       |     * * * | * * * * * |     * * * * * * * * * |       |         * |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
runtime 0.249 wallclock seconds.

Go

Generates maze, picks start and finish cells randomly, solves, prints. <lang go>package main

import (

   "bytes"
   "fmt" 
   "math/rand"
   "time"

)

type maze struct {

   c2 [][]byte // cells by row
   h2 [][]byte // horizontal walls by row (ignore first row)
   v2 [][]byte // vertical walls by row (ignore first of each column)

}

func newMaze(rows, cols int) *maze {

   c := make([]byte, rows*cols)              // all cells
   h := bytes.Repeat([]byte{'-'}, rows*cols) // all horizontal walls
   v := bytes.Repeat([]byte{'|'}, rows*cols) // all vertical walls
   c2 := make([][]byte, rows)                // cells by row
   h2 := make([][]byte, rows)                // horizontal walls by row
   v2 := make([][]byte, rows)                // vertical walls by row
   for i := range h2 {
       c2[i] = c[i*cols : (i+1)*cols]
       h2[i] = h[i*cols : (i+1)*cols]
       v2[i] = v[i*cols : (i+1)*cols]
   }
   return &maze{c2, h2, v2}

}

func (m *maze) String() string {

   hWall := []byte("+---")
   hOpen := []byte("+   ")
   vWall := []byte("|   ")
   vOpen := []byte("    ")
   rightCorner := []byte("+\n")
   rightWall := []byte("|\n")
   var b []byte
   for r, hw := range m.h2 {
       for _, h := range hw {
           if h == '-' || r == 0 {
               b = append(b, hWall...)
           } else {
               b = append(b, hOpen...)
               if h != '-' && h != 0 {
                   b[len(b)-2] = h
               }
           }
       }
       b = append(b, rightCorner...)
       for c, vw := range m.v2[r] {
           if vw == '|' || c == 0 {
               b = append(b, vWall...)
           } else {
               b = append(b, vOpen...)
               if vw != '|' && vw != 0 {
                   b[len(b)-4] = vw
               }
           }
           if m.c2[r][c] != 0 {
               b[len(b)-2] = m.c2[r][c]
           }
       }
       b = append(b, rightWall...)
   }
   for _ = range m.h2[0] {
       b = append(b, hWall...)
   }
   b = append(b, rightCorner...)
   return string(b)

}

func (m *maze) gen() {

   m.g2(rand.Intn(len(m.c2)), rand.Intn(len(m.c2[0])))

}

const (

   up = iota
   dn
   rt
   lf

)

func (m *maze) g2(r, c int) {

   m.c2[r][c] = ' '
   for _, dir := range rand.Perm(4) {
       switch dir {
       case up:
           if r > 0 && m.c2[r-1][c] == 0 {
               m.h2[r][c] = 0
               m.g2(r-1, c)
           }
       case lf:
           if c > 0 && m.c2[r][c-1] == 0 {
               m.v2[r][c] = 0
               m.g2(r, c-1)
           }
       case dn:
           if r < len(m.c2)-1 && m.c2[r+1][c] == 0 {
               m.h2[r+1][c] = 0
               m.g2(r+1, c)
           }
       case rt:
           if c < len(m.c2[0])-1 && m.c2[r][c+1] == 0 {
               m.v2[r][c+1] = 0
               m.g2(r, c+1)
           } 
       }
   }

}

func main() {

   rand.Seed(time.Now().UnixNano())
   const height = 4
   const width = 7
   m := newMaze(height, width)
   m.gen() 
   m.solve(
       rand.Intn(height), rand.Intn(width),
       rand.Intn(height), rand.Intn(width))
   fmt.Print(m)

}

func (m *maze) solve(ra, ca, rz, cz int) {

   var rSolve func(ra, ca, dir int) bool
   rSolve = func(r, c, dir int) bool {
       if r == rz && c == cz {
           m.c2[r][c] = 'F'
           return true
       }
       if dir != dn && m.h2[r][c] == 0 {
           if rSolve(r-1, c, up) {
               m.c2[r][c] = '^'
               m.h2[r][c] = '^'
               return true
           }
       }
       if dir != up && r+1 < len(m.h2) && m.h2[r+1][c] == 0 {
           if rSolve(r+1, c, dn) {
               m.c2[r][c] = 'v'
               m.h2[r+1][c] = 'v'
               return true
           }
       }
       if dir != lf && c+1 < len(m.v2[0]) && m.v2[r][c+1] == 0 {
           if rSolve(r, c+1, rt) {
               m.c2[r][c] = '>'
               m.v2[r][c+1] = '>'
               return true
           }
       }
       if dir != rt && m.v2[r][c] == 0 {
           if rSolve(r, c-1, lf) {
               m.c2[r][c] = '<'
               m.v2[r][c] = '<'
               return true
           }
       }
       return false
   }
   rSolve(ra, ca, -1)
   m.c2[ra][ca] = 'S'

}</lang> Example output:

+---+---+---+---+---+---+---+
|           | v < < < < < < |
+   +---+   + v +   +---+ ^ +
|       | F < < |   |     ^ |
+---+---+---+---+   +---+ ^ +
|               |       | ^ |
+   +---+---+   +---+   + ^ +
|   |                   | S |
+---+---+---+---+---+---+---+

Haskell

Works with: GHC version 7.4.1

On standard input, takes a maze made up of "+", "|", and "---" (i. e. each cell is two lines high and four characters wide), such as produced by the Haskell or Java generators.

<lang haskell>#!/usr/bin/runhaskell

import Data.Maybe

-- given two points, returns the average of them average :: (Int, Int) -> (Int, Int) -> (Int, Int) average (x, y) (x', y') = ((x + x') `div` 2, (y + y') `div` 2)

-- given a maze and a tuple of position and wall position, returns -- true if the wall position is not blocked (first position is unused) notBlocked :: [String] -> ((Int, Int), (Int, Int)) -> Bool notBlocked maze (_, (x, y)) = ' ' == (maze !! y) !! x

-- given a list, a position, and an element, returns a new list -- with the new element substituted at the position -- (it seems such a function should exist in the standard library; -- I must be missing it) substitute :: [a] -> Int -> a -> [a] substitute orig pos el =

 let (before, after) = splitAt pos orig
 in before ++ [el] ++ tail after

-- given a maze and a position, draw a '*' at that position in the maze draw :: [String] -> (Int, Int) -> [String] draw maze (x,y) = substitute maze y $ substitute row x '*'

 where row = maze !! y

-- given a maze, a previous position, and a list of tuples of potential -- new positions and their wall positions, returns the solved maze, or -- None if it cannot be solved tryMoves :: [String] -> (Int, Int) -> [((Int, Int), (Int, Int))] -> Maybe [String] tryMoves _ _ [] = Nothing tryMoves maze prevPos ((newPos,wallPos):more) =

 case solve' maze newPos prevPos
      of Nothing -> tryMoves maze prevPos more
         Just maze' -> Just $ foldl draw maze' [newPos, wallPos]

-- given a maze, a new position, and a previous position, returns -- the solved maze, or None if it cannot be solved -- (assumes goal is upper-left corner of maze) solve' :: [String] -> (Int, Int) -> (Int, Int) -> Maybe [String] solve' maze (2, 1) _ = Just maze solve' maze pos@(x, y) prevPos =

 let newPositions = [(x, y - 2), (x + 4, y), (x, y + 2), (x - 4, y)]
     notPrev pos' = pos' /= prevPos
     newPositions' = filter notPrev newPositions
     wallPositions = map (average pos) newPositions'
     zipped = zip newPositions' wallPositions
     legalMoves = filter (notBlocked maze) zipped
 in tryMoves maze pos legalMoves

-- given a maze, returns a solved maze, or None if it cannot be solved -- (starts at lower right corner and goes to upper left corner) solve :: [String] -> Maybe [String] solve maze = solve' (draw maze start) start (-1, -1)

 where startx = length (head maze) - 3
       starty = length maze - 2
       start = (startx, starty)

-- takes unsolved maze on standard input, prints solved maze on standard output main = interact main'

 where main' x = unlines $ fromMaybe ["can't solve"] $ solve $ lines x</lang>

Output:

+---+---+---+---+---+---+---+---+---+---+---+
| * |           |               |           |
+ * +   +---+   +   +---+   +---+   +---+   +
| * |       |   |       |   |           |   |
+ * +---+   +   +---+   +---+   +---+---+   +
| *         |       |       |   |   |       |
+ * +---+---+---+   +---+   +   +   +   +   +
| * * * * * * * |       |           |   |   |
+---+---+---+ * +---+   +---+---+---+   +   +
|           | * * * |   |           |   |   |
+   +---+   +---+ * +   +   +---+   +   +---+
|       |   | * * * |       |   |   |       |
+---+---+   + * +---+---+---+   +   +---+   +
|           | * * * * * |       |       |   |
+   +---+---+---+---+ * +---+   +---+---+   +
|                     * * * * * * * * * * * |
+---+---+---+---+---+---+---+---+---+---+---+

Icon and Unicon

The following code works with the solution from Maze Generation.

Replace the main with this: <lang Icon>procedure main(A)

  /mh := \A[1] | 12
  /mw := \A[2] | 16
  mz := DisplayMaze(GenerateMaze(mh,mw))
  WriteImage(mz.filename)              # save file
  WAttrib(mz.window,"canvas=normal")   # show it
  until Event() == &lpress # wait for left mouse press
  Solver(mz.maze)
  DisplayMazeSolution(mz)
  WriteImage(mz.filename ?:= (="maze-", "maze-solved-" || tab(0)))
  until Event() == &lpress # wait
  close(mz.window)

end</lang>

And include this after the Generator and Display procedures. <lang Icon>procedure Solver(r,c) static maze,h,w,rd

  if type(r) == "list" then { # ------------------- Top Level (r == maze)
     h := *(maze := r)                              # height
     w := *maze[1]                                  # width
     every r := 1 to h & c := 1 to w do             # remove breadcrumbs
        maze[r,c] := iand(maze[r,c],NORTH+EAST+SOUTH+WEST+START+FINISH)                               
     every ((r := 1 | h) & (c := 1 to w)) |         # search perimiter
           ((r := 1 to h) & (c := 1 | w)) do 
           if iand(maze[r,c],START) > 0 then break  # until start found
     Solver(r,c)                                    # recurse through maze      
     return 1(.maze,maze := &null)                  # return maze and reset 
     }
  else                        # ------------------- Recurse way through maze
     if iand(x := maze[r,c],SEEN) = 0  then {       # in bounds and not seen?
        (iand(x,FINISH) > 0, maze[r,c] +:= PATH, return ) # at finish? - done!
        maze[r,c] +:= SEEN                          # drop bread crumb
        (iand(x,NORTH) > 0, Solver(r-1,c), maze[r,c] +:= PATH, return) 
        (iand(x,EAST)  > 0, Solver(r,c+1), maze[r,c] +:= PATH, return) 
        (iand(x,SOUTH) > 0, Solver(r+1,c), maze[r,c] +:= PATH, return)  
        (iand(x,WEST)  > 0, Solver(r,c-1), maze[r,c] +:= PATH, return)   
        }

end

procedure DisplayMazeSolution(mz) #: draw marked PATH &window := mz.window maze := mz.maze WAttrib("dx="||(dxy:=BORDER+CELL/2),"dy="||dxy) every (r := 1 to *maze) & (c := 1 to *maze[1]) do {

  if fg ~=== "blue" then Fg(fg := "blue")
  if iand(maze[r,c],START) > 0 then Fg(fg := "red")
  if iand(maze[r,c],PATH) > 0 then
     FillCircle(x := CELL*(c-1),y := CELL*(r-1),rad := CELL/5)
  }

return mz end</lang>

J

<lang J> NB. source Dijkstra_equal_weights graph NB. NB. + +---+---+ NB. | 0 1 2 | (sample cell numbers) NB. +---+ + + NB. | 3 4 | 5 NB. +---+---+---+ NB. NB. graph =: 1;0 2 4;1 5;4;1 3;2 NB. The graph is a vector of boxed vectors of neighbors.

Dijkstra_equal_weights =: 4 : 0

dist =. previous =. #&_ n =. # graph =. y [ source =. x
dist =. 0 source } dist
Q =. 0
while. #Q do.
  u =. {.Q
  Q =. }.Q
  if. _ = u{dist do. break. end.
  for_v. >u{graph do.
    if. -. v e. previous do.
      alt =. >: u { dist
      if. alt < v { dist do.
        dist =. alt v } dist
        previous =. u v } previous
        if. v e. Q do.
          echo 'belch'
        else.
          Q =. Q,v
        end.
      end.
    end.
  end.
end.
dist;previous

)

path =. 3 : 0

 p =. <:#y
 while. _ > {:p do.
   p =. p,y{~{:p
 end.
 |.}:p

)

solve=:3 :0

 NB. convert walls to graph
 shape =. }.@$@:>
 ew =. (,.&0 ,: 0&,.)@>@{.  NB. east west doors
 ns =. (, &0 ,: 0&, )@>@{:
 cell_offsets =. 1 _1 1 _1 * 2 # 1 , {:@shape
 cell_numbers =. i.@shape
 neighbors =. (cell_numbers +"_ _1 cell_offsets *"_1 (ew , ns))y
 graph =. (|:@(,/"_1) <@-."1 0 ,@i.@shape)neighbors NB. list of boxed neighbors
 NB. solve it
 path , > {: 0 Dijkstra_equal_weights graph

)

display=:3 :0 NB. Monadic display copied from maze generation task

 size=. >.&$&>/y
 text=. (}:1 3$~2*1+{:size)#"1":size$<' '
 'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y
 ' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text

 a=. display y
 size=. >.&$&>/y
 columns=. {: size
 cells =. <"1(1 2&p.@<.@(%&columns) ,.  2 4&p.@(columns&|))x
 '+' cells } a  NB. exercise, replace cells with a gerund to draw arrows on the path.

)

  4 (display~ solve)@maze 9

┌ ┬───┬───┬───┬───┬───┬───┬───┬───┐ │ + │ │ │ ├ ┼───┼ ┼ ┼ ┼───┼ ┼ ┼ ┤ │ + + │ │ │ │ │ ├───┼ ┼───┼───┼───┼───┼───┼ ┼───┤ │ │ + + + │ + + + │ │ ├ ┼───┼───┼ ┼ ┼───┼ ┼───┼───┤ │ + + │ + + + └───┴───┴───┴───┴───┴───┴───┴───┴───┘

</lang>

Java

<lang java>import java.io.*; import java.util.*;

public class MazeSolver {

   /**
    * Reads a file into an array of strings, one per line.
    */
   private static String[] readLines (InputStream f) throws IOException
   {
       BufferedReader r =
           new BufferedReader (new InputStreamReader (f, "US-ASCII"));
       ArrayList<String> lines = new ArrayList<String>();
       String line;
       while ((line = r.readLine()) != null)
           lines.add (line);
       return lines.toArray(new String[0]);
   }

   /**
    * Makes the maze half as wide (i. e. "+---+" becomes "+-+"), so that
    * each cell in the maze is the same size horizontally as vertically.
    * (Versus the expanded version, which looks better visually.)
    * Also, converts each line of the maze from a String to a
    * char[], because we'll want mutability when drawing the solution later.
    */
   private static char[][] decimateHorizontally (String[] lines)
   {
       final int width = (lines[0].length() + 1) / 2;
       char[][] c = new char[lines.length][width];
       for (int i = 0  ;  i < lines.length  ;  i++)
           for (int j = 0  ;  j < width  ;  j++)
               c[i][j] = lines[i].charAt (j * 2);
       return c;
   }

   /**
    * Given the maze, the x and y coordinates (which must be odd),
    * and the direction we came from, return true if the maze is
    * solvable, and draw the solution if so.
    */
   private static boolean solveMazeRecursively (char[][] maze,
                                                int x, int y, int d)
   {
       boolean ok = false;
       for (int i = 0  ;  i < 4  &&  !ok  ;  i++)
           if (i != d)
               switch (i)
                   {
                       // 0 = up, 1 = right, 2 = down, 3 = left
                   case 0:
                       if (maze[y-1][x] == ' ')
                           ok = solveMazeRecursively (maze, x, y - 2, 2);
                       break;
                   case 1:
                       if (maze[y][x+1] == ' ')
                           ok = solveMazeRecursively (maze, x + 2, y, 3);
                       break;
                   case 2:
                       if (maze[y+1][x] == ' ')
                           ok = solveMazeRecursively (maze, x, y + 2, 0);
                       break;
                   case 3:
                       if (maze[y][x-1] == ' ')
                           ok = solveMazeRecursively (maze, x - 2, y, 1);
                       break;
                   }
       // check for end condition
       if (x == 1  &&  y == 1)
           ok = true;
       // once we have found a solution, draw it as we unwind the recursion
       if (ok)
           {
               maze[y][x] = '*';
               switch (d)
                   {
                   case 0:
                       maze[y-1][x] = '*';
                       break;
                   case 1:
                       maze[y][x+1] = '*';
                       break;
                   case 2:
                       maze[y+1][x] = '*';
                       break;
                   case 3:
                       maze[y][x-1] = '*';
                       break;
                   }
           }
       return ok;
   }

   /**
    * Solve the maze and draw the solution.  For simplicity,
    * assumes the starting point is the lower right, and the
    * ending point is the upper left.
    */
   private static void solveMaze (char[][] maze)
   {
       solveMazeRecursively (maze, maze[0].length - 2, maze.length - 2, -1);
   }

   /**
    * Opposite of decimateHorizontally().  Adds extra characters to make
    * the maze "look right", and converts each line from char[] to
    * String at the same time.
    */
   private static String[] expandHorizontally (char[][] maze)
   {
       char[] tmp = new char[3];
       String[] lines = new String[maze.length];
       for (int i = 0  ;  i < maze.length  ;  i++)
           {
               StringBuilder sb = new StringBuilder(maze[i].length * 2);
               for (int j = 0  ;  j < maze[i].length  ;  j++)
                   if (j % 2 == 0)
                       sb.append (maze[i][j]);
                   else
                       {
                           tmp[0] = tmp[1] = tmp[2] = maze[i][j];
                           if (tmp[1] == '*')
                               tmp[0] = tmp[2] = ' ';
                           sb.append (tmp);
                       }
               lines[i] = sb.toString();
           }
       return lines;
   }

   /**
    * Accepts a maze as generated by:
    * http://rosettacode.org/wiki/Maze_generation#Java
    * in a file whose name is specified as a command-line argument,
    * or on standard input if no argument is specified.
    */
   public static void main (String[] args) throws IOException
   {
       InputStream f = (args.length > 0
                        ?  new FileInputStream (args[0])
                        :  System.in);
       String[] lines = readLines (f);
       char[][] maze = decimateHorizontally (lines);
       solveMaze (maze);
       String[] solvedLines = expandHorizontally (maze);
       for (int i = 0  ;  i < solvedLines.length  ;  i++)
           System.out.println (solvedLines[i]);
   }

}</lang>

Output:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| * |           |               |         * * * * * |           |
+ * +   +   +---+   +---+---+   +   +---+ * +---+ * +---+   +---+
| * |   |       |   | * * * |   |       | * * * | * * * |       |
+ * +   +---+   +   + * + * +   +---+   +---+ * +---+ * +---+   +
| * |       |       | * | * |           | * * * |   | * |       |
+ * +---+---+   +---+ * + * +---+---+   + * +---+   + * +   +   +
| * | * * * |       | * | * | * * * |   | * |       | * |   |   |
+ * + * + * +---+   + * + * + * + * +---+ * +---+   + * +   +---+
| * * * | * |       | * | * * * | * * * * * |       | * |       |
+---+---+ * +---+---+ * +---+---+---+---+---+   +---+ * +---+   +
|       | * * * | * * * |               |           | * * * |   |
+   +---+---+ * + * +---+   +---+---+   +   +---+   +---+ * +   +
| * * * * * * * | * |   |           |   |   |   |       | * * * |
+ * +---+---+---+ * +   +   +---+   +---+   +   +   +---+---+ * +
| * * * * * * * * * |           |               |             * |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Mathematica

Graph

Solving the maze generated in Maze_generation#Graph: <lang mathematica>HighlightGraph[maze, PathGraph@FindShortestPath[maze, 1, 273]]</lang>

Output:

Perl 6

Works with: niecza version 2013-03-06

(Includes maze generation code.) <lang perl6>constant mapping = :OPEN(' '), :N< ╵ >, :E< ╶ >, :NE< └ >, :S< ╷ >, :NS< │ >, :ES< ┌ >, :NES< ├ >, :W< ╴ >, :NW< ┘ >, :EW< ─ >, :NEW< ┴ >, :SW< ┐ >, :NSW< ┤ >, :ESW< ┬ >, :NESW< ┼ >, :TODO< x >, :TRIED< · >;

enum Code (mapping.map: *.key); my @code = mapping.map: *.value;

enum Direction <DeadEnd Up Right Down Left>;

sub gen_maze ( $X,

              $Y,
              $start_x = (^$X).pick * 2 + 1,
              $start_y = (^$Y).pick * 2 + 1 )

{

   my @maze;
   push @maze, [ ES, -N, (ESW, EW) xx $X - 1, SW ];
   push @maze, [ (NS, TODO) xx $X, NS ];
   for 1 ..^ $Y {

push @maze, [ NES, EW, (NESW, EW) xx $X - 1, NSW ]; push @maze, [ (NS, TODO) xx $X, NS ];

   }
   push @maze, [ NE, (EW, NEW) xx $X - 1, -NS, NW ];
   @maze[$start_y][$start_x] = OPEN;

   my @stack;
   my $current = [$start_x, $start_y];
   loop {
       if my $dir = pick_direction( $current ) {
           @stack.push: $current;
           $current = move( $dir, $current );
       }
       else {
           last unless @stack;
           $current = @stack.pop;
       }
   }
   return @maze;

   sub pick_direction([$x,$y]) {

my @neighbors = (Up if @maze[$y - 2][$x]), (Down if @maze[$y + 2][$x]), (Left if @maze[$y][$x - 2]), (Right if @maze[$y][$x + 2]); @neighbors.pick or DeadEnd;

   sub move ($dir, @cur) {

my ($x,$y) = @cur; given $dir { when Up { @maze[--$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y--][$x+1] -= W; } when Down { @maze[++$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y++][$x+1] -= W; } when Left { @maze[$y][--$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x--] -= N; } when Right { @maze[$y][++$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x++] -= N; } } @maze[$y][$x] = 0; [$x,$y];

}

sub display (@maze) {

   for @maze -> @y {

for @y -> $w, $c { print @code[abs $w]; if $c >= 0 { print @code[$c] x 3 } else { print ' ', @code[abs $c], ' ' } } say @code[@y[*-1]];

}

my @M = gen_maze( 29, 19 );

display solve @M;

sub solve (@maze is copy, @from = [1, 1], @to = [@maze[0] - 2, @maze - 2]) {

   my ($x, $y) = @from;
   my ($xto, $yto) = @to;
   my @stack;

   sub drop-crumb($x,$y,$c) { @maze[$y][$x] = -$c }
   drop-crumb($x,$y,N);

   loop {

my $dir = pick_direction([$x,$y]); if $dir { ($x, $y) = move($dir, [$x,$y]); return @maze if $x == $xto and $y == $yto; } else { @maze[$y][$x] = -TRIED; ($x,$y) = @stack.pop[]; @maze[$y][$x] = -TRIED; ($x,$y) = @stack.pop[]; }

   sub pick_direction([$x,$y]) {

my @neighbors = (Up unless @maze[$y - 1][$x]), (Down unless @maze[$y + 1][$x]), (Left unless @maze[$y][$x - 1]), (Right unless @maze[$y][$x + 1]); @neighbors.pick or DeadEnd;

   sub move ($dir, @cur) {

my ($x,$y) = @cur; given $dir { when Up { for ^2 { push @stack, [$x,$y--]; drop-crumb $x,$y,S; } } when Down { for ^2 { push @stack, [$x,$y++]; drop-crumb $x,$y,N; } } when Left { for ^2 { push @stack, [$x--,$y]; drop-crumb $x,$y,E; } } when Right { for ^2 { push @stack, [$x++,$y]; drop-crumb $x,$y,W; } } } $x,$y;

}</lang>

Output:

┌ ╵ ────┬───────────────┬───────────────┬───────────────────────────────┬───────────┬───────────────┬───────────────┐
│ ╵ · · │ ╷ ╴ ╴ ╴ ╴     │               │ ╷ ╴ ╴ · · · · · · · · · · · · │ ╷ ╴ ╴ · · │ · · · · · · · │ · · · · · · · │
│ ╵ ╶───┘ ╷ ╶───┐ ╵ ╷   │   ╷   ╶───────┤ ╷ ╷ ╵ ╶───────┬───────┐ · ┌───┘ ╷ ╷ ╵ ╷ · │ · ╶───┬───╴ · │ · ╷ · ┌───╴ · │
│ ╵ ╴ ╴ ╴ ╴ · · │ ╵ │   │   │           │ ╷ │ ╵ ╴ ╴ ╴ ╴ │ ╷ ╴ ╴ │ · │ ╷ ╴ ╴ │ ╵ │ · │ · · · │ · · · │ · │ · │ · · · │
│ · ┌───────────┤ ╵ │   └───┴───────╴   │ ╷ ├───────┐ ╵ ╵ ╷ ╷ ╵ └───┘ ╷ ┌───┘ ╵ │ · │ · ╷ · │ · ┌───┴───┘ · │ · ╶───┤
│ · │ ╶ ╶ ╶ ╶ ╷ │ ╵ │                   │ ╷ │       │ ╵ ╴ ╴ │ ╵ ╴ ╴ ╴ ╴ │ ╶ ╶ ╵ │ · │ · │ · │ · │ · · · · · │ · · · │
│ · │ ╵ ╶───┐ ╷ ╵ ╵ ├───────────────╴   │ ╷ └───╴   └───────┼───┬───────┤ ╵ ┌───┤ · ├───┘ · │ · │ · ╷ · ┌───┴───┐ · │
│ · │ ╵ ╴ ╴ │ ╶ ╶ ╵ │                   │ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╷ │ · │ ╶ ╶ ╷ │ ╵ │ · │ · │ · · · │ · │ · │ · │ · · · │ · │
│ · └───┐ ╵ ├───────┴───────┐   ╶───────┴───────┬───────╴ ╷ │ · │ ╵ ╷ ╷ │ ╵ │ · │ · │ · ┌───┤ · │ · │ · │ · ╷ · ╵ · │
│ · · · │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │                   │ ╷ ╴ ╴ ╴ ╴ │ · │ ╵ │ ╷ │ ╵ │ · │ · │ · │ · │ · │ · │ · │ · │ · · · │
├───╴ · │ ╵ │ ╷ ╶───────┐ ╵ ├───────────────┐   │ ╷ ╶───┬───┘ · │ ╵ │ ╷ ╵ ╵ │ · ╵ · ╵ · │ · ╵ · └───┘ · │ · ├───────┤
│ · · · │ ╵ │ ╶ ╶ ╶ ╶ ╷ │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │   │ ╶ ╶ ╷ │ · · · │ ╵ │ ╶ ╶ ╵ │ · · · · · │ · · · · · · · │ · │ · · · │
│ · ┌───┤ ╵ └───────╴ ╷ │ ╵ ╵ ╷ ┌───────┐ ╵ │   └───┐ ╷ └───┐ · │ ╵ ├───────┼───────┬───┴───────┬───┬───┘ · ├───╴ · │
│ · │ · │ ╵ ╴ ╴ ╴ ╴ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ ╵ │       │ ╶ ╶ ╷ │ · │ ╵ │ ╷ ╴ ╴ │ ╷ ╴ ╴ │ ╷ ╴ ╴ ╴ ╴ │ · │ · · · │ · · · │
│ · ╵ · ├───────────────┴───────┴───┐ · │ ╵ └───────┴───┐ ╷ │ · │ ╵ ╵ ╷ ╷ ╵ ╵ ╷ ╷ ╵ │ ╷ ┌───╴ ╵ │ · │ · ╶───┤ · ╶───┤
│ · · · │ · · · · · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ · · │ ╷ │ · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ ╵ │ ╷ │ ╶ ╶ ╵ │ · │ · · · │ · · · │
├───┐ · │ · ┌───────────╴ · ┌───┐ · │ · └───┬───╴ ╵ ┌───┘ ╷ │ · ├───────┴───────┤ ╵ ╵ ╷ │ ╵ ╶───┤ · └───┐ · │ · ╷ · │
│ · │ · │ · │ · · · · · · · │ · │ · │ · · · │ ╶ ╶ ╵ │ ╷ ╴ ╴ │ · │ · · · · · · · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ · │ · │ · │
│ · │ · └───┘ · ┌───────────┘ · │ · ├───╴ · │ ╵ ┌───┘ ╷ ┌───┘ · │ · ╷ · ┌───╴ · └───────┴───┐ ╵ └───┐ · ╵ · ├───┘ · │
│ · │ · · · · · │ · · · · · · · │ · │ · · · │ ╵ │ ╷ ╴ ╴ │ · · · │ · │ · │ · · · · · · · · · │ ╵ ╴ ╴ │ · · · │ · · · │
│ · ├───────╴ · ├───┐ · ┌───┐ · ╵ · │ · ╶───┤ ╵ ╵ ╷ ┌───┘ · ╶───┤ · │ · └───┬───╴ · ┌───────┤ · ╷ ╵ │ · ╶───┘ · ╷ · │
│ · │ · · · · · │   │ · │ · │ · · · │ · · · │ ╵ ╴ ╴ │ · · · · · │ · │ · · · │ · · · │ ╶ ╶ ╷ │ · │ ╵ │ · · · · · │ · │
│ · ╵ · ┌───────┘   │ · ╵ · └───────┤ · ╷ · └───────┴───────┐ · ╵ · └───┐ · └───┐ · │ ╵ ╷ ╷ └───┘ ╵ ├───────────┤ · │
│ · · · │           │ · · · · · · · │ · │ · · · · · · · · · │ · · · · · │ · · · │ · │ ╵ │ ╶ ╶ ╶ ╶ ╵ │ ╷ ╴ ╴ ╴ ╴ │ · │
│ · ╶───┤   ╶───────┴───┬───────┐ · ├───┘ · ┌───────────┐ · ├───────────┴───╴ · │ · │ ╵ └───────┐ · │ ╷ ┌───╴ ╵ │ · │
│ · · · │               │ · · · │ · │ · · · │ · · · · · │ · │ · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ │ · │ ╷ │ ╶ ╶ ╵ │ · │
├───┐ · ├───────┬───╴   │ · ╷ · │ · │ · ┌───┤ · ╶───────┤ · │ · ╶───────┬───┐ · ├───┴───────┐ ╵ └───┘ ╷ │ ╵ ┌───┴───┤
│ · │ · │       │       │ · │ · │ · │ · │ · │ · · · · · │ · │ · · · · · │ · │ · │           │ ╵ ╴ ╴ ╴ ╴ │ ╵ │ ╷ ╴ ╴ │
│ · │ · │   ╷   ╵   ┌───┘ · │ · ╵ · ╵ · │ · ╵ · ┌───┐ · ╵ · └───────╴ · │ · ╵ · │   ┌───╴   └───────┐ · │ ╵ ╵ ╷ ╷ ╵ │
│ · │ · │   │       │ · · · │ · · · · · │ · · · │ · │ · · · · · · · · · │ · · · │   │               │ · │ ╵ ╴ ╴ │ ╵ │
│ · │ · │   └───┬───┴───────┴───┬───────┤ · ┌───┘ · ├───────────────────┴───────┤   └───────────┐   └───┴───────┤ ╵ │
│ · │ · │       │               │       │ · │ · · · │                           │               │               │ ╵ │
│ · ╵ · ├───┐   │   ╶───────┐   ╵   ╷   │ · ╵ · ╷ · │   ╶───────────────────┐   └───┬───────┐   └───────┬───┐   │ ╵ │
│ · · · │ · │   │           │       │   │ · · · │ · │                       │       │       │           │   │   │ ╵ │
│ · ╶───┤ · │   └───────┐   ├───────┤   └───┬───┴───┼───────────┬───────┐   ├───┐   ╵   ╷   ├───────┐   │   │   │ ╵ │
│ · · · │ · │           │   │       │       │       │           │       │   │   │       │   │       │   │   │   │ ╵ │
├───╴ · ╵ · └───────┐   ╵   │   ╷   └───╴   ╵   ╷   ╵   ┌───╴   ╵   ╷   ╵   │   └───────┘   ╵   ╷   ╵   │   ╵   ╵ ╵ │
│ · · · · · · · · · │       │   │               │       │           │       │                   │       │         ╵ │
└───────────────────┴───────┴───┴───────────────┴───────┴───────────┴───────┴───────────────────┴───────┴──────── │ ┘

PicoLisp

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

  (let (Path NIL  Best NIL  Dir " > ")
     (recur (This Path Dir)
        (when (and This (not (: mark)))
           (push 'Path (cons This Dir))
           (if (== Goal This)
              (unless (and Best (>= (length Path) (length Best)))
                 (setq Best Path) )
              (=: mark T)
              (recurse (: west) Path " > ")
              (recurse (: east) Path " < ")
              (recurse (: south) Path " \^ ")
              (recurse (: north) Path " v ")
              (=: mark NIL) ) ) )
     (disp Maze 0
        '((Fld) (if (asoq Fld Best) (cdr @) "   ")) ) ) )</lang>

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

: (shortestPath 'a8 'k1 (maze 11 8))
   +   +---+---+---+---+---+---+---+---+---+---+
 8 | >   >   v | >   v |                       |
   +   +   +   +   +   +   +---+   +---+---+   +
 7 |   |   | >   ^ | v |   |       |       |   |
   +---+   +---+---+   +   +   +---+   +   +   +
 6 |   |       |     v |   |           |   |   |
   +   +---+   +---+   +---+---+---+   +   +---+
 5 |       |       | >   >   >   v |   |       |
   +---+   +---+   +---+---+---+   +---+---+   +
 4 |   |       |       |       | v | >   >   v |
   +   +---+   +---+   +---+   +   +   +---+   +
 3 |       |       |   |       | v | ^   < | v |
   +   +---+---+   +   +   +   +   +---+   +   +
 2 |       |       |   |   |   | v | >   ^ | v |
   +   +   +   +---+   +   +---+   +   +---+   +
 1 |   |               |         >   ^ |     >
   +---+---+---+---+---+---+---+---+---+---+---+
     a   b   c   d   e   f   g   h   i   j   k

Prolog

Works with SWI-Prolog and XPCE.

<lang Prolog>:- dynamic cell/2.

- dynamic maze/3.

- dynamic path/1.

maze_solve(Lig,Col) :- retractall(cell(_,_)), retractall(maze(_,_,_)), retractall(path(_)),

% initialisation of the neighbours of the cells forall(between(0, Lig, I), ( forall(between(0, Col, J), assert(maze(I, J, []))))),

% creation of the window of the maze new(D, window('Maze')), forall(between(0,Lig, I), (XL is 50, YL is I * 30 + 50, XR is Col * 30 + 50, new(L, line(XL, YL, XR, YL)), send(D, display, L))),

forall(between(0,Col, I), (XT is 50 + I * 30, YT is 50, YB is Lig * 30 + 50, new(L, line(XT, YT, XT, YB)), send(D, display, L))),

SX is Col * 30 + 100, SY is Lig * 30 + 100, send(D, size, new(_, size(SX, SY))), L0 is random(Lig), C0 is random(Col), assert(cell(L0, C0)), \+search(D, Lig, Col, L0, C0), send(D, open),

% we look for a path from cell(0, 0) to cell(Lig-1, Col-1) % creation of the entrance erase_line(D, -1, 0, 0, 0),

% creation of the exit Lig1 is Lig-1, Col1 is Col-1, erase_line(D, Lig1, Col1, Lig, Col1),

% seraching the path assert(path([[0, 0], [-1, 0]])), walk(Lig, Col), path(P), display_path(D, P).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% walk(Lig, Col) :- path([[L, C] | _R]), L is Lig - 1, C is Col - 1, retract(path(P)), assert(path([[Lig, C]|P])).

walk(Lig, Col) :- retract(path([[L, C] | R])), maze(L, C, Edge), member([L1, C1], Edge), \+member([L1, C1], R), assert(path([[L1,C1], [L, C] | R])), walk(Lig, Col).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% display_path(_, []).

display_path(D, [[L, C] | R]):- new(B, box(10,10)), send(B, fill_pattern, new(_, colour(@default, 0,0,0))), X is C * 30 + 60, Y is L * 30 + 60, send(D, display, B, point(X,Y)), display_path(D, R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% search(D, Lig, Col, L, C) :- Dir is random(4), nextcell(Dir, Lig, Col, L, C, L1, C1), assert(cell(L1,C1)), assert(cur(L1,C1)),

retract(maze(L, C, Edge)), assert(maze(L, C, [[L1, C1] | Edge])), retract(maze(L1, C1, Edge1)), assert(maze(L1, C1, [[L, C] | Edge1])),

erase_line(D, L, C, L1, C1), search(D, Lig, Col, L1, C1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% erase_line(D, L, C, L, C1) :- ( C < C1 -> C2 = C1; C2 = C), XT is C2 * 30 + 50, YT is L * 30 + 51, YR is (L+1) * 30 + 50, new(Line, line(XT, YT, XT, YR)), send(Line, colour, white), send(D, display, Line).

erase_line(D, L, C, L1, C) :- XT is 51 + C * 30, XR is 50 + (C + 1) * 30, ( L < L1 -> L2 is L1; L2 is L), YT is L2 * 30 + 50, new(Line, line(XT, YT, XR, YT)), send(Line, colour, white), send(D, display, Line).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% nextcell(Dir, Lig, Col, L, C, L1, C1) :- next(Dir, Lig, Col, L, C, L1, C1); ( Dir1 is (Dir+3) mod 4, next(Dir1, Lig, Col, L, C, L1, C1)); ( Dir2 is (Dir+1) mod 4, next(Dir2, Lig, Col, L, C, L1, C1)); ( Dir3 is (Dir+2) mod 4, next(Dir3, Lig, Col, L, C, L1, C1)).

% 0 => northward next(0, _Lig, _Col, L, C, L1, C) :- L > 0, L1 is L - 1, \+cell(L1, C).

% 1 => rightward next(1, _Lig, Col, L, C, L, C1) :- C < Col - 1, C1 is C + 1, \+cell(L, C1).

% 2 => southward next(2, Lig, _Col, L, C, L1, C) :- L < Lig - 1, L1 is L + 1, \+cell(L1, C).

% 3 => leftward next(2, _Lig, _Col, L, C, L, C1) :- C > 0, C1 is C - 1, \+cell(L, C1).

</lang> output :

PureBasic

<lang PureBasic>;code from the maze generation task is place here in its entirety before the rest of the code

Procedure displayMazePath(Array maze(2), List Path.POINT())

 Protected x, y, vWall.s, hWall.s
 Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2)
 Protected Dim mazeOutput.mazeOutput(mazeHeight)
 Protected Dim mazeRow.mazeOutput(0)
 Static pathChars.s = "@^>v<"
 
 For y = 0 To mazeHeight
   makeDisplayMazeRow(mazeRow(), maze(), y): mazeOutput(y) = mazeRow(0)
 Next
 
 If ListSize(path())
   FirstElement(path())
   Protected prevPath.POINT = path()
   
   While NextElement(path())
     x = path()\x - prevPath\x
     y = path()\y - prevPath\y
     Select x
       Case -1: dirTaken = #dir_W
       Case 1: dirTaken = #dir_E
       Default
         If y < 0
           dirTaken = #dir_N
         Else
           dirTaken = #dir_S
         EndIf 
     EndSelect
     hWall = mazeOutput(prevPath\y)\hWall
     mazeOutput(prevPath\y)\hWall = Left(hWall, prevPath\x * #cellDWidth + 2) + Mid(pathChars, dirTaken + 1, 1) + Right(hWall, Len(hWall) - (prevPath\x * #cellDWidth + 3))
     prevPath = path()
   Wend 
   hWall = mazeOutput(prevPath\y)\hWall
   mazeOutput(prevPath\y)\hWall = Left(hWall, prevPath\x * #cellDWidth + 2) + Mid(pathChars, #dir_ID + 1, 1) + Right(hWall, Len(hWall) - (prevPath\x * #cellDWidth + 3))
   
   For y = 0 To mazeHeight
     PrintN(mazeOutput(y)\vWall): PrintN(mazeOutput(y)\hWall)
   Next 
 EndIf

EndProcedure

Procedure solveMaze(Array maze(2), *start.POINT, *finish.POINT, List Path.POINT())

 Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2)
 Dim visited(mazeWidth + 1, mazeHeight + 1) ;includes padding for easy border detection
 
 Protected i
 ;mark outside border as already visited (off limits)
 For i = 1 To mazeWidth
   visited(i, 0) = #True: visited(i, mazeHeight + 1) = #True
 Next
 For i = 1 To mazeHeight
   visited(0, i) = #True: visited(mazeWidth + 1, i) = #True
 Next
 
 Protected x = *start\x, y = *start\y, nextCellDir
 visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True
 
 ClearList(path())
 Repeat
   If x = *finish\x And y = *finish\y
     AddElement(path())
     path()\x = x: path()\y = y
     Break ;success
   EndIf 
   
   nextCellDir = #firstDir - 1
   For i = #firstDir To #numDirs
     If Not visited(x + offset(#visited, i)\x, y + offset(#visited, i)\y)
       If maze(x + offset(#wall, i)\x, y + offset(#wall, i)\y) & wallvalue(i) <> #Null
         nextCellDir = i: Break ;exit for/next search
       EndIf 
     EndIf 
   Next 
   
   If nextCellDir >= #firstDir
     visited(x + offset(#visited, nextCellDir)\x, y + offset(#visited, nextCellDir)\y) = #True
     
     AddElement(path())
     path()\x = x: path()\y = y
     
     x + offset(#maze, nextCellDir)\x: y + offset(#maze, nextCellDir)\y
   ElseIf ListSize(path()) > 0
     x = path()\x: y = path()\y
     DeleteElement(path())
   Else 
     Break
   EndIf 
 ForEver

EndProcedure

demonstration

If OpenConsole()

 Define.POINT start, finish
 start\x = Random(mazeWidth - 1): start\y = Random(mazeHeight - 1)
 finish\x = Random(mazeWidth - 1): finish\y = Random(mazeHeight - 1)
 NewList Path.POINT()
 solveMaze(maze(), start, finish, path())
 If ListSize(path()) > 0
   PrintN("Solution found for path between (" + Str(start\x) + ", " + Str(start\y) + ") and (" + Str(finish\x) + ", " + Str(finish\y) + ")")
   displayMazePath(maze(), path())
 Else
   PrintN("No solution found for path between (" + Str(start\x) + ", " + Str(start\y) + ") and (" + Str(finish\x) + ", " + Str(finish\y) + ")")
 EndIf 
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang> Using the maze produced in Maze generation#PureBasic, this additional code will find and display the path between two random maze cells. A working example requires combining the two code listings by placing the 'maze generation' code at the beginning of the 'maze solving' code.

Sample output:

Solution found for path between (3, 2) and (7, 1)
+---+---+---+---+---+---+---+---+---+---+
| v   <   <   <   < |   | v   <   <     |
+   +---+---+---+   +   +   +---+   +---+
| >   v         | ^ |   | v | @ | ^   < |
+---+   +---+---+   +   +   +   +---+   +
|   | v |     >   ^ |     v | ^     | ^ |
+   +   +   +---+---+---+   +   +---+   +
| v   < |               | >   ^ | >   ^ |
+   +---+---+---+---+   +---+   +   +   +
| v |       |           |       | ^ |   |
+   +---+   +   +---+---+---+---+   +---+
| >   >   v |       |     >   v | ^   < |
+---+---+   +---+---+---+   +   +---+   +
|         >   >   >   >   ^ | >   >   ^ |
+---+---+---+---+---+---+---+---+---+---+

Python

python 3

def Dijkstra(Graph, source):

   
       +   +---+---+
       | 0   1   2 |
       +---+   +   +
       | 3   4 | 5  
       +---+---+---+

       >>> graph = (        # or ones on the diagonal
       ...     (0,1,0,0,0,0,),
       ...     (1,0,1,0,1,0,),
       ...     (0,1,0,0,0,1,),
       ...     (0,0,0,0,1,0,),
       ...     (0,1,0,1,0,0,),
       ...     (0,0,1,0,0,0,),
       ... )
       ...
       >>> Dijkstra(graph, 0)
       ([0, 1, 2, 3, 2, 3], [1e+140, 0, 1, 4, 1, 2])
       >>> display_solution([1e+140, 0, 1, 4, 1, 2])
       5<2<1<0
   
   # Graph[u][v] is the weight from u to v (however 0 means infinity)
   infinity = float('infinity')
   n = len(graph)
   dist = [infinity]*n   # Unknown distance function from source to v
   previous = [infinity]*n # Previous node in optimal path from source
   dist[source] = 0        # Distance from source to source
   Q = list(range(n)) # All nodes in the graph are unoptimized - thus are in Q
   while Q:           # The main loop
       u = min(Q, key=lambda n:dist[n])                 # vertex in Q with smallest dist[]
       Q.remove(u)
       if dist[u] == infinity:
           break # all remaining vertices are inaccessible from source
       for v in range(n):               # each neighbor v of u
           if Graph[u][v] and (v in Q): # where v has not yet been visited
               alt = dist[u] + Graph[u][v]
               if alt < dist[v]:       # Relax (u,v,a)
                   dist[v] = alt
                   previous[v] = u
   return dist,previous

def display_solution(predecessor):

   cell = len(predecessor)-1
   while cell:
       print(cell,end='<')
       cell = predecessor[cell]
   print(0)

</lang>

Ruby

This solution extends the maze generator script. To get a working script, copy & paste both parts into one file. <lang ruby>class Maze

 # Solve via breadth-first algorithm.
 # Each queue entry is a path, that is list of coordinates with the
 # last coordinate being the one that shall be visited next.
 def solve
   queue = []
   path = nil

   # Enqueue start position.
   enqueue_cell queue, [], @start_x, @start_y

   # Loop as long as there are cells to visit and no solution has
   # been found yet.
   while !queue.empty? && !path
     path = solve_visit_cell queue
   end

   # Clean up.
   reset_visiting_state

   puts "No solution found?!" unless path

   # Mark the cells that make up the shortest path.
   for x, y in path
     @path[y][x] = true
   end
 end

 private

 # Maze solving visiting method.
 def solve_visit_cell(queue)
   # Get the next path.
   path = queue.shift
   # The cell to visit is the last entry in the path.
   x, y = path.last

   # Have we reached the end yet?
   if x == @end_x && y == @end_y
     # Yes, we have!
     return path
   end

   # Mark cell as visited.
   @visited[y][x] = true

   # Left
   new_x = x - 1
   if move_valid?(new_x, y) && !@vertical_walls[y][new_x]
     enqueue_cell queue, path, new_x, y
   end

   # Right
   new_x = x + 1
   if move_valid?(new_x, y) && !@vertical_walls[y][x]
     enqueue_cell queue, path, new_x, y
   end

   # Top
   new_y = y - 1
   if move_valid?(x, new_y) && !@horizontal_walls[new_y][x]
     enqueue_cell queue, path, x, new_y
   end

   # Bottom
   new_y = y + 1
   if move_valid?(x, new_y) && !@horizontal_walls[y][x]
     enqueue_cell queue, path, x, new_y
   end

   # No solution yet.
   return nil
 end

 # Enqueue a new coordinate to visit.
 def enqueue_cell(queue, path, x, y)
   # Copy the current path, add the new coordinates and enqueue
   # the new path.
   path = path.dup
   path << [x, y]
   queue << path
 end

end

Demonstration:

maze = Maze.new 20, 10 maze.solve maze.print </lang> Example output:

+---+---+---+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+
|                   |   | o   o   o   o   o     |   | o   o | o   o   o |       |
+   +---+   +---+   +   +   +---+---+---+   +   +   +---+   +   +---+   +---+   +
|   |   |   |           | o |       | o   o |   |       | o   o |   | o |       |
+   +   +   +---+---+   +   +   +---+   +---+   +---+   +---+---+   +   +   +---+
|   |   |           |   | o   o | o   o |       |           |   | o   o |       |
+   +   +---+---+   +---+---+   +   +---+---+   +   +---+   +   +   +---+---+   +
|   |           |           | o | o   o   o |       |       |   | o   o   o   o |
+   +---+---+   +---+---+   +   +---+---+   +---+---+   +---+   +---+---+---+   +
|               |       |   | o   o |   | o |                       | o   o | o |
+---+---+   +---+   +   +   +---+   +   +   +---+---+---+---+   +---+   +   +   +
|   |       |       |           | o   o | o   o   o |           | o   o | o   o |
+   +   +---+   +---+---+---+---+---+   +---+---+   +   +---+---+   +---+---+---+
|   |       |                       | o |       | o |       |   | o |           |
+   +---+   +---+---+---+---+---+   +   +---+   +   +---+   +   +   +---+---+   +
|       |           |   |           | o   o   o | o   o |       | o |           |
+   +   +---+---+   +   +   +---+---+---+---+   +---+   +---+---+   +   +---+---+
|   |       |       |   |       | o   o   o   o | o   o | o   o   o |           |
+   +   +---+   +---+   +---+   +   +---+---+---+   +---+   +---+---+---+---+   +
|   |                       |     o   o   o     | o   o   o                     |
+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+

Tcl

Works with: Tcl version 8.6

This script assumes that the contents of the generation task have already been sourced. Note that the algorithm implemented here does not assume that the maze is free of circuits, and in the case that there are multiple routes, it finds the shortest one because it is a breadth-first search (by virtue of the queue variable being used as a queue). <lang tcl>oo::define maze {

   method solve {} {

### Initialization of visited matrix and location/path queue set visited [lrepeat $x [lrepeat $y 0]] set queue {0 0 {}}

### Loop to do the searching ### while 1 { # Check for running out of path; an error in maze construction if {[llength $queue] == 0} { error "cannot reach finish" } # Visit the next square from the queue set queue [lassign $queue cx cy path] if {[lindex $visited $cx $cy]} continue lset visited $cx $cy 1 lappend path $cx $cy # Check for reaching the goal if {$cx == $x-1 && $cy == $y-1} break # Add the square in each direction to the queue if a move there is legal foreach {dx dy} {0 1 1 0 0 -1 -1 0} { set nx [expr {$cx + $dx}]; set ny [expr {$cy + $dy}] if { $nx >= 0 && $nx < $x && $ny >= 0 && $ny < $y && ($dx && idx($verti, min($cx,$nx), $cy) || $dy && idx($horiz, $cx, min($cy,$ny))) } then { lappend queue $nx $ny $path } } }

### Loop to set up the path rendering ### # (-2,-2) is just a marker that isn't next to the maze at all, so # guaranteeing the use of the last 'else' clause foreach {cx cy} $path {nx ny} [concat [lrange $path 2 end] -2 -2] { if {$nx-$cx == 1} { lset content $cx $cy "v" } elseif {$nx-$cx == -1} { lset content $cx $cy "^" } elseif {$ny-$cy == -1} { lset content $cx $cy "<" } else { lset content $cx $cy ">" } }

### Return the path ### return $path

}

Do the solution (we ignore the returned path here...)

m solve

Print it out

puts [m view]</lang> Example output:

+   +---+---+---+---+---+---+---+---+---+---+
| v     |                                   |
+   +---+   +---+---+---+---+---+---+---+   +
| v |       | >   v | >   v |   |           |
+   +   +---+   +   +   +   +   +   +---+   +
| v     | >   ^ | v | ^ | v |   |       |   |
+   +---+   +---+   +   +   +   +---+   +---+
| v | >   ^ | v   < | ^ | v |       |   |   |
+   +   +---+   +---+   +   +   +---+   +   +
| >   ^ | v   < | >   ^ | v |       |       |
+---+---+   +---+   +---+   +---+   +---+---+
| v   <   < | >   ^ | v   < | >   >   >   v |
+   +---+---+   +---+   +---+   +---+---+   +
| >   v |     ^   < | >   >   ^ |       | v |
+---+   +---+---+   +---+---+---+   +   +   +
|     >   >   >   ^ |               |     >  
+---+---+---+---+---+---+---+---+---+---+---+