# Maze solving

Maze solving
You are encouraged to solve this task according to the task description, using any language you may know.

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.

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

`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;`
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!
+-*-+---+---+---+---+---+---+---+---+---+---+
| * * * * * * * * * * * * * * * * * * * |   |
+   +   +---+---+---+---+---+---+---+ * +   +
|   |           |       | * * * * * * * |   |
+   +---+---+   +---+   + * +---+---+---+   +
|   |           |       | * |   |           |
+---+   +---+---+   +---+ * +   +   +---+   +
|       |           | * * * |   |   |       |
+   +---+   +---+---+ * +---+   +   +   +---+
|       |   | * * * * * |           |       |
+---+---+   + * +---+---+---+---+   +---+   +
|           | * * * |     * * * |       |   |
+   +   +---+---+ * +---+ * + * +---+---+   +
|   |           | * * * * * | * * * * * * * |
+   +---+   +---+---+---+---+---+---+---+ * +
|       |                                 * |
+---+---+---+---+---+---+---+---+---+---+-*-+
```

## AutoHotkey

Generator and solver combined.

`Width := 10, Height	:= 10												; set grid sizeSleepTime := 0 gosub, Startup Gui, +AlwaysOnTopGui, font, s12, consolasGui, add, edit, vEditGrid x10, % mazeGui, add, button, xs gStartup Default, Generate mazeGui, add, button, x+10 gSolve, Solve Gui, show,, mazeGuiControl,, EditGrid, % maze											; show mazereturn ;-----------------------------------------------------------------------^Esc::GuiEscape:GuiClose:ExitAppreturn ;-----------------------------------------------------------------------Startup:oMaze := []																; initialize Solved := falseloop, % Height{	row := A_Index	loop, % Width														; create oMaze[row,column] borders 		col := A_Index, oMaze[row,col] :=  "LRTB"						; i.e. oMaze[2,5] := LRTB (add all borders)}Random, row, 1, % Height												; random rowRandom, col, 1, % Width													; random colgrid := maze2text(oMaze)												; object to textGuiControl,, EditGrid, % Grid											; show Gridrow := col := 1															; reset to 1,1oMaze := Generate_maze(row, col, oMaze)									; generate maze starting from random row/columnoMaze[1,1] .= "X"														; start from 1,1maze := maze2text(oMaze)												; object to textGuiControl,, EditGrid, % maze											; show mazeGuiControl,, EditRoute													; clear routeGuiControl, Enable, Solvereturn ;-----------------------------------------------------------------------Solve:GuiControl, Disable, Generate mazeGuiControl, Disable, Solveloop % oRoute.MaxIndex()	oRoute.pop() oSolution	:= Solve(1, 1, oMaze)										; solve starting from 1,1oMaze 		:= oSolution.1oRoute 		:= oSolution.2Update(oMaze, oRoute)Solved := trueGuiControl, Enable, Generate mazereturn ;-----------------------------------------------------------------------Update(oMaze, oRoute){	global SleepTime	GuiControl,, EditGrid, % maze2text(oMaze)	Sleep, % SleepTime} ;-----------------------------------------------------------------------maze2text(oMaze){	width := oMaze.1.MaxIndex()	BLK := "█"	for row, objRow in oMaze	{		for col, val in objRow											; add ceiling		{			ceiling := InStr(oMaze[row, col] , "x") && InStr(oMaze[row-1, col] , "x") ? "+ " BLK " " : "+   "			grid .= (InStr(val, "T") ? "+---" : ceiling) (col = Width ? "+`n" : "")		}		for col, val in objRow											; add left wall		{			wall := SubStr(val, 0) = "X" ? BLK : " "			grid .= (InStr(val, "L") ? "| " : "  ") wall " " (col = Width ? "|`n" : "") ; add left wall if needed then outer right border		}	}	Loop % Width		Grid .= "+---"													; add bottom floor	Grid .= "+"															; add right bottom corner	return RegExReplace(grid , BLK "   (?=" BLK ")" ,  BLK BLK BLK BLK)	; fill gaps} ;-----------------------------------------------------------------------Generate_maze(row, col, oMaze) {	neighbors := row+1 "," col "`n" row-1 "," col  "`n" row "," col+1  "`n" row "," col-1	Sort, neighbors, random												; randomize neighbors list	Loop, parse, neighbors, `n											; for each neighbor	{		rowX := StrSplit(A_LoopField, ",").1							; this neighbor row		colX := StrSplit(A_LoopField, ",").2							; this neighbor column		if !instr(oMaze[rowX,colX], "LRTB") || !oMaze[rowX, colX]		; if visited (has a missing border) or out of bounds			continue													; skip 		; remove borders		if (row > rowX)													; Cell is below this neighbor			oMaze[row,col] := StrReplace(oMaze[row,col], "T") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "B")		else if (row < rowX)											; Cell is above this neighbor			oMaze[row,col] := StrReplace(oMaze[row,col], "B") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "T")		else if (col > colX)											; Cell is right of this neighbor			oMaze[row,col] := StrReplace(oMaze[row,col], "L") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "R")		else if (col < colX)											; Cell is left of this neighbor			oMaze[row,col] := StrReplace(oMaze[row,col], "R") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "L") 		Generate_maze(rowX, colX, oMaze)								; recurse for this neighbor	}	return, oMaze} ;-----------------------------------------------------------------------Solve(row, col, oMaze){	static oRoute := []	oNeighbor := [], targetrow := oMaze.MaxIndex(), targetCol := oMaze.1.MaxIndex() 	;~ Update(oMaze, oRoute)	oRoute.push(row ":" col)											; push current cell address to oRoute	oMaze[row, col] .= "X"												; mark it visited "X" 	if (row = targetrow) && (Col = targetCol)							; if solved		return true														; return ture 	; create list of Neighbors	oNeighbor[row, col] := []	if !InStr(oMaze[row, col], "R")										; if no Right border		oNeighbor[row, col].push(row "," col+1)							; add neighbor	if !InStr(oMaze[row, col], "B")										; if no Bottom border		oNeighbor[row, col].push(row+1 "," col)							; add neighbor	if !InStr(oMaze[row, col], "T")										; if no Top border		oNeighbor[row, col].push(row-1 "," col)							; add neighbor	if !InStr(oMaze[row, col], "L")										; if no Left border		oNeighbor[row, col].push(row "," col-1)							; add neighbor 	; recurese for each oNeighbor	for each, neighbor in oNeighbor[row, col]							; for each neighbor 	{		Update(oMaze, oRoute)		startrow := StrSplit(neighbor, ",").1							; this neighbor		startCol := StrSplit(neighbor, ",").2							; becomes starting point		 		if !InStr(oMaze[startrow, startCol], "X")						; if it was not visited			if Solve(startrow, startCol, oMaze)							; recurse for current neighbor				return [oMaze, oRoute]									; return solution if solved	}	oRoute.pop()														; no solution found, back track	oMaze[row, Col] := StrReplace(oMaze[row, Col], "X")					; no solution found, back track	;~ Update(oMaze, oRoute)} ;-----------------------------------------------------------------------#IfWinActive, mazeRight::Left::Up::Down::if Solved	return if (A_ThisHotkey="Right") && (!InStr(oMaze[row,col], "R"))	oMaze[row, col] := StrReplace(oMaze[row, col], "X")		, col++if (A_ThisHotkey="Left") && (!InStr(oMaze[row,col], "L"))	oMaze[row, col] := StrReplace(oMaze[row, col], "X")		, col--if (A_ThisHotkey="Up") && (!InStr(oMaze[row,col], "T"))	oMaze[row, col] := StrReplace(oMaze[row, col], "X")		, row--if (A_ThisHotkey="Down") && (!InStr(oMaze[row,col], "B"))	oMaze[row, col] := StrReplace(oMaze[row, col], "X")		, row++ oMaze[row, col] .= "X"GuiControl,, EditGrid, % maze2text(oMaze) if (col = Width) && (row = Height){	Solved := true	oMaze[height, width] := StrReplace(oMaze[height, width], "X")	SleepTime := 0	gosub, solve	return}return#IfWinActive`
Outputs:
```+---+---+---+---+---+---+---+---+---+---+
| ¦¦¦¦¦ |     ¦¦¦¦¦ |     ¦¦¦¦¦¦¦¦¦¦¦¦¦ |
+---+ ¦ +---+ ¦ + ¦ +---+ ¦ +---+---+ ¦ +
|   | ¦ | ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦ | ¦¦¦¦¦ | ¦ |
+   + ¦ + ¦ +---+---+---+---+ ¦ + ¦ + ¦ +
| ¦¦¦¦¦ | ¦ | ¦¦¦¦¦¦¦¦¦¦¦¦¦ | ¦ | ¦¦¦¦¦ |
+ ¦ +---+ ¦ + ¦ +---+---+ ¦ + ¦ +---+---+
| ¦ |     ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦ | ¦¦¦¦¦ |   |
+ ¦ +---+---+---+ ¦ +---+---+---+ ¦ +   +
| ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦ |             ¦¦¦¦¦ |
+---+ ¦ + ¦ +---+---+   +---+---+---+ ¦ +
| ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦ |   | ¦¦¦¦¦ |   | ¦ |
+ ¦ +---+---+---+ ¦ +---+ ¦ + ¦ +   + ¦ +
| ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦ | ¦¦¦¦¦ | ¦ | ¦¦¦¦¦ |
+---+ ¦ + ¦ +---+---+ ¦ +---+ ¦ + ¦ +---+
| ¦¦¦¦¦ | ¦ | ¦¦¦¦¦¦¦¦¦ | ¦¦¦¦¦ | ¦ |   |
+ ¦ +---+ ¦ + ¦ +---+---+ ¦ +---+ ¦ +   +
| ¦ |     ¦¦¦¦¦     | ¦¦¦¦¦ |   | ¦¦¦¦¦ |
+ ¦ +---+---+---+---+ ¦ +---+   +---+ ¦ +
| ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ |             ¦ |
+---+---+---+---+---+---+---+---+---+---+```

## BBC BASIC

Maze generation code also included.

`      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`

## C

See Maze generation for combined gen/solve code.

## C++

Generator and solver combined. The generator is the same found in Maze generation

` #include <windows.h>#include <iostream>#include <string> //--------------------------------------------------------------------------------------------------using namespace std; //--------------------------------------------------------------------------------------------------const int BMP_SIZE = 512, CELL_SIZE = 8; //--------------------------------------------------------------------------------------------------enum directions { NONE, NOR = 1, EAS = 2, SOU = 4, WES = 8 }; //--------------------------------------------------------------------------------------------------class myBitmap{public:    myBitmap() : pen( NULL ) {}    ~myBitmap()    {	DeleteObject( pen );	DeleteDC( hdc );	DeleteObject( bmp );    }     bool create( int w, int h )    {	BITMAPINFO	bi;	ZeroMemory( &bi, sizeof( bi ) );	bi.bmiHeader.biSize	   = sizeof( bi.bmiHeader );	bi.bmiHeader.biBitCount	   = sizeof( DWORD ) * 8;	bi.bmiHeader.biCompression = BI_RGB;	bi.bmiHeader.biPlanes	   = 1;	bi.bmiHeader.biWidth	   =  w;	bi.bmiHeader.biHeight	   = -h; 	HDC dc = GetDC( GetConsoleWindow() );	bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 );	if( !bmp ) return false; 	hdc = CreateCompatibleDC( dc );	SelectObject( hdc, bmp );	ReleaseDC( GetConsoleWindow(), dc ); 	width = w; height = h; 	return true;    }     void clear()    {	ZeroMemory( pBits, width * height * sizeof( DWORD ) );    }     void setPenColor( DWORD clr )    {	if( pen ) DeleteObject( pen );	pen = CreatePen( PS_SOLID, 1, clr );	SelectObject( hdc, pen );    }     void saveBitmap( string path )    {	BITMAPFILEHEADER fileheader;	BITMAPINFO	 infoheader;	BITMAP		 bitmap;	DWORD		 wb; 	GetObject( bmp, sizeof( bitmap ), &bitmap ); 	DWORD* dwpBits = new DWORD[bitmap.bmWidth * bitmap.bmHeight];	ZeroMemory( dwpBits, bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ) );	ZeroMemory( &infoheader, sizeof( BITMAPINFO ) );	ZeroMemory( &fileheader, sizeof( BITMAPFILEHEADER ) ); 	infoheader.bmiHeader.biBitCount = sizeof( DWORD ) * 8;	infoheader.bmiHeader.biCompression = BI_RGB;	infoheader.bmiHeader.biPlanes = 1;	infoheader.bmiHeader.biSize = sizeof( infoheader.bmiHeader );	infoheader.bmiHeader.biHeight = bitmap.bmHeight;	infoheader.bmiHeader.biWidth = bitmap.bmWidth;	infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ); 	fileheader.bfType    = 0x4D42;	fileheader.bfOffBits = sizeof( infoheader.bmiHeader ) + sizeof( BITMAPFILEHEADER );	fileheader.bfSize    = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage; 	GetDIBits( hdc, bmp, 0, height, ( LPVOID )dwpBits, &infoheader, DIB_RGB_COLORS ); 	HANDLE file = CreateFile( path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL );	WriteFile( file, &fileheader, sizeof( BITMAPFILEHEADER ), &wb, NULL );	WriteFile( file, &infoheader.bmiHeader, sizeof( infoheader.bmiHeader ), &wb, NULL );	WriteFile( file, dwpBits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, NULL );	CloseHandle( file ); 	delete [] dwpBits;    }     HDC getDC() const     { return hdc; }    int getWidth() const  { return width; }    int getHeight() const { return height; } private:    HBITMAP bmp;    HDC	    hdc;    HPEN    pen;    void    *pBits;    int	    width, height;};//--------------------------------------------------------------------------------------------------class mazeGenerator{public:    mazeGenerator()    {	_world = 0; 	_bmp.create( BMP_SIZE, BMP_SIZE ); 	_bmp.setPenColor( RGB( 0, 255, 0 ) );     }     ~mazeGenerator() { killArray(); }     BYTE* getMaze() const { return _world; }     void create( int side )    {	_s = side;	generate();    } private:    void generate()    {	killArray();	_world = new BYTE[_s * _s];	ZeroMemory( _world, _s * _s );	_ptX = rand() % _s; _ptY = rand() % _s;	carve();    }     void carve()    {	while( true )	{	    int d = getDirection();	    if( d < NOR ) return; 	    switch( d )	    {		case NOR:		    _world[_ptX + _s * _ptY] |= NOR; _ptY--;		    _world[_ptX + _s * _ptY] = SOU | SOU << 4;		break;		case EAS:		    _world[_ptX + _s * _ptY] |= EAS; _ptX++;		    _world[_ptX + _s * _ptY] = WES | WES << 4;		break;		case SOU:		    _world[_ptX + _s * _ptY] |= SOU; _ptY++;		    _world[_ptX + _s * _ptY] = NOR | NOR << 4;		break;		case WES:		    _world[_ptX + _s * _ptY] |= WES; _ptX--;		    _world[_ptX + _s * _ptY] = EAS | EAS << 4;	    }	}    }     int getDirection()    {	int d = 1 << rand() % 4;	while( true )	{	    for( int x = 0; x < 4; x++ )	    {		if( testDir( d ) ) return d;		d <<= 1;		if( d > 8 ) d = 1;	    }	    d = ( _world[_ptX + _s * _ptY] & 0xf0 ) >> 4;	    if( !d ) return -1;	    switch( d )	    {		case NOR: _ptY--; break;		case EAS: _ptX++; break;		case SOU: _ptY++; break;		case WES: _ptX--; break;	    } 	    d = 1 << rand() % 4;        }    }     bool testDir( int d )    {	switch( d )	{	    case NOR: return ( _ptY - 1 > -1 && !_world[_ptX + _s * ( _ptY - 1 )] );	    case EAS: return ( _ptX + 1 < _s && !_world[_ptX + 1 + _s * _ptY] );	    case SOU: return ( _ptY + 1 < _s && !_world[_ptX + _s * ( _ptY + 1 )] );	    case WES: return ( _ptX - 1 > -1 && !_world[_ptX - 1 + _s * _ptY] );	}	return false;    }     void killArray() { if( _world ) delete [] _world; }     BYTE*    _world;    int      _s, _ptX, _ptY;    myBitmap _bmp;};//--------------------------------------------------------------------------------------------------class mazeSolver{public:    mazeSolver()          {	_bmp.create( BMP_SIZE, BMP_SIZE );	_pts = 0;    }     ~mazeSolver() { killPoints(); }     void solveIt( BYTE* maze, int size, int sX, int sY, int eX, int eY )    {	_lastDir = NONE;	_world = maze; _s = size; _sx = sX; _sy = sY; _ex = eX; _ey = eY; 	for( int y = 0; y < _s; y++ )	    for( int x = 0; x < _s; x++ )		_world[x + _s * y] &= 0x0f;         _world[_sx + _s * _sy] |= NOR << 4; 	killPoints();	_pts = new BYTE[_s * _s];	ZeroMemory( _pts, _s * _s ); 	findTheWay(); 	_sx = sX; _sy = sY;	display();    } private:    int invert( int d )    {	switch( d )	{	    case NOR: return SOU;	    case SOU: return NOR;	    case WES: return EAS;	    case EAS: return WES;	}	return NONE;    }     void updatePosition( int d )    {        switch( d )	{	    case NOR: _sy--; break;	    case EAS: _sx++; break;	    case SOU: _sy++; break;	    case WES: _sx--;	}    }     void findTheWay()    {	while( true )	{	    int d = getDirection();	    if( d < NOR ) return;	    _lastDir = invert( d );	    _world[_sx + _s * _sy] |= d;	    _pts[_sx + _s * _sy] = d;	    updatePosition( d );	    if( _sx == _ex && _sy == _ey ) return;	    _world[_sx + _s * _sy] |= _lastDir << 4;	}    }     int getDirection()    {	int d = 1 << rand() % 4;	while( true )	{	    for( int x = 0; x < 4; x++ )	    {		if( testDirection( d ) ) return d;		d <<= 1;		if( d > 8 ) d = 1;	    } 	    d = ( _world[_sx + _s * _sy] & 0xf0 ) >> 4;	    if( !d ) return -1;	    _pts[_sx + _s * _sy] = 0;	    updatePosition( d );	    _lastDir = invert( d );	    d = 1 << rand() % 4;	}    }     bool testDirection( int d )    {	if( d == _lastDir || !( _world[_sx + _s * _sy] & d ) ) return false;	switch( d )	{	    case NOR: 		return _sy - 1 > -1 && !( _world[_sx + _s * ( _sy - 1 )] & 0xf0 );	    case EAS: 		return _sx + 1 < _s && !( _world[_sx + 1 + _s * _sy] & 0xf0 );	    case SOU: 		return _sy + 1 < _s && !( _world[_sx + _s * ( _sy + 1 )] & 0xf0 );	    case WES: 		return _sx - 1 > -1 && !( _world[_sx - 1 + _s * _sy] & 0xf0 );	}	return false;    }     void display()    {	_bmp.setPenColor( RGB( 0, 255, 0 ) );	_bmp.clear();	HDC dc = _bmp.getDC();	for( int y = 0; y < _s; y++ )	{	    int yy = y * _s;	    for( int x = 0; x < _s; x++ )	    {		BYTE b = _world[x + yy];		int nx = x * CELL_SIZE, 		    ny = y * CELL_SIZE; 		if( !( b & NOR ) )		{		    MoveToEx( dc, nx, ny, NULL );		    LineTo( dc, nx + CELL_SIZE + 1, ny );		}		if( !( b & EAS ) )		{		    MoveToEx( dc, nx + CELL_SIZE, ny, NULL );		    LineTo( dc, nx + CELL_SIZE, ny + CELL_SIZE + 1 );		}		if( !( b & SOU ) )		{		    MoveToEx( dc, nx, ny + CELL_SIZE, NULL );		    LineTo( dc, nx + CELL_SIZE + 1, ny + CELL_SIZE );		}		if( !( b & WES ) )		{		    MoveToEx( dc, nx, ny, NULL );		    LineTo( dc, nx, ny + CELL_SIZE + 1 );		}	    }	} 	drawEndPoints( dc );	_bmp.setPenColor( RGB( 255, 0, 0 ) ); 	for( int y = 0; y < _s; y++ )	{	    int yy = y * _s;	    for( int x = 0; x < _s; x++ )	    {		BYTE d = _pts[x + yy];		if( !d ) continue; 		int nx = x * CELL_SIZE + 4, 		    ny = y * CELL_SIZE + 4; 		MoveToEx( dc, nx, ny, NULL );		switch( d )		{		    case NOR: LineTo( dc, nx, ny - CELL_SIZE - 1 ); break;		    case EAS: LineTo( dc, nx + CELL_SIZE + 1, ny ); break;		    case SOU: LineTo( dc, nx, ny + CELL_SIZE + 1 ); break;		    case WES: LineTo( dc, nx - CELL_SIZE - 1, ny ); break;		}	    }	} 	_bmp.saveBitmap( "f:\\rc\\maze_s.bmp" );	BitBlt( GetDC( GetConsoleWindow() ), 10, 60, BMP_SIZE, BMP_SIZE, _bmp.getDC(), 0, 0, SRCCOPY );    }     void drawEndPoints( HDC dc )    {	RECT rc;	int x = 1 + _sx * CELL_SIZE, y = 1 + _sy * CELL_SIZE;	SetRect( &rc, x, y, x + CELL_SIZE - 1, y + CELL_SIZE - 1 );	FillRect( dc, &rc, ( HBRUSH )GetStockObject( WHITE_BRUSH ) );	x = 1 + _ex * CELL_SIZE, y = 1 + _ey * CELL_SIZE;	SetRect( &rc, x, y, x + CELL_SIZE - 1, y + CELL_SIZE - 1 );	FillRect( dc, &rc, ( HBRUSH )GetStockObject( WHITE_BRUSH ) );    }     void killPoints() { if( _pts ) delete [] _pts; }     BYTE*    _world, *_pts;    int      _s, _sx, _sy, _ex, _ey, _lastDir;    myBitmap _bmp;};//--------------------------------------------------------------------------------------------------int main( int argc, char* argv[] ){    ShowWindow( GetConsoleWindow(), SW_MAXIMIZE );    srand( GetTickCount() );     mazeGenerator mg;    mazeSolver ms;    int s;    while( true )    {	cout << "Enter the maze size, an odd number bigger than 2 ( 0 to QUIT ): "; cin >> s;	if( !s ) return 0;	if( !( s & 1 ) ) s++;	if( s >= 3 ) 	{	    mg.create( s );	    int sx, sy, ex, ey;	    while( true )	    {		sx = rand() % s; sy = rand() % s;		ex = rand() % s; ey = rand() % s;		if( ex != sx || ey != sy ) break;	    }	    ms.solveIt( mg.getMaze(), s, sx, sy, ex, ey );	    cout << endl;	}	system( "pause" );	system( "cls" );    }    return 0;}//-------------------------------------------------------------------------------------------------- `

## Clojure

`(ns small-projects.find-shortest-way  (:require [clojure.string :as str])) ;Misk functions(defn cell-empty? [maze coords]  (= :empty (get-in maze coords))) (defn wall? [maze coords]  (= :wall (get-in maze coords))) (defn track? [maze coords]  (= :track (get-in maze coords))) (defn get-neighbours [maze [y x cell]]  [[y (dec x)] [(inc y) x] [y (inc x)] [(dec y) x]]) (defn get-difference [coll1 filter-coll]  (filter #(not (contains? filter-coll %)) coll1)) (defn get-empties [maze cell]      (->> (get-neighbours maze cell)           (filter (partial cell-empty? maze)))) (defn possible-ways [maze cell filter-coll]  (-> (get-empties maze cell)      (get-difference filter-coll))) (defn replace-cells [maze coords v]  (if (empty? coords)    maze    (recur (assoc-in maze (first coords) v) (rest coords) v))) ;Print and parse functions(def cell-code->str  ["  " "  " "  " "  " "· " "╵ " "╴ " "┘ "   "  " "  " "  " "  " "╶─" "└─" "──" "┴─"   "  " "  " "  " "  " "╷ " "│ " "┐ " "┤ "   "  " "  " "  " "  " "┌─" "├─" "┬─" "┼─"   "  " "  " "  " "  " "■ " "╹ " "╸ " "┛ "   "  " "  " "  " "  " "╺━" "┗━" "━━" "┻━"   "  " "  " "  " "  " "╻ " "┃ " "┓ " "┫ "   "  " "  " "  " "  " "┏━" "┣━" "┳━" "╋━"   "  "]) (defn get-cell-code [maze coords]  (let [mode (if (track? maze coords) 1 0)        check (if (zero? mode) wall? track?)]    (transduce      (comp        (map (partial check maze))        (keep-indexed (fn [idx test] (when test idx)))        (map (partial bit-shift-left 1)))      (completing bit-or)      (bit-shift-left mode 5)      (sort (conj (get-neighbours maze coords) coords))))) (defn code->str [cell-code]  (nth cell-code->str cell-code)) (defn maze->str-symbols [maze]  (for [y (range (count maze))]    (for [x (range (count (nth maze y)))]      (code->str (get-cell-code maze [y x]))))) (defn maze->str [maze]  (->> (maze->str-symbols maze)       (map str/join)       (str/join "\n"))) (defn parse-pretty-maze [maze-str]  (->> (str/split-lines maze-str)       (map (partial take-nth 2))       (map (partial map #(if (= \space %) :empty :wall)))       (map vec)       (vec))) ;Core(defn find-new-border [maze border old-border] (apply conj (map (fn [cell]                    (zipmap (possible-ways maze cell (conj border old-border))                            (repeat cell)))                  (keys border)))) (defn backtrack [visited route]  (let [cur-cell (get visited (first route))]    (if (= cur-cell :start)        route        (recur visited (conj route cur-cell))))) (defn breadth-first-search [maze start-cell end-cell]    (loop [visited {start-cell :start}           border {start-cell :start}           old-border {start-cell :start}]     (if (contains? old-border end-cell)         (backtrack visited (list end-cell))         (recur           (conj visited border)           (find-new-border maze border old-border)           border)))) (def maze (parse-pretty-maze maze-str)) (def solved-maze  (replace-cells maze (breadth-first-search maze [1 1] [19 19]) :track)) (println (maze->str solved-maze))`
Input:
```┌───────────┬───────┬───────┬───────────┐
│           │       │       │           │
│   ╶───────┘   ╷   ╵   ╷   ╵   ┌───╴   │
│               │       │       │       │
│   ╶───────┬───┴───┬───┴───┬───┘   ╷   │
│           │       │       │       │   │
├───────╴   │   ╷   ╵   ╷   │   ┌───┘   │
│           │   │       │   │   │       │
│   ┌───┬───┘   ├───────┤   │   ├───────┤
│   │   │       │       │   │   │       │
│   ╵   ╵   ╶───┴───┐   │   │   ╵   ╷   │
│                   │   │   │       │   │
├───────────────┐   ╵   │   │   ╶───┤   │
│               │       │   │       │   │
│   ╶───┐   ┌───┴───╴   │   │   ┌───┘   │
│       │   │           │   │   │       │
├───╴   │   │   ╶───┬───┤   └───┤   ╶───┤
│       │   │       │   │       │       │
│   ╶───┤   └───╴   ╵   └───┐   └───╴   │
│       │                   │           │
└───────┴───────────────────┴───────────┘  ```
Output:
```┌───────────┬───────┬───────┬───────────┐
│ ╻         │       │       │           │
│ ┃ ╶───────┘   ╷   ╵   ╷   ╵   ┌───╴   │
│ ┃             │       │       │       │
│ ┃ ╶───────┬───┴───┬───┴───┬───┘   ╷   │
│ ┗━━━━━━━┓ │ ┏━━━┓ │ ┏━━━┓ │       │   │
├───────╴ ┃ │ ┃ ╷ ┃ ╵ ┃ ╷ ┃ │   ┌───┘   │
│ ┏━━━━━━━┛ │ ┃ │ ┗━━━┛ │ ┃ │   │       │
│ ┃ ┌───┬───┘ ┃ ├───────┤ ┃ │   ├───────┤
│ ┃ │   │ ┏━━━┛ │       │ ┃ │   │       │
│ ┃ ╵   ╵ ┃ ╶───┴───┐   │ ┃ │   ╵   ╷   │
│ ┗━━━━━━━┛         │   │ ┃ │       │   │
├───────────────┐   ╵   │ ┃ │   ╶───┤   │
│               │       │ ┃ │       │   │
│   ╶───┐   ┌───┴───╴   │ ┃ │   ┌───┘   │
│       │   │           │ ┃ │   │       │
├───╴   │   │   ╶───┬───┤ ┃ └───┤   ╶───┤
│       │   │       │   │ ┗━━━┓ │       │
│   ╶───┤   └───╴   ╵   └───┐ ┃ └───╴   │
│       │                   │ ┗━━━━━━━╸ │
└───────┴───────────────────┴───────────┘ ```

## D

 This example is incorrect. Please fix the code and remove this message.Details: Is output double spaced, with only two dots above the E rather than 4, see comment Pete Lomax (talk) 06:09, 19 March 2017 (UTC)

This entry reads a maze generated by http://rosettacode.org/wiki/Maze_generation#D and chooses two random start-end points.

`import std.stdio, std.random, std.string, std.array, std.algorithm,       std.file, std.conv; enum int cx = 4, cy = 2; // Cell size x and y.enum int cx2 = cx / 2, cy2 = cy / 2;enum pathSymbol = '.';struct V2 { int x, y; } bool solveMaze(char[][] maze, in V2 s, in V2 end) pure nothrow @safe @nogc {    if (s == end)        return true;     foreach (immutable 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] == ' ') {//Would this help?//          maze[s.y + (d.y / 2)][s.x + (d.x / 2)] = pathSymbol;            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 = "maze.txt".File.byLine.map!(r => r.chomp.dup).array;    immutable h = (maze.length.signed - 1) / cy;    assert (h > 0);    immutable w = (maze[0].length.signed - 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))        return "No solution path found.".writeln;    maze[start.y][start.x] = 'S';    maze[end.y][end.x] = 'E';    writefln("%-(%s\n%)", maze);}`
Output:
```+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |               |           | . . . . . . . . .     |
+   +   +---+---+   +   +---+   + . +---+---+---+ . +   +
|               |           |   | . . . |       | . |   |
+---+---+---+---+---+---+---+   +---+ . +---+   + . +---+
|                   |       |       | . . . . . | E     |
+   +---+---+---+   +   +   +---+   +---+---+ . +---+---+
|       | . . . |   |   |               |   | . . . |   |
+---+   + . + . +   +   +---+---+---+   +   +---+ . +   +
|       | . | . |       | . . . |           | . . . |   |
+   +---+ . + . +---+---+ . + . +---+---+---+ . +---+   +
| . . . . . | . | . . . . . | . . . . . . . | . . . . . |
+ . +---+---+ . + . +---+---+---+---+---+ . +---+---+ . +
| . . . |   | . . . |   |               | .         | . |
+---+ . +   +---+---+   +   +---+   +   + . +---+---+ . +
|   | . . . . . . . |       |       |   | . | . . . . . |
+   +---+---+---+ . +   +---+   +---+   + . + . +---+---+
|   | . . . . . . . |   |       |   |   | . . . |       |
+   + . +---+---+---+---+   +---+   +   +---+---+   +   +
|     . . . . . . S         |                       |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+```

## 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`
Output example (for 10x10 maze):
```+---+---+---+---+---+---+---+---+---+---+
|       |               |       |       |
+   +---+   +---+---+   +   +   +---+   +
|       |   |       |       |   |   |   |
+---+   +   +---+   +---+---+   +   +   +
|       |       |       |   |       |   |
+   +---+---+   +   +   +   +---+---+   +
|   |       |   |   |               |   |
+   +   +   +   +   +---+---+---+   +   +
|       |       |   |       |       |   |
+   +---+---+---+   +   +---+   +---+   +
|       |           |   |       |       |
+---+   +---+   +---+   +   +---+   +   +
|   |   |       |           |       |   |
+   +   +   +---+   +---+---+---+---+   +
|   |   |   |   |                   |   |
+   +   +   +   +---+---+---+---+   +   +
|   |   |   |           |       |   |   |
+   +   +   +   +---+---+   +   +   +   +
|           |               |           |
+---+---+---+---+---+---+---+---+---+---+

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

## Erlang

Using the maze from Maze_generation. When the path splits each possibility gets its own process that checks if it is the correct one or a dead end. It is intentional that the receive statement in loop_stop/5 only selects successful result.

` -module( maze_solving ). -export( [task/0] ). cells( {Start_x, Start_y}, {Stop_x, Stop_y}, Maze ) ->    Start_pid = maze:cell_pid( Start_x, Start_y, Maze ),    Stop_pid =  maze:cell_pid( Stop_x,  Stop_y, Maze ),    {ok, Cells} = loop( Start_pid, Stop_pid, maze:cell_accessible_neighbours(Start_pid), [Start_pid] ),    Cells. task() ->    Max_x = 16,    Max_y = 8,    Maze = maze:generation( Max_x, Max_y ),    Start_x = random:uniform( Max_x ),    Start_y = random:uniform( Max_y ),    Stop_x = random:uniform( Max_x ),    Stop_y = random:uniform( Max_y ),    Cells = cells( {Start_x, Start_y}, {Stop_x, Stop_y}, Maze ),    [maze:cell_content_set(X, ".") || X <- Cells],    maze:cell_content_set( maze:cell_pid(Start_x, Start_y, Maze), "S" ),    maze:cell_content_set( maze:cell_pid(Stop_x, Stop_y, Maze), "G" ),    maze:display( Maze ),    maze:stop( Maze ).   loop( _Start, _Stop, [], _Acc) -> {error, dead_end};loop( _Start, Stop, [Stop], Acc ) -> {ok, lists:reverse( [Stop | Acc] )};loop( Start, Stop, [Next], [Previous | _T]=Acc ) -> loop( Start, Stop, lists:delete(Previous, maze:cell_accessible_neighbours(Next)), [Next | Acc] );loop( Start, Stop, Nexts, Acc ) -> loop_stop( lists:member(Stop, Nexts), Start, Stop, Nexts, Acc ). loop_stop( true, _Start, Stop, _Nexts, Acc ) -> {ok, lists:reverse( [Stop | Acc] )};loop_stop( false, Start, Stop, Nexts, Acc ) ->        My_pid = erlang:self(),        [erlang:spawn( fun() -> My_pid ! loop( Start, Stop, [X], Acc ) end ) || X <- Nexts],        receive        {ok, Cells} -> {ok, Cells}        end. `
Output:
```8> maze_solving:task().
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|     .   .   .   . | .   .   .   . | .   .   .   . |           |
+---+   +---+---+   +   +---+---+   +   +---+---+   +   +---+   +
| .   . |       | .   . |       | .   . |       | .   . |       |
+   +---+   +   +---+---+   +---+---+---+   +   +---+   +---+   +
| . |       |           |                   |       | . |   |   |
+   +---+   +---+---+   +   +   +---+---+   +---+---+   +   +---+
| .   . |   |       |   |   |   |           | .   . | . |       |
+   +   +   +   +   +---+   +   +---+---+---+   +   +   +---+   +
|   | . |       |           |             S   . | .   .     |   |
+---+   +---+---+   +---+---+---+   +---+---+---+   +---+---+   +
| .   . | .   . |       | .   . |   |           |   |           |
+   +   +   +   +---+   +   +   +   +   +---+   +   +   +---+---+
| . |   | . | . |       | . | . |   | G   . |   |   |           |
+   +---+   +   +---+---+   +   +---+---+   +   +---+---+---+   +
| .   .   . | .   .   .   . | .   .   .   . |                   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```

## Frege

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.

`module MazeSolver where import frege.IOimport Data.Maybe -- given two points, returns the average of themaverage :: (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)) -> BoolnotBlocked 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 positionsubstitute :: [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 characterssubstituteString :: String -> Int -> String -> StringsubstituteString 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 mazedraw :: [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 solvedtryMoves :: [String] -> (Int, Int) -> [((Int, Int), (Int, Int))] -> Maybe [String]tryMoves _ _ [] = NothingtryMoves 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 mazesolve' 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 outputmain _ = do  isin  <- stdin  isrin <- InputStreamReader.new isin  brin  <- BufferedReader.fromISR isrin  lns <- BufferedReader.getlines brin  printStr \$ unlines \$ fromMaybe ["can't solve"] \$ solve lns`
Output:
```+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| * |         * * * * * |       |       |                   |       |       |
+ * +---+---+ * +---+ * +---+   +   +   +   +---+---+---+   +   +   +   +   +
| * | * * * * * |   | * |       |   |       | * * * * * |       |       |   |
+ * + * +---+---+   + * +   +---+   +---+---+ * +---+ * +   +---+---+---+   +
| * * * |       |   | * |   |       | * * * * * | * * * |   | * * * * * |   |
+---+---+   +   +   + * +   +   +---+ * +---+---+ * +---+---+ * +---+ * +   +
|           |       | * |       |   | * |   | * * * | * * * * * | * * * |   |
+   +   +---+---+---+ * +   +---+   + * +   + * +---+ * +---+---+ * +---+   +
|   |   | * * * * * * * |           | * |     * * * * * |       | * * * * * |
+   +   + * +---+---+---+---+---+---+ * +---+---+---+---+   +   +---+---+ * +
|   |   | * * * | * * * * * | * * * | * * * | * * * |       |           | * |
+   +---+---+ * + * +---+ * + * + * +---+ * + * + * +---+   +---+   +   + * +
|   |       | * | * | * * * | * | * * * | * * * | * * * |   |   |   |   | * |
+   +   +   + * + * + * +---+ * +---+ * +---+---+---+ * +   +   +   +---+ * +
|       |     * * * | * * * * * |     * * * * * * * * * |       |         * |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
runtime 0.249 wallclock seconds.
```

## Go

Generates maze, picks start and finish cells randomly, solves, prints.

`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'}`
Example output
:
```+---+---+---+---+---+---+---+
|           | v < < < < < < |
+   +---+   + v +   +---+ ^ +
|       | F < < |   |     ^ |
+---+---+---+---+   +---+ ^ +
|               |       | ^ |
+   +---+---+   +---+   + ^ +
|   |                   | S |
+---+---+---+---+---+---+---+
```

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.

`#!/usr/bin/runhaskell import Data.Maybe (fromMaybe) -- given two points, returns the average of themaverage :: (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)) -> BoolnotBlocked 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 mazedraw :: [String] -> (Int, Int) -> [String]draw maze (x, y) =  let row = maze !! y  in substitute maze y \$ substitute row x '*' -- 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 solvedtryMoves :: [String]         -> (Int, Int)         -> [((Int, Int), (Int, Int))]         -> Maybe [String]tryMoves _ _ [] = NothingtryMoves 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 mazesolve_ 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 outputmain =  let main_ = unlines . fromMaybe ["can_t solve"] . solve . lines  in interact main_ `
Output:
```+---+---+---+---+---+---+---+---+---+---+---+
| * |           |               |           |
+ * +   +---+   +   +---+   +---+   +---+   +
| * |       |   |       |   |           |   |
+ * +---+   +   +---+   +---+   +---+---+   +
| *         |       |       |   |   |       |
+ * +---+---+---+   +---+   +   +   +   +   +
| * * * * * * * |       |           |   |   |
+---+---+---+ * +---+   +---+---+---+   +   +
|           | * * * |   |           |   |   |
+   +---+   +---+ * +   +   +---+   +   +---+
|       |   | * * * |       |   |   |       |
+---+---+   + * +---+---+---+   +   +---+   +
|           | * * * * * |       |       |   |
+   +---+---+---+---+ * +---+   +---+---+   +
|                     * * * * * * * * * * * |
+---+---+---+---+---+---+---+---+---+---+---+
```

## Icon and Unicon

The following code works with the solution from Maze Generation.

20x20 solved start @ red

Replace the main with this:

`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`

And include this after the Generator and Display procedures.

`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.windowmaze := mz.mazeWAttrib("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 mzend`

The following Unicon-only solution is a variant of the above. It shares the same maze generation code and maze display code with the above but spawns threads to parallelize the searching. The algorithm runs each path to a dead end, a target, or a length greater than the current shortest path to a target and works if there are multiple target cells, multiple paths to those targets, or cyclic paths. The shortest solution path is then marked and displayed.

`global showMice import Utils	# To get 'Args' singleton class procedure main(A)   Args(A)   if \Args().get("help","yes") then helpMesg()   showMice := Args().get("showmice","yes") # Show movements of all mice   mh := Args().get("rows") | 32            # Maze height (rows)   mw := Args().get("cols") | 48            # Maze width (columns)    mz := DisplayMaze(GenerateMaze(mh,mw))   # Build and show maze    QMouse(mz.maze,findStart(mz.maze),&null,0)   # Start first quantum mouse   waitForCompletion() # block until all quantum mice have finished    # Mark the best path into the maze and display it.   if showPath(mz.maze) then DisplayMazeSolution(mz) else write("No path found!")end procedure helpMesg()    write(&errout,"Usage: qSolve [--showmice] [--cols=C] [--rows=R]")    write(&errout,"\twhere:")    write(&errout,"\t\t--showmice # displays all mice paths as they search")    write(&errout,"\t\t--cols=C   # sets maze width to C (default 16) columns")    write(&errout,"\t\t--rows=R   # sets maze height to R (default 12) rows")    stop()end # A "Quantum-mouse" for traversing mazes. Each mouse lives for just one cell, but#   can spawn other mice to search from adjoining cells. global qMice, bestMouse, bestMouseLock, region, qMiceEmptyrecord Position(r,c) # Must match values used in maze generation!\$define FINISH 64 # exit\$define START  32 # entrance\$define PATH  128 \$define SEEN   16 # bread crumbs for generator\$define NORTH   8 # sides ...\$define EAST    4\$define SOUTH   2\$define WEST    1\$define EMPTY   0 # like new class QMouse(maze, loc, parent, len, val)    method getLoc(); return loc; end   method getParent(); return \parent; end   method getLen(); return len; end   method atEnd();   return EMPTY ~= iand(val, FINISH); end   method goNorth(); if EMPTY ~= iand(val,NORTH) then return visit(loc.r-1, loc.c); end   method goSouth(); if EMPTY ~= iand(val,SOUTH) then return visit(loc.r+1, loc.c); end   method goEast();  if EMPTY ~= iand(val,EAST)  then return visit(loc.r, loc.c+1); end   method goWest();  if EMPTY ~= iand(val,WEST)  then return visit(loc.r, loc.c-1); end    method visit(r,c)       critical region[r,c]: if EMPTY = iand(maze[r,c],SEEN) then {           if /bestMouse | (len <= bestMouse.getLen()) then { # Keep going?               mark(maze, r,c)               unlock(region[r,c])               return Position(r,c)               }           }   end initially (m, l, p, n)    initial {   # Construct critical region mutexes and completion condvar        qMice := mutex(set())        qMiceEmpty := condvar()        bestMouseLock := mutex()        region := list(*m)            # Minimize critical region size        every r := 1 to *m do region[r] := list(*m[1])        every !!region := mutex()        }    maze := m    loc := l    parent := p    len := n+1    val := maze[loc.r,loc.c] | fail   # Fail if outside maze    insert(qMice, self)    thread {        if atEnd() then {            critical bestMouseLock:                if /bestMouse | (len < bestMouse.getLen()) then bestMouse := self            }        else {         # Spawn more mice to look for finish            QMouse(maze, goNorth(), self, len)            QMouse(maze, goSouth(), self, len)            QMouse(maze, goEast(), self, len)            QMouse(maze, goWest(), self, len)            }         delete(qMice, self)        if *qMice=0 then signal(qMiceEmpty)        }end procedure mark(maze, r,c)    ior(maze[r,c],SEEN)    if \showMice then markCell(r,c,"grey",5)    return Position(r,c)end procedure clearMaze(maze)  # Clear out dregs from maze creation    every r := 1 to *maze & c := 1 to *maze[1] do  # remove breadcrumbs        maze[r,c] := iand(maze[r,c],NORTH+EAST+SOUTH+WEST+START+FINISH)end procedure findStart(maze)  # Anywhere in maze    clearMaze(maze)                                # Remove breadcrumbs    every r := 1 to *maze & c := 1 to *maze[1] do  # Locate START cell        if EMPTY ~= iand(maze[r,c],START) then return mark(maze, r,c)end procedure showPath(maze)    if path := \bestMouse then {   # Mark it in maze       repeat {           loc := path.getLoc()           maze[loc.r,loc.c] +:= PATH           path := \path.getParent() | break           }       return       }end procedure waitForCompletion()   critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)end`

## J

Due to reports that the program failed, the generation and solver are shown together. The display verb was extended to include a dyadic definition. The complete program was tested with j 8.0.2 on linux using no profile, the command \$ ijconsole -jprofile

` maze=:4 :0  assert.0<:n=.<:x*y  horiz=. 0\$~x,y-1  verti=. 0\$~(x-1),y  path=.,:here=. ?x,y  unvisited=.0 (<here+1)} 0,0,~|:0,0,~1\$~y,x  while.n do.    neighbors=. here+"1 (,-)=0 1    neighbors=. neighbors #~ (<"1 neighbors+1) {unvisited    if.#neighbors do.      n=.n-1      next=. ({~ [email protected]#) neighbors      unvisited=.0 (<next+1)} unvisited      if.{.next=here      do. horiz=.1 (<-:here+next-0 1)} horiz      else. verti=. 1 (<-:here+next-1 0)} verti end.      path=.path,here=.next    else.      here=.{:path      path=.}:path    end.  end.  horiz;verti) NB. source Dijkstra_equal_weights graphNB. 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;2NB. 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 =. }[email protected][email protected]:>  ew =. (,.&0 ,: 0&,.)@>@{.  NB. east west doors  ns =. (, &0 ,: 0&, )@>@{:  cell_offsets =. 1 _1 1 _1 * 2 # 1 , {:@shape  cell_numbers =. [email protected]  neighbors =. (cell_numbers +"_ _1 cell_offsets *"_1 (ew , ns))y  graph =. (|:@(,/"_1) <@-."1 0 ,@[email protected])neighbors NB. list of boxed neighbors  NB. solve it  path , > {: 0 Dijkstra_equal_weights graph) display=:3 :0  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&[email protected]<[email protected](%&columns) ,.  2 4&[email protected](columns&|))x  'o' cells } a  NB. exercise, replace cells with a gerund to draw arrows on the path.) `
Example:
```   4 (display~ solve)@maze 20
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 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
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```

## 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]);    }}`
Output:
```+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| * |           |               |         * * * * * |           |
+ * +   +   +---+   +---+---+   +   +---+ * +---+ * +---+   +---+
| * |   |       |   | * * * |   |       | * * * | * * * |       |
+ * +   +---+   +   + * + * +   +---+   +---+ * +---+ * +---+   +
| * |       |       | * | * |           | * * * |   | * |       |
+ * +---+---+   +---+ * + * +---+---+   + * +---+   + * +   +   +
| * | * * * |       | * | * | * * * |   | * |       | * |   |   |
+ * + * + * +---+   + * + * + * + * +---+ * +---+   + * +   +---+
| * * * | * |       | * | * * * | * * * * * |       | * |       |
+---+---+ * +---+---+ * +---+---+---+---+---+   +---+ * +---+   +
|       | * * * | * * * |               |           | * * * |   |
+   +---+---+ * + * +---+   +---+---+   +   +---+   +---+ * +   +
| * * * * * * * | * |   |           |   |   |   |       | * * * |
+ * +---+---+---+ * +   +   +---+   +---+   +   +   +---+---+ * +
| * * * * * * * * * |           |               |             * |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```

### Animated version

Uses code from maze generation task

Works with: Java version 8
`import java.awt.*;import java.awt.event.*;import java.awt.geom.Path2D;import java.util.*;import javax.swing.*; public class MazeGenerator extends JPanel {    enum Dir {        N(1, 0, -1), S(2, 0, 1), E(4, 1, 0), W(8, -1, 0);        final int bit;        final int dx;        final int dy;        Dir opposite;         // use the static initializer to resolve forward references        static {            N.opposite = S;            S.opposite = N;            E.opposite = W;            W.opposite = E;        }         Dir(int bit, int dx, int dy) {            this.bit = bit;            this.dx = dx;            this.dy = dy;        }    };    final int nCols;    final int nRows;    final int cellSize = 25;    final int margin = 25;    final int[][] maze;    LinkedList<Integer> solution;     public MazeGenerator(int size) {        setPreferredSize(new Dimension(650, 650));        setBackground(Color.white);        nCols = size;        nRows = size;        maze = new int[nRows][nCols];        solution = new LinkedList<>();        generateMaze(0, 0);         addMouseListener(new MouseAdapter() {            @Override            public void mousePressed(MouseEvent e) {                new Thread(() -> {                    solve(0);                }).start();            }        });    }     @Override    public void paintComponent(Graphics gg) {        super.paintComponent(gg);        Graphics2D g = (Graphics2D) gg;        g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,                RenderingHints.VALUE_ANTIALIAS_ON);         g.setStroke(new BasicStroke(5));        g.setColor(Color.black);         // draw maze        for (int r = 0; r < nRows; r++) {            for (int c = 0; c < nCols; c++) {                 int x = margin + c * cellSize;                int y = margin + r * cellSize;                 if ((maze[r][c] & 1) == 0) // N                    g.drawLine(x, y, x + cellSize, y);                 if ((maze[r][c] & 2) == 0) // S                    g.drawLine(x, y + cellSize, x + cellSize, y + cellSize);                 if ((maze[r][c] & 4) == 0) // E                    g.drawLine(x + cellSize, y, x + cellSize, y + cellSize);                 if ((maze[r][c] & 8) == 0) // W                    g.drawLine(x, y, x, y + cellSize);            }        }         // draw pathfinding animation        int offset = margin + cellSize / 2;         Path2D path = new Path2D.Float();        path.moveTo(offset, offset);         for (int pos : solution) {            int x = pos % nCols * cellSize + offset;            int y = pos / nCols * cellSize + offset;            path.lineTo(x, y);        }         g.setColor(Color.orange);        g.draw(path);         g.setColor(Color.blue);        g.fillOval(offset - 5, offset - 5, 10, 10);         g.setColor(Color.green);        int x = offset + (nCols - 1) * cellSize;        int y = offset + (nRows - 1) * cellSize;        g.fillOval(x - 5, y - 5, 10, 10);     }     void generateMaze(int r, int c) {        Dir[] dirs = Dir.values();        Collections.shuffle(Arrays.asList(dirs));        for (Dir dir : dirs) {            int nc = c + dir.dx;            int nr = r + dir.dy;            if (withinBounds(nr, nc) && maze[nr][nc] == 0) {                maze[r][c] |= dir.bit;                maze[nr][nc] |= dir.opposite.bit;                generateMaze(nr, nc);            }        }    }     boolean withinBounds(int r, int c) {        return c >= 0 && c < nCols && r >= 0 && r < nRows;    }     boolean solve(int pos) {        if (pos == nCols * nRows - 1)            return true;         int c = pos % nCols;        int r = pos / nCols;         for (Dir dir : Dir.values()) {            int nc = c + dir.dx;            int nr = r + dir.dy;            if (withinBounds(nr, nc) && (maze[r][c] & dir.bit) != 0                    && (maze[nr][nc] & 16) == 0) {                 int newPos = nr * nCols + nc;                 solution.add(newPos);                maze[nr][nc] |= 16;                 animate();                 if (solve(newPos))                    return true;                 animate();                 solution.removeLast();                maze[nr][nc] &= ~16;            }        }         return false;    }     void animate() {        try {            Thread.sleep(50L);        } catch (InterruptedException ignored) {        }        repaint();    }     public static void main(String[] args) {        SwingUtilities.invokeLater(() -> {            JFrame f = new JFrame();            f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);            f.setTitle("Maze Generator");            f.setResizable(false);            f.add(new MazeGenerator(24), BorderLayout.CENTER);            f.pack();            f.setLocationRelativeTo(null);            f.setVisible(true);        });    }}`

## JavaScript

Animated: generating and solving.
To start solving, click to choose a 'start' and an 'end' points.
Go here to see it in action.

` var ctx, wid, hei, cols, rows, maze, stack = [], start = {x:-1, y:-1}, end = {x:-1, y:-1}, grid = 8;function drawMaze() {    for( var i = 0; i < cols; i++ ) {        for( var j = 0; j < rows; j++ ) {            switch( maze[i][j] ) {                case 0: ctx.fillStyle = "black"; break;                case 1: ctx.fillStyle = "green"; break;                case 2: ctx.fillStyle = "red"; break;                case 3: ctx.fillStyle = "yellow"; break;                case 4: ctx.fillStyle = "#500000"; break;            }            ctx.fillRect( grid * i, grid * j, grid, grid  );        }    }}function getFNeighbours( sx, sy, a ) {    var n = [];    if( sx - 1 > 0 && maze[sx - 1][sy] == a ) {        n.push( { x:sx - 1, y:sy } );    }    if( sx + 1 < cols - 1 && maze[sx + 1][sy] == a ) {        n.push( { x:sx + 1, y:sy } );    }    if( sy - 1 > 0 && maze[sx][sy - 1] == a ) {        n.push( { x:sx, y:sy - 1 } );    }    if( sy + 1 < rows - 1 && maze[sx][sy + 1] == a ) {        n.push( { x:sx, y:sy + 1 } );    }    return n;}function solveMaze() {    if( start.x == end.x && start.y == end.y ) {        for( var i = 0; i < cols; i++ ) {            for( var j = 0; j < rows; j++ ) {                switch( maze[i][j] ) {                    case 2: maze[i][j] = 3; break;                    case 4: maze[i][j] = 0; break;                }            }        }        drawMaze();        return;    }    var neighbours = getFNeighbours( start.x, start.y, 0 );    if( neighbours.length ) {        stack.push( start );        start = neighbours[0];        maze[start.x][start.y] = 2;    } else {        maze[start.x][start.y] = 4;        start = stack.pop();    }     drawMaze();    requestAnimationFrame( solveMaze );}function getCursorPos( event ) {    var rect = this.getBoundingClientRect();    var x = Math.floor( ( event.clientX - rect.left ) / grid ),         y = Math.floor( ( event.clientY - rect.top  ) / grid );    if( maze[x][y] ) return;    if( start.x == -1 ) {        start = { x: x, y: y };    } else {        end = { x: x, y: y };        maze[start.x][start.y] = 2;        solveMaze();    }}function getNeighbours( sx, sy, a ) {    var n = [];    if( sx - 1 > 0 && maze[sx - 1][sy] == a && sx - 2 > 0 && maze[sx - 2][sy] == a ) {        n.push( { x:sx - 1, y:sy } ); n.push( { x:sx - 2, y:sy } );    }    if( sx + 1 < cols - 1 && maze[sx + 1][sy] == a && sx + 2 < cols - 1 && maze[sx + 2][sy] == a ) {        n.push( { x:sx + 1, y:sy } ); n.push( { x:sx + 2, y:sy } );    }    if( sy - 1 > 0 && maze[sx][sy - 1] == a && sy - 2 > 0 && maze[sx][sy - 2] == a ) {        n.push( { x:sx, y:sy - 1 } ); n.push( { x:sx, y:sy - 2 } );    }    if( sy + 1 < rows - 1 && maze[sx][sy + 1] == a && sy + 2 < rows - 1 && maze[sx][sy + 2] == a ) {        n.push( { x:sx, y:sy + 1 } ); n.push( { x:sx, y:sy + 2 } );    }    return n;}function createArray( c, r ) {    var m = new Array( c );    for( var i = 0; i < c; i++ ) {        m[i] = new Array( r );        for( var j = 0; j < r; j++ ) {            m[i][j] = 1;        }    }    return m;}function createMaze() {    var neighbours = getNeighbours( start.x, start.y, 1 ), l;    if( neighbours.length < 1 ) {        if( stack.length < 1 ) {            drawMaze(); stack = [];            start.x = start.y = -1;            document.getElementById( "canvas" ).addEventListener( "mousedown", getCursorPos, false );            return;        }        start = stack.pop();    } else {        var i = 2 * Math.floor( Math.random() * ( neighbours.length / 2 ) )        l = neighbours[i]; maze[l.x][l.y] = 0;        l = neighbours[i + 1]; maze[l.x][l.y] = 0;        start = l        stack.push( start )    }    drawMaze();    requestAnimationFrame( createMaze );}function createCanvas( w, h ) {    var canvas = document.createElement( "canvas" );    wid = w; hei = h;    canvas.width = wid; canvas.height = hei;    canvas.id = "canvas";    ctx = canvas.getContext( "2d" );    ctx.fillStyle = "black"; ctx.fillRect( 0, 0, wid, hei );    document.body.appendChild( canvas ); }function init() {    cols = 73; rows = 53;    createCanvas( grid * cols, grid * rows );    maze = createArray( cols, rows );    start.x = Math.floor( Math.random() * ( cols / 2 ) );    start.y = Math.floor( Math.random() * ( rows / 2 ) );    if( !( start.x & 1 ) ) start.x++; if( !( start.y & 1 ) ) start.y++;    maze[start.x][start.y] = 0;    createMaze();} `

HTML to test.

```<!DOCTYPE html>
<title>Maze</title>
```

## Julia

Works with: Julia version 0.6
Translation of: Python
`"""    +   +---+---+    | 1   2   3 |    +---+   +   +    | 4   5 | 6    +---+---+---+     julia> const graph = [            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]     julia> dist, path = dijkstra(graph, 1)    (Dict(4=>3,2=>1,3=>2,5=>2,6=>3,1=>0), Dict(4=>5,2=>1,3=>2,5=>2,6=>3,1=>0))     julia> printpath(path, 6) # Display solution of the maze    1 -> 2 -> 3 -> 6 """function dijkstra(graph, source::Int=1)    # ensure that the adjacency matrix is squared    @assert size(graph, 1) == size(graph, 2)    inf = typemax(Int64)    n   = size(graph, 1)     Q    = IntSet(1:n)                  # Set of unvisited nodes    dist = Dict(n => inf for n in Q)    # Unknown distance function from source to v    prev = Dict(n => 0   for n in Q)    # Previous node in optimal path from source    dist[source] = 0                    # Distance from source to source     function _minimumdist(nodes) # Find the less distant node among nodes        kmin, vmin = nothing, inf        for (k, v) in dist            if k ∈ nodes && v ≤ vmin                kmin, vmin = k, v            end        end        return kmin    end    # Until all nodes are visited...    while !isempty(Q)        u = _minimumdist(Q)         # Vertex in Q with smallest dist[]        pop!(Q, u)        if dist[u] == inf break end # All remaining vertices are inaccessible from source        for v in 1:n                # Each neighbor v of u            if graph[u, v] != 0 && v ∈ 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                    prev[v] = u                end            end        end    end     return dist, prevend function printpath(prev::Dict, target::Int)    path = "\$target"    while prev[target] != 0        target = prev[target]        path = "\$target -> " * path    end    println(path)end const graph = [    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] dist, path = dijkstra(graph)printpath(path, 6)`

## Kotlin

Translation of: Java
`// Version 1.2.31 import java.io.File typealias Maze = List<CharArray> /**    * 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.    */fun decimateHorizontally(lines: List<String>): Maze {    val width = (lines[0].length + 1) / 2    val c = List(lines.size) { CharArray(width) }    for (i in 0 until lines.size) {        for (j in 0 until width) c[i][j] = lines[i][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.    */fun solveMazeRecursively(maze: Maze, x: Int, y: Int, d: Int): Boolean {    var ok = false    var i = 0    while (i < 4 && !ok) {        if (i != d) {            // 0 = up, 1 = right, 2 = down, 3 = left            when(i) {                0 -> if (maze[y - 1][x] == ' ') ok = solveMazeRecursively (maze, x, y - 2, 2)                1 -> if (maze[y][x + 1] == ' ') ok = solveMazeRecursively (maze, x + 2, y, 3)                2 -> if (maze[y + 1][x] == ' ') ok = solveMazeRecursively (maze, x, y + 2, 0)                3 -> if (maze[y][x - 1] == ' ') ok = solveMazeRecursively (maze, x - 2, y, 1)             else -> {}            }        }        i++    }     // 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] = '*'        when (d) {            0 -> maze[y - 1][x] = '*'            1 -> maze[y][x + 1] = '*'            2 -> maze[y + 1][x] = '*'            3 -> maze[y][x - 1] = '*'         else -> {}        }    }    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.    */fun solveMaze(maze: Maze) =    solveMazeRecursively(maze, maze[0].size - 2, maze.size - 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.    */fun expandHorizontally(maze: Maze): Array<String> {    val tmp = CharArray(3)    val lines = Array<String>(maze.size) { "" }    for (i in 0 until maze.size) {        val sb = StringBuilder(maze[i].size * 2)        for (j in 0 until maze[i].size) {            if (j % 2 == 0)                sb.append(maze[i][j])            else {                for (k in 0..2) tmp[k] = 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#Kotlin    * in a file whose name is specified as a command-line argument.    */fun main(args: Array<String>) {    if (args.size != 1) {        println("The maze file to be read should be passed as a single command line argument.")        return    }    val f = File(args[0])    if (!f.exists()) {        println("Sorry \${args[0]} does not exist.")        return    }    val lines = f.readLines(Charsets.US_ASCII)    val maze = decimateHorizontally(lines)    solveMaze(maze)    val solvedLines = expandHorizontally(maze)    println(solvedLines.joinToString("\n"))}`
Output:

Maze (maze.txt) produced by the maze generation program:

```+---+---+---+---+---+---+---+---+
|           |               |   |
+---+---+   +   +   +---+   +   +
|       |   |   |   |   |       |
+   +   +   +---+   +   +---+   +
|   |   |   |       |           |
+   +   +   +   +---+---+---+   +
|   |   |   |               |   |
+---+   +   +---+---+---+   +   +
|       |   |           |   |   |
+   +---+   +   +---+   +   +   +
|   |       |       |       |   |
+   +   +---+---+   +---+---+   +
|       |       |       |       |
+   +---+   +   +---+   +   +---+
|           |           |       |
+---+---+---+---+---+---+---+---+
```

Solution generated by this program when passed maze.txt - follow *'s from bottom right (start) to top left (finish):

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

## Mathematica

### Graph

Solving the maze generated in Maze_generation#Graph:

`HighlightGraph[maze, [email protected][maze, 1, 273]]`
Output:

## Perl

This example includes maze generation code.

` #!perluse strict;use warnings; my (\$width, \$height) = @ARGV;\$_ ||= 10 for \$width, \$height; my %visited; my \$h_barrier = "+" . ("--+" x \$width) . "\n";my \$v_barrier = "|" . ("  |" x \$width) . "\n";my @output = (\$h_barrier, \$v_barrier) x \$height;push @output, \$h_barrier;my @dx = qw(-1 1 0 0);my @dy = qw(0 0 -1 1); sub visit {   my (\$x, \$y) = @_;   \$visited{\$x, \$y} = 1;   my \$rand = int rand 4;   for my \$n ( \$rand .. 3, 0 .. \$rand-1 ) {      my (\$xx, \$yy) = (\$x + \$dx[\$n], \$y + \$dy[\$n]);      next if \$visited{ \$xx, \$yy };      next if \$xx < 0 or \$xx >= \$width;      next if \$yy < 0 or \$yy >= \$height;       my \$row = \$y * 2 + 1 + \$dy[\$n];      my \$col = \$x * 3 + 1 + \$dx[\$n];      substr( \$output[\$row], \$col, 2, '  ' );       no warnings 'recursion';      visit( \$xx, \$yy );   }} visit( int rand \$width, int rand \$height ); print "Here is the maze:\n";print @output; %visited = (); my @d = ('>>', '<<', 'vv', '^^');sub solve {   my (\$x, \$y) = @_;   return 1 if \$x == 0 and \$y == 0;   \$visited{ \$x, \$y } = 1;   my \$rand = int rand 4;   for my \$n ( \$rand .. 3, 0 .. \$rand-1 ) {      my (\$xx, \$yy) = (\$x + \$dx[\$n], \$y + \$dy[\$n]);      next if \$visited{ \$xx, \$yy };      next if \$xx < 0 or \$xx >= \$width;      next if \$yy < 0 or \$yy >= \$height;       my \$row = \$y * 2 + 1 + \$dy[\$n];      my \$col = \$x * 3 + 1 + \$dx[\$n];       my \$b = substr( \$output[\$row], \$col, 2 );      next if "  " ne \$b;       no warnings 'recursion';      next if not solve( \$xx, \$yy );       substr( \$output[\$row], \$col, 2, \$d[\$n] );      substr( \$output[\$row-\$dy[\$n]], \$col-\$dx[\$n], 2, \$d[\$n] );      return 1;   }   0;} if( solve( \$width-1, \$height-1 ) ) {   print "Here is the solution:\n";   substr( \$output[1], 1, 2, '**' );   print @output;} else {   print "Could not solve!\n";} `
Output:
```Here is the maze:
+--+--+--+--+--+--+--+--+--+--+
|  |                    |     |
+  +  +--+--+--+  +--+  +  +  +
|     |        |  |        |  |
+  +--+--+  +  +  +--+--+--+  +
|           |  |     |     |  |
+--+--+--+--+  +--+  +--+  +  +
|           |  |  |     |     |
+  +  +--+  +  +  +--+  +--+  +
|  |     |  |  |     |     |  |
+--+--+  +--+  +  +  +--+  +--+
|        |     |  |  |  |     |
+  +--+--+  +--+--+  +  +--+  +
|  |     |  |        |        |
+  +  +  +  +  +--+--+--+--+--+
|  |  |     |  |     |        |
+  +  +--+--+  +  +  +  +--+  +
|  |  |     |     |        |  |
+  +  +  +  +--+--+--+--+--+  +
|        |                    |
+--+--+--+--+--+--+--+--+--+--+
Here is the solution:
+--+--+--+--+--+--+--+--+--+--+
|**|                    |     |
+vv+  +--+--+--+  +--+  +  +  +
|vv   |   ^^>>>|  |        |  |
+vv+--+--+^^+vv+  +--+--+--+  +
|vv>>>>>>>>>|vv|     |     |  |
+--+--+--+--+vv+--+  +--+  +  +
|           |vv|  |     |     |
+  +  +--+  +vv+  +--+  +--+  +
|  |     |  |vv|     |     |  |
+--+--+  +--+vv+  +  +--+  +--+
|        |<<<vv|  |  |  |     |
+  +--+--+vv+--+--+  +  +--+  +
|  |<<<^^|vv|        |        |
+  +vv+^^+vv+  +--+--+--+--+--+
|  |vv|<<<vv|  |     |        |
+  +vv+--+--+  +  +  +  +--+  +
|  |vv|^^>>>|     |        |  |
+  +vv+^^+vv+--+--+--+--+--+  +
|   vv>>>|vv>>>>>>>>>>>>>>>>>>|
+--+--+--+--+--+--+--+--+--+--+
```

## Perl 6

Works with: Rakudo version 2017.02

(Includes maze generation code.)

`constant mapping = :OPEN(' '),		      :N< ╵ >,		      :E< ╶ >,		     :NE< └ >,		      :S< ╷ >,		     :NS< │ >,		     :ES< ┌ >,		    :NES< ├ >,		      :W< ╴ >,		     :NW< ┘ >,		     :EW< ─ >,		    :NEW< ┴ >,		     :SW< ┐ >,		    :NSW< ┤ >,		    :ESW< ┬ >,		   :NESW< ┼ >,		   :TODO< x >,	          :TRIED< · >; enum Sym (mapping.map: *.key);my @ch = 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, \$[ flat ES, -N, (ESW, EW) xx \$X - 1, SW ];    push @maze, \$[ flat (NS, TODO) xx \$X, NS ];    for 1 ..^ \$Y {	push @maze, \$[ flat NES, EW, (NESW, EW) xx \$X - 1, NSW ];	push @maze, \$[ flat (NS, TODO) xx \$X, NS ];    }    push @maze, \$[ flat 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.rotor(2) -> (\$w, \$c) {	    print @ch[abs \$w];	    if \$c >= 0 { print @ch[\$c] x 3 } 	    else { print ' ', @ch[abs \$c], ' ' }	}	say @ch[@y[*-1]];    }} 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;    }} display solve gen_maze( 29, 19 );`
Output:
```┌ ╵ ────┬───────────────┬───────────────┬───────────────────────────────┬───────────┬───────────────┬───────────────┐
│ ╵ · · │ ╷ ╴ ╴ ╴ ╴     │               │ ╷ ╴ ╴ · · · · · · · · · · · · │ ╷ ╴ ╴ · · │ · · · · · · · │ · · · · · · · │
│ ╵ ╶───┘ ╷ ╶───┐ ╵ ╷   │   ╷   ╶───────┤ ╷ ╷ ╵ ╶───────┬───────┐ · ┌───┘ ╷ ╷ ╵ ╷ · │ · ╶───┬───╴ · │ · ╷ · ┌───╴ · │
│ ╵ ╴ ╴ ╴ ╴ · · │ ╵ │   │   │           │ ╷ │ ╵ ╴ ╴ ╴ ╴ │ ╷ ╴ ╴ │ · │ ╷ ╴ ╴ │ ╵ │ · │ · · · │ · · · │ · │ · │ · · · │
│ · ┌───────────┤ ╵ │   └───┴───────╴   │ ╷ ├───────┐ ╵ ╵ ╷ ╷ ╵ └───┘ ╷ ┌───┘ ╵ │ · │ · ╷ · │ · ┌───┴───┘ · │ · ╶───┤
│ · │ ╶ ╶ ╶ ╶ ╷ │ ╵ │                   │ ╷ │       │ ╵ ╴ ╴ │ ╵ ╴ ╴ ╴ ╴ │ ╶ ╶ ╵ │ · │ · │ · │ · │ · · · · · │ · · · │
│ · │ ╵ ╶───┐ ╷ ╵ ╵ ├───────────────╴   │ ╷ └───╴   └───────┼───┬───────┤ ╵ ┌───┤ · ├───┘ · │ · │ · ╷ · ┌───┴───┐ · │
│ · │ ╵ ╴ ╴ │ ╶ ╶ ╵ │                   │ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╷ │ · │ ╶ ╶ ╷ │ ╵ │ · │ · │ · · · │ · │ · │ · │ · · · │ · │
│ · └───┐ ╵ ├───────┴───────┐   ╶───────┴───────┬───────╴ ╷ │ · │ ╵ ╷ ╷ │ ╵ │ · │ · │ · ┌───┤ · │ · │ · │ · ╷ · ╵ · │
│ · · · │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │                   │ ╷ ╴ ╴ ╴ ╴ │ · │ ╵ │ ╷ │ ╵ │ · │ · │ · │ · │ · │ · │ · │ · │ · · · │
├───╴ · │ ╵ │ ╷ ╶───────┐ ╵ ├───────────────┐   │ ╷ ╶───┬───┘ · │ ╵ │ ╷ ╵ ╵ │ · ╵ · ╵ · │ · ╵ · └───┘ · │ · ├───────┤
│ · · · │ ╵ │ ╶ ╶ ╶ ╶ ╷ │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │   │ ╶ ╶ ╷ │ · · · │ ╵ │ ╶ ╶ ╵ │ · · · · · │ · · · · · · · │ · │ · · · │
│ · ┌───┤ ╵ └───────╴ ╷ │ ╵ ╵ ╷ ┌───────┐ ╵ │   └───┐ ╷ └───┐ · │ ╵ ├───────┼───────┬───┴───────┬───┬───┘ · ├───╴ · │
│ · │ · │ ╵ ╴ ╴ ╴ ╴ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ ╵ │       │ ╶ ╶ ╷ │ · │ ╵ │ ╷ ╴ ╴ │ ╷ ╴ ╴ │ ╷ ╴ ╴ ╴ ╴ │ · │ · · · │ · · · │
│ · ╵ · ├───────────────┴───────┴───┐ · │ ╵ └───────┴───┐ ╷ │ · │ ╵ ╵ ╷ ╷ ╵ ╵ ╷ ╷ ╵ │ ╷ ┌───╴ ╵ │ · │ · ╶───┤ · ╶───┤
│ · · · │ · · · · · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ · · │ ╷ │ · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ ╵ │ ╷ │ ╶ ╶ ╵ │ · │ · · · │ · · · │
├───┐ · │ · ┌───────────╴ · ┌───┐ · │ · └───┬───╴ ╵ ┌───┘ ╷ │ · ├───────┴───────┤ ╵ ╵ ╷ │ ╵ ╶───┤ · └───┐ · │ · ╷ · │
│ · │ · │ · │ · · · · · · · │ · │ · │ · · · │ ╶ ╶ ╵ │ ╷ ╴ ╴ │ · │ · · · · · · · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ · │ · │ · │
│ · │ · └───┘ · ┌───────────┘ · │ · ├───╴ · │ ╵ ┌───┘ ╷ ┌───┘ · │ · ╷ · ┌───╴ · └───────┴───┐ ╵ └───┐ · ╵ · ├───┘ · │
│ · │ · · · · · │ · · · · · · · │ · │ · · · │ ╵ │ ╷ ╴ ╴ │ · · · │ · │ · │ · · · · · · · · · │ ╵ ╴ ╴ │ · · · │ · · · │
│ · ├───────╴ · ├───┐ · ┌───┐ · ╵ · │ · ╶───┤ ╵ ╵ ╷ ┌───┘ · ╶───┤ · │ · └───┬───╴ · ┌───────┤ · ╷ ╵ │ · ╶───┘ · ╷ · │
│ · │ · · · · · │   │ · │ · │ · · · │ · · · │ ╵ ╴ ╴ │ · · · · · │ · │ · · · │ · · · │ ╶ ╶ ╷ │ · │ ╵ │ · · · · · │ · │
│ · ╵ · ┌───────┘   │ · ╵ · └───────┤ · ╷ · └───────┴───────┐ · ╵ · └───┐ · └───┐ · │ ╵ ╷ ╷ └───┘ ╵ ├───────────┤ · │
│ · · · │           │ · · · · · · · │ · │ · · · · · · · · · │ · · · · · │ · · · │ · │ ╵ │ ╶ ╶ ╶ ╶ ╵ │ ╷ ╴ ╴ ╴ ╴ │ · │
│ · ╶───┤   ╶───────┴───┬───────┐ · ├───┘ · ┌───────────┐ · ├───────────┴───╴ · │ · │ ╵ └───────┐ · │ ╷ ┌───╴ ╵ │ · │
│ · · · │               │ · · · │ · │ · · · │ · · · · · │ · │ · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ │ · │ ╷ │ ╶ ╶ ╵ │ · │
├───┐ · ├───────┬───╴   │ · ╷ · │ · │ · ┌───┤ · ╶───────┤ · │ · ╶───────┬───┐ · ├───┴───────┐ ╵ └───┘ ╷ │ ╵ ┌───┴───┤
│ · │ · │       │       │ · │ · │ · │ · │ · │ · · · · · │ · │ · · · · · │ · │ · │           │ ╵ ╴ ╴ ╴ ╴ │ ╵ │ ╷ ╴ ╴ │
│ · │ · │   ╷   ╵   ┌───┘ · │ · ╵ · ╵ · │ · ╵ · ┌───┐ · ╵ · └───────╴ · │ · ╵ · │   ┌───╴   └───────┐ · │ ╵ ╵ ╷ ╷ ╵ │
│ · │ · │   │       │ · · · │ · · · · · │ · · · │ · │ · · · · · · · · · │ · · · │   │               │ · │ ╵ ╴ ╴ │ ╵ │
│ · │ · │   └───┬───┴───────┴───┬───────┤ · ┌───┘ · ├───────────────────┴───────┤   └───────────┐   └───┴───────┤ ╵ │
│ · │ · │       │               │       │ · │ · · · │                           │               │               │ ╵ │
│ · ╵ · ├───┐   │   ╶───────┐   ╵   ╷   │ · ╵ · ╷ · │   ╶───────────────────┐   └───┬───────┐   └───────┬───┐   │ ╵ │
│ · · · │ · │   │           │       │   │ · · · │ · │                       │       │       │           │   │   │ ╵ │
│ · ╶───┤ · │   └───────┐   ├───────┤   └───┬───┴───┼───────────┬───────┐   ├───┐   ╵   ╷   ├───────┐   │   │   │ ╵ │
│ · · · │ · │           │   │       │       │       │           │       │   │   │       │   │       │   │   │   │ ╵ │
├───╴ · ╵ · └───────┐   ╵   │   ╷   └───╴   ╵   ╷   ╵   ┌───╴   ╵   ╷   ╵   │   └───────┘   ╵   ╷   ╵   │   ╵   ╵ ╵ │
│ · · · · · · · · · │       │   │               │       │           │       │                   │       │         ╵ │
└───────────────────┴───────┴───┴───────────────┴───────┴───────────┴───────┴───────────────────┴───────┴──────── │ ┘```

## Phix

Combined generator and solver.

`-- demo\rosetta\Maze_solving.exwconstant w = 11, h = 8 sequence wall = join(repeat("+",w+1),"---")&"\n",         cell = join(repeat("|",w+1)," ? ")&"\n",         grid = split(join(repeat(wall,h+1),cell),'\n') procedure amaze(integer x, integer y)    grid[y][x] = ' '                        -- mark cell visited    sequence p = shuffle({{x-4,y},{x,y+2},{x+4,y},{x,y-2}})    for i=1 to length(p) do        integer {nx,ny} = p[i]        if nx>1 and nx<w*4 and ny>1 and ny<=2*h and grid[ny][nx]='?' then            integer mx = (x+nx)/2            grid[(y+ny)/2][mx-1..mx+1] = ' ' -- knock down wall            amaze(nx,ny)        end if    end forend procedure integer dx,dy -- door location (in a wall!) function solve_maze(integer x, y)    sequence p = {{x-4,y},{x,y+2},{x+4,y},{x,y-2}}    for d=1 to length(p) do        integer {nx,ny} = p[d]        integer {wx,wy} = {(x+nx)/2,(y+ny)/2}        if grid[wy][wx]=' ' then            grid[wy][wx] = "-:-:"[d]        -- mark path            if {wx,wy}={dx,dy} then return true end if            if grid[ny][nx]=' ' then                grid[ny][nx] = 'o'          -- mark cell                if solve_maze(nx,ny) then return true end if                grid[ny][nx] = ' '          -- unmark cell            end if            grid[wy][wx] = ' '              -- unmark path        end if    end for     return falseend function function heads()    return rand(2)=1 -- toin coss 50:50 true(1)/false(0)end function integer {x,y} = {(rand(w)*4)-1,rand(h)*2}amaze(x,y)-- mark start posgrid[y][x] = '*'-- add a random door (heads=rhs/lhs, tails=top/btm)if heads() then    {dy,dx} = {rand(h)*2,heads()*w*4+1}    grid[dy][dx] = ' 'else    {dy,dx} = {heads()*h*2+1,rand(w)*4-1}    grid[dy][dx-1..dx+1] = ' 'end if{} = solve_maze(x,y)puts(1,join(grid,'\n'))`
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 |               |   |
+---+---+---+---+---+---+---+---+---+---+---+
```

## 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 @) "   ")) ) ) )`

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.

`:- 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 => northwardnext(0, _Lig, _Col, L, C, L1, C) :-	L > 0,	L1 is L - 1,	\+cell(L1, C). % 1 => rightwardnext(1, _Lig, Col, L, C, L, C1) :-	C < Col - 1,	C1 is C + 1,	\+cell(L, C1). % 2 => southwardnext(2, Lig, _Col, L, C, L1, C) :-	L < Lig - 1,	L1 is L + 1,	\+cell(L1, C). % 3 => leftwardnext(2, _Lig, _Col, L, C, L, C1) :-	C > 0,	C1 is C - 1,	\+cell(L, C1).  `

output :

## 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 ;demonstrationIf 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`

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

## Racket

Following function returns a path between two cells in a maze which is created by the build-maze function (See Maze generation).

` ;; Returns a path connecting two given cells in the maze;; find-path :: Maze Cell Cell -> (Listof Cell)(define (find-path m p1 p2)  (match-define (maze N M tbl) m)  (define (alternatives p prev) (remove prev (connections tbl p)))  (define (dead-end? p prev) (empty? (alternatives p prev)))  (define ((next-turn route) p)    (define prev (car route))    (cond      [(equal? p p2) (cons p2 route)]      [(dead-end? p prev) '()]      [else (append-map (next-turn (cons p route))                         (alternatives p prev))]))  (reverse    (append-map (next-turn (list p1))                (alternatives p1 (list p1))))) `

Reading a maze from a file

` ;; Reads the maze from the textual form;; read-maze :: File-path -> Maze(define (read-maze file)  (define tbl (make-hash))  (with-input-from-file file    (λ ()      ; the first line gives us the width of the maze      (define N (/ (- (string-length (read-line)) 1) 4))      ; while reading other lines we get the height of the maze      (define M        (for/sum ([h (in-lines)] [v (in-lines)] [j (in-naturals)])          (for ([i (in-range N)])            (when (eq? #\space (string-ref h (* 4 (+ 1 i))))              (connect! tbl (list i j) (list (+ i 1) j)))            (when (eq? #\space (string-ref v (+ 1 (* 4 i))))              (connect! tbl (list i j) (list i (+ j 1)))))          1))      (maze N M tbl)))) `

Printing out a maze with a path between two given cells

` ;; Shows a maze with a path connecting two given cells(define (show-path m p1 p2)    (match-define (maze N M tbl) m)  (define route (find-path m p1 p2))  (for ([i N]) (display "+---"))  (displayln "+")  (for ([j M])    (display "|")    (for ([i (- N 0)])      (if (member (list i j) route)          (display " *")          (display "  "))      (if (connected? tbl (list i j) (list (+ 1 i) j))          (display "  ")          (display " |")))    (newline)    (for ([i N])      (if (connected? tbl (list i j) (list i (+ j 1)))          (display "+   ")          (display "+---")))    (displayln "+"))  (newline)) `

Example:

```-> (define m (build-maze 14 7))
-> (with-output-to-file "maze" (λ () (show-maze m)))
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                       |           |           |       |
+   +---+---+---+---+   +   +   +   +---+   +---+   +   +
|       |           |   |   |   |   |       |       |   |
+---+   +   +---+   +---+   +   +   +   +---+   +---+   +
|       |   |   |           |   |   |       |   |       |
+   +   +   +   +---+---+---+   +   +   +   +   +   +---+
|   |   |   |       |           |   |   |       |       |
+   +---+   +   +   +   +---+---+   +   +---+---+---+   +
|   |       |   |   |           |   |           |   |   |
+   +   +---+---+   +---+---+   +   +---+---+   +   +   +
|   |               |   |       |           |       |   |
+   +---+---+---+   +   +   +---+---+---+   +---+---+   +
|                   |       |                           |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

-> (show-path m '(0 0) '(13 6))
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| *                     | *   *   * |           |       |
+   +---+---+---+---+   +   +   +   +---+   +---+   +   +
| *   * | *   *   * |   | * |   | * |       |       |   |
+---+   +   +---+   +---+   +   +   +   +---+   +---+   +
| *   * | * |   | *   *   * |   | * |       |   |       |
+   +   +   +   +---+---+---+   +   +   +   +   +   +---+
| * |   | * |       |           | * |   |       |       |
+   +---+   +   +   +   +---+---+   +   +---+---+---+   +
| * | *   * |   |   |           | * |           |   |   |
+   +   +---+---+   +---+---+   +   +---+---+   +   +   +
| * | *   *   *   * |   |       | *   *   * |       |   |
+   +---+---+---+   +   +   +---+---+---+   +---+---+   +
| *   *   *   *   * |       |             *   *   *   * |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```

## Ruby

This solution extends the maze generator script. To get a working script, copy & paste both parts into one file.

`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     # Clean up.    reset_visiting_state     # Enqueue start position.    @queue = []    enqueue_cell([], @start_x, @start_y)     # Loop as long as there are cells to visit and no solution has    # been found yet.    path = nil    until path || @queue.empty?      path = solve_visit_cell    end     if path      # Mark the cells that make up the shortest path.      for x, y in path        @path[x][y] = true      end    else      puts "No solution found?!"    end  end   private   # Maze solving visiting method.  def solve_visit_cell    # 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?    return path  if x == @end_x && y == @end_y     # Mark cell as visited.    @visited[x][y] = true     for dx, dy in DIRECTIONS      if dx.nonzero?        # Left / Right        new_x = x + dx        if move_valid?(new_x, y) && [email protected]_walls[ [x, new_x].min ][y]          enqueue_cell(path, new_x, y)        end      else        # Top / Bottom        new_y = y + dy        if move_valid?(x, new_y) && [email protected]_walls[x][ [y, new_y].min ]          enqueue_cell(path, x, new_y)        end      end    end     nil         # No solution yet.  end   # Enqueue a new coordinate to visit.  def enqueue_cell(path, x, y)    # Add new coordinates to the current path and enqueue the new path.    @queue << path + [[x, y]]  endend # Demonstration:maze = Maze.new 20, 10maze.solvemaze.print`

Example output:

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

## Tcl

Works with: Tcl version 8.6

This script assumes that the contents of the generation task have already been `source`d. 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).

`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 outputs [m view]`

Example output:

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

## zkl

This entry parses a maze generated by http://rosettacode.org/wiki/Maze_generation#zkl and chooses random start/end points. Parsing the maze and switching between row major (h,w) and row minor (x,y) makes for some pretty vile code.

`ver,hor:=make_maze();  // see above link for this code fcn munge(a,b){ String(a[0,2],b,a[3,*]) } // "+---" --> "+-*-" fcn solveMaze(ver,hor, a,b, u,v, w,h){   if (a==u and b==v) return(True);    sh:=hor[b][a]; sv:=ver[b][a];   hor[b][a]=munge(sh,"*"); ver[b][a]=munge(sv,"*");   // drop breadcrumb    foreach dx,dy in (T( T(0,-1),T(1,0),T(0,1),T(-1,0) )){      x:=a+dx; y:=b+dy; hy:=hor[y]; vy:=ver[y];      if ( (0<=x<w) and (0<=y<h) and // (x,y) in bounds	   (dx==0 or (dx== 1 and vy[x]=="    ") or   // horizontal		     (dx==-1 and vy[a][0]==" " and vy[x][2]!="*")) and	   (dy==0 or (dy== 1 and hy[x]=="+   ") or   // vertical		     (dy==-1 and hor[b][a][1]==" " and hy[x][2]!="*"))         )      {	 sh:=hy[x];	 if(solveMaze(ver,hor, x,y, u,v, w,h)){	    hy[x]=sh; // remove splat on wall but not floor while backing out	    return(True); 	 }      }   }   hor[b][a]=sh; ver[b][a]=sv;  // pick up breadcrumb when backtracking   return(False);} w:=(hor[0].len() - 1); h:=(hor.len() - 1);startx:=(0).random(w); starty:=(0).random(h);endx  :=(0).random(w); endy  :=(0).random(h); sh:=hor[starty][startx];if (not solveMaze(ver,hor, startx,starty, endx,endy, w,h))   println("No solution path found.");else{   hor[starty][startx]=sh;   ver[starty][startx]=munge(ver[starty][startx],"S");   ver[endy][endx]    =munge(ver[endy][endx],"E");   foreach a,b in (hor.zip(ver)) { println(a.concat(),"\n",b.concat()) }}`
Output:
```+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|           | *   *         | *   * | *   *   *   *   *   * |   |
+---+---+   +   +   +---+   +   +   +   +   +---+---+---+   +   +
|           | * | * |       | * | *   * |   | *   *   * | * | S |
+   +---+   +   +   +---+---+   +---+---+   +   +---+   +   +   +
|   |       | * | * | *   * | *     |       | * | *   * | * | * |
+   +   +---+   +   +   +   +   +---+   +---+   +   +---+   +   +
|   |       | * | *   * | *   * |       | *   * | * | *   * | * |
+   +   +---+   +---+---+---+---+   +---+   +---+   +   +---+   +
|   |   | *   * |           |       | *   * |   | *   * | *   * |
+   +---+   +---+   +   +   +   +---+   +---+   +---+---+   +---+
| E   *   * |       |   |   |   |   | * | *   *   *   *   * |   |
+   +---+---+---+---+   +   +   +   +   +   +---+---+---+---+   +
|   |       |       |   |   |   |     *   * |               |   |
+   +   +   +   +   +   +   +   +---+---+---+   +---+---+   +   +
|       |       |       |   |                           |       |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```