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.
Ada
The maze is read from the standard input. The size of the maze is hardwired into the program (see the constants X_Size and Y_Size).
<lang Ada>with Ada.Text_IO;
procedure Maze_Solver is
X_Size: constant Natural := 45; Y_Size: constant Natural := 17;
subtype X_Range is Natural range 1 .. X_Size; subtype Y_Range is Natural range 1 .. Y_Size;
East: constant X_Range := 2; South: constant Y_Range := 1;
X_Start: constant X_Range := 3; -- start at the upper left Y_Start: constant Y_Range := 1; X_Finish: constant X_Range := X_Size-East; -- go to the lower right Y_Finish: constant Y_Range := Y_Size;
type Maze_Type is array (Y_Range) of String(X_Range);
function Solved(X: X_Range; Y: Y_Range) return Boolean is begin return (X = X_Finish) and (Y = Y_Finish); end Solved;
procedure Output_Maze(M: Maze_Type; Message: String := "") is begin if Message /= "" then Ada.Text_IO.Put_Line(Message); end if; for I in M'Range loop Ada.Text_IO.Put_Line(M(I)); end loop; end Output_Maze;
procedure Search(M: in out Maze_Type; X: X_Range; Y:Y_Range) is begin M(Y)(X) := '*'; if Solved(X, Y) then Output_Maze(M, "Solution found!"); else if Integer(Y)-South >= 1 and then M(Y-South)(X) = ' ' then Search(M, X, Y-South); end if; if Integer(Y)+South <= Y_Size and then M(Y+South)(X) = ' ' then Search(M, X, Y+South); end if; if Integer(X)-East >= 1 and then M(Y)(X-East) = ' ' then Search(M, X-East, Y); end if; if Integer(Y)+East <= Y_Size and then M(Y)(X+East) = ' ' then Search(M, X+East, Y); end if; end if; M(Y)(X) := ' '; end Search;
Maze: Maze_Type; X: X_Range := X_Start; Y: Y_Range := Y_Start;
begin
for I in 1 .. Y_Size loop Maze(I) := Ada.Text_IO.Get_Line; end loop; Maze(Y_Start)(X_Start) := ' '; -- Start from Maze(Y_Finish)(X_Finish) := ' '; -- Go_To Output_Maze(Maze, "The Maze:"); Ada.Text_IO.New_Line;
Search(Maze, X, Y) ; -- Will output *all* Solutions. -- If there is no output, there is no solution.
end Maze_Solver;</lang>
Example output (using a maze generated by the Ada implementation of the maze generation task as the input):
> ./maze_solver < maze.txt The Maze: +- -+---+---+---+---+---+---+---+---+---+---+ | | | + + +---+---+---+---+---+---+---+ + + | | | | | | + +---+---+ +---+ + +---+---+---+ + | | | | | | | +---+ +---+---+ +---+ + + +---+ + | | | | | | | + +---+ +---+---+ +---+ + + +---+ | | | | | | +---+---+ + +---+---+---+---+ +---+ + | | | | | | + + +---+---+ +---+ + +---+---+ + | | | | | + +---+ +---+---+---+---+---+---+---+ + | | | +---+---+---+---+---+---+---+---+---+---+- -+ Solution found! +-*-+---+---+---+---+---+---+---+---+---+---+ | * * * * * * * * * * * * * * * * * * * | | + + +---+---+---+---+---+---+---+ * + + | | | | * * * * * * * | | + +---+---+ +---+ + * +---+---+---+ + | | | | * | | | +---+ +---+---+ +---+ * + + +---+ + | | | * * * | | | | + +---+ +---+---+ * +---+ + + +---+ | | | * * * * * | | | +---+---+ + * +---+---+---+---+ +---+ + | | * * * | * * * | | | + + +---+---+ * +---+ * + * +---+---+ + | | | * * * * * | * * * * * * * | + +---+ +---+---+---+---+---+---+---+ * + | | * | +---+---+---+---+---+---+---+---+---+---+-*-+
BBC BASIC
Maze generation code also included. <lang bbcbasic> MazeWidth% = 11
MazeHeight% = 9 MazeCell% = 50 VDU 23,22,MazeWidth%*MazeCell%/2+3;MazeHeight%*MazeCell%/2+3;8,16,16,128 VDU 23,23,3;0;0;0; : REM Line thickness OFF PROCgeneratemaze(Maze&(), MazeWidth%, MazeHeight%, MazeCell%) PROCsolvemaze(Path{()}, Maze&(), 0, MazeHeight%-1, MazeWidth%-1, 0, MazeCell%) END DEF PROCsolvemaze(RETURN s{()}, m&(), x%, y%, dstx%, dsty%, s%) LOCAL h%, i%, n%, p%, q%, w% w% = DIM(m&(),1) h% = DIM(m&(),2) DIM s{(w%*h%) x%,y%} GCOL 3,14 m&(x%,y%) OR= &80 REPEAT FOR i% = 0 TO 3 CASE i% OF WHEN 0: p% = x%-1 : q% = y% WHEN 1: p% = x%+1 : q% = y% WHEN 2: p% = x% : q% = y%-1 WHEN 3: p% = x% : q% = y%+1 ENDCASE IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &80 THEN IF p% > x% IF m&(p%,q%) AND 1 EXIT FOR IF q% > y% IF m&(p%,q%) AND 2 EXIT FOR IF x% > p% IF m&(x%,y%) AND 1 EXIT FOR IF y% > q% IF m&(x%,y%) AND 2 EXIT FOR ENDIF NEXT IF i% < 4 THEN m&(p%,q%) OR= &80 s{(n%)}.x% = x% s{(n%)}.y% = y% n% += 1 ELSE IF n% > 0 THEN n% -= 1 p% = s{(n%)}.x% q% = s{(n%)}.y% ENDIF ENDIF LINE (x%+0.5)*s%,(y%+0.5)*s%,(p%+0.5)*s%,(q%+0.5)*s% x% = p% y% = q% UNTIL x%=dstx% AND y%=dsty% s{(n%)}.x% = x% s{(n%)}.y% = y% ENDPROC DEF PROCgeneratemaze(RETURN m&(), w%, h%, s%) LOCAL x%, y% DIM m&(w%, h%) FOR y% = 0 TO h% LINE 0,y%*s%,w%*s%,y%*s% NEXT FOR x% = 0 TO w% LINE x%*s%,0,x%*s%,h%*s% NEXT GCOL 15 PROCcell(m&(), RND(w%)-1, y% = RND(h%)-1, w%, h%, s%) ENDPROC DEF PROCcell(m&(), x%, y%, w%, h%, s%) LOCAL i%, p%, q%, r% m&(x%,y%) OR= &40 : REM Mark visited r% = RND(4) FOR i% = r% TO r%+3 CASE i% MOD 4 OF WHEN 0: p% = x%-1 : q% = y% WHEN 1: p% = x%+1 : q% = y% WHEN 2: p% = x% : q% = y%-1 WHEN 3: p% = x% : q% = y%+1 ENDCASE IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &40 THEN IF p% > x% m&(p%,q%) OR= 1 : LINE p%*s%,y%*s%+4,p%*s%,(y%+1)*s%-4 IF q% > y% m&(p%,q%) OR= 2 : LINE x%*s%+4,q%*s%,(x%+1)*s%-4,q%*s% IF x% > p% m&(x%,y%) OR= 1 : LINE x%*s%,y%*s%+4,x%*s%,(y%+1)*s%-4 IF y% > q% m&(x%,y%) OR= 2 : LINE x%*s%+4,y%*s%,(x%+1)*s%-4,y%*s% PROCcell(m&(), p%, q%, w%, h%, s%) ENDIF NEXT ENDPROC</lang>
C
See Maze generation for combined gen/solve code.
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;
} //-------------------------------------------------------------------------------------------------- </lang>
D
This entry reads a maze generated by http://rosettacode.org/wiki/Maze_generation#D and chooses two random start-end points. <lang d>import std.stdio, std.random, std.string, std.array, std.algorithm,
std.traits;
enum int cx = 4; // Cell size x. enum int cy = 2; // Cell size y. enum int cx2 = cx / 2; enum int cy2 = cy / 2; enum char pathSymbol = '.'; struct V2 { int x, y; }
bool solveMaze(char[][] maze, in V2 s, in V2 end) pure nothrow {
if (s == end) return true;
foreach (d; [V2(0, -cy), V2(+cx, 0), V2(0, +cy), V2(-cx, 0)]) if (maze[s.y + (d.y / 2)][s.x + (d.x / 2)] == ' ' && maze[s.y + d.y][s.x + d.x] == ' ') { maze[s.y + d.y][s.x + d.x] = pathSymbol; if (solveMaze(maze, V2(s.x + d.x, s.y + d.y), end)) return true; maze[s.y + d.y][s.x + d.x] = ' '; }
return false;
}
void main() {
auto maze = File("maze.txt") .byLine() .map!(r => r.strip().dup)() .filter!(r => !r.empty)() .array();
immutable int h = (maze.length - 1) / cy; assert (h > 0); immutable int w = (maze[0].length - 1) / cx;
immutable start = V2(cx2 + cx * uniform(0, w), cy2 + cy * uniform(0, h)); immutable end = V2(cx2 + cx * uniform(0, w), cy2 + cy * uniform(0, h));
maze[start.y][start.x] = pathSymbol; if (solveMaze(maze, start, end)) { maze[start.y][start.x] = 'S'; maze[end.y][end.x] = 'E'; writefln("%-(%s\n%)", maze); } else writeln("No solution path found.");
}</lang>
- Output:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | | | | . . . . . . . . . | + + +---+---+ + +---+ + . +---+---+---+ . + + | | | | . . . | | . | | +---+---+---+---+---+---+---+ +---+ . +---+ + . +---+ | | | | . . . . . | E | + +---+---+---+ + + +---+ +---+---+ . +---+---+ | | . . . | | | | | . . . | | +---+ + . + . + + +---+---+---+ + +---+ . + + | | . | . | | . . . | | . . . | | + +---+ . + . +---+---+ . + . +---+---+---+ . +---+ + | . . . . . | . | . . . . . | . . . . . . . | . . . . . | + . +---+---+ . + . +---+---+---+---+---+ . +---+---+ . + | . . . | | . . . | | | . | . | +---+ . + +---+---+ + +---+ + + . +---+---+ . + | | . . . . . . . | | | | . | . . . . . | + +---+---+---+ . + +---+ +---+ + . + . +---+---+ | | . . . . . . . | | | | | . . . | | + + . +---+---+---+---+ +---+ + +---+---+ + + | . . . . . . S | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
EGL
<lang EGL>program MazeGenAndSolve
// First and last columns/rows are "dead" cells. Makes generating // a maze with border walls much easier. Therefore, a visible // 20x20 maze has a maze size of 22. mazeSize int = 22;
south boolean[][]; west boolean[][]; visited boolean[][];
// Solution variables solution Dictionary; done boolean; startingRow, startingCol, endingRow, endingCol int;
function main() initMaze(); generateMaze(); drawMaze(false); // Draw maze without solution
solveMaze(); drawMaze(true); // Draw maze with solution end
private function initMaze()
visited = createBooleanArray(mazeSize, mazeSize, false);
// Initialize border cells as already visited for(col int from 1 to mazeSize) visited[col][1] = true; visited[col][mazeSize] = true; end for(row int from 1 to mazeSize) visited[1][row] = true; visited[mazeSize][row] = true; end
// Initialize all walls as present south = createBooleanArray(mazeSize, mazeSize, true); west = createBooleanArray(mazeSize, mazeSize, true); end
private function createBooleanArray(col int in, row int in, initialState boolean in) returns(boolean[][])
newArray boolean[][] = new boolean[0][0];
for(i int from 1 to col) innerArray boolean[] = new boolean[0]; for(j int from 1 to row) innerArray.appendElement(initialState); end newArray.appendElement(innerArray); end
return(newArray);
end
private function createIntegerArray(col int in, row int in, initialValue int in) returns(int[][])
newArray int[][] = new int[0][0];
for(i int from 1 to col) innerArray int[] = new int[0]; for(j int from 1 to row) innerArray.appendElement(initialValue); end newArray.appendElement(innerArray); end
return(newArray);
end
private function generate(col int in, row int in)
// Mark cell as visited
visited[col][row] = true;
// Keep going as long as there is an unvisited neighbor while(!visited[col][row + 1] || !visited[col + 1][row] || !visited[col][row - 1] || !visited[col - 1][row])
while(true) r float = MathLib.random(); // Choose a random direction case when(r < 0.25 && !visited[col][row + 1]) // Go south south[col][row] = false; // South wall down generate(col, row + 1); exit while; when(r >= 0.25 && r < 0.50 && !visited[col + 1][row]) // Go east west[col + 1][row] = false; // West wall of neighbor to the east down generate(col + 1, row); exit while; when(r >= 0.5 && r < 0.75 && !visited[col][row - 1]) // Go north south[col][row - 1] = false; // South wall of neighbor to the north down generate(col, row - 1); exit while; when(r >= 0.75 && r < 1.00 && !visited[col - 1][row]) // Go west west[col][row] = false; // West wall down generate(col - 1, row); exit while; end end end
end
private function generateMaze()
// Pick random start position (within the visible maze space) randomStartCol int = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2); randomStartRow int = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2);
generate(randomStartCol, randomStartRow);
end
private function drawMaze(solve boolean in)
line string;
// Iterate over wall arrays (skipping dead border cells as required). // Construct a row at a time and output to console. for(row int from 1 to mazeSize - 1)
if(row > 1) line = ""; for(col int from 2 to mazeSize) if(west[col][row]) line ::= cellTest(col, row, solve); else line ::= cellTest(col, row, solve); end end Syslib.writeStdout(line); end
line = ""; for(col int from 2 to mazeSize - 1) if(south[col][row]) line ::= "+---"; else line ::= "+ "; end end line ::= "+"; SysLib.writeStdout(line);
end
end
private function cellTest(col int in, row int in, solve boolean in) returns(string)
wall string;
// Determine cell wall structure. If in solve mode, show start, end and // solution markers. if(!solve) if(west[col][row]) wall = "| "; else wall = " "; end else if(west[col][row])
case when(col == startingCol and row == startingRow) wall = "| S "; when(col == endingCol and row == endingRow) wall = "| E "; when(solution.containsKey("x=" + col + "y=" + row)) wall = "| * "; otherwise wall = "| "; end
else case when(col == startingCol and row == startingRow) wall = " S "; when(col == endingCol and row == endingRow) wall = " E "; when(solution.containsKey("x=" + col + "y=" + row)) wall = " * "; otherwise wall = " "; end end end
return(wall); end
private function solve(col int in, row int in)
if(col == 1 || row == 1 || col == mazeSize || row == mazeSize) return; end
if(done || visited[col][row]) return; end
visited[col][row] = true;
solution["x=" + col + "y=" + row] = true;
// Reached the end point if(col == endingCol && row == endingRow) done = true; end
if(!south[col][row]) // Go South solve(col, row + 1); end if(!west[col + 1][row]) // Go East solve(col + 1, row); end if(!south[col][row - 1]) // Go North solve(col, row - 1); end if(!west[col][row]) // Go West solve(col - 1, row); end
if(done) return; end
solution.removeElement("x=" + col + "y=" + row);
end
private function solveMaze() for(col int from 1 to mazeSize) for(row int from 1 to mazeSize) visited[col][row] = false; end end
solution = new Dictionary(false, OrderingKind.byInsertion); done = false;
// Pick random start position on first visible row startingCol = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2); startingRow = 2;
// Pick random end position on last visible row endingCol = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2); endingRow = mazeSize - 1;
solve(startingCol, startingRow); end
end</lang>
- Output example (for 10x10 maze):
+---+---+---+---+---+---+---+---+---+---+ | | | | | + +---+ +---+---+ + + +---+ + | | | | | | | | +---+ + +---+ +---+---+ + + + | | | | | | | + +---+---+ + + + +---+---+ + | | | | | | | + + + + + +---+---+---+ + + | | | | | | | + +---+---+---+ + +---+ +---+ + | | | | | | +---+ +---+ +---+ + +---+ + + | | | | | | | + + + +---+ +---+---+---+---+ + | | | | | | | + + + + +---+---+---+---+ + + | | | | | | | | + + + + +---+---+ + + + + | | | | +---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+---+ | | * * S | | | + +---+ +---+---+ + + +---+ + | | * | | | | | | +---+ + +---+ +---+---+ + + + | | * * | * * | | | | + +---+---+ + + + +---+---+ + | | * * | * | * | * * * * | | + + + + + +---+---+---+ + + | * * | * * | * | | * * | | + +---+---+---+ + +---+ +---+ + | * * | * * | | * * | | +---+ +---+ +---+ + +---+ + + | | * | * * | * * * | | | + + + +---+ +---+---+---+---+ + | | * | * | | * * * * * | | + + + + +---+---+---+---+ + + | | * | * | | * * | * | | + + + + +---+---+ + + + + | * * | E | * * | +---+---+---+---+---+---+---+---+---+---+
Frege
On standard input, takes a maze made up of "+", "|", and "---" (i. e. each cell is two lines high and four characters wide), such as produced by the Haskell or Java generators.
<lang frege>module MazeSolver where
import frege.IO import Data.Maybe
-- given two points, returns the average of them average :: (Int, Int) -> (Int, Int) -> (Int, Int) average (x, y) (x', y') = ((x + x') `div` 2, (y + y') `div` 2)
-- given a maze and a tuple of position and wall position, returns -- true if the wall position is not blocked (first position is unused) notBlocked :: [String] -> ((Int, Int), (Int, Int)) -> Bool notBlocked maze (_, (x, y)) = (' ' == String.charAt (maze !! y) x)
-- given a list, a position, and an element, returns a new list -- with the new element substituted at the position substitute :: [a] -> Int -> a -> [a] substitute orig pos el =
let (before, after) = splitAt pos orig in before ++ [el] ++ tail after
-- like above, but for strings, since Frege strings are not -- lists of characters substituteString :: String -> Int -> String -> String substituteString orig pos el =
let before = substr orig 0 pos after = strtail orig (pos + 1) in before ++ el ++ after
-- given a maze and a position, draw a '*' at that position in the maze draw :: [String] -> (Int, Int) -> [String] draw maze (x,y) = substitute maze y $ substituteString row x "*"
where row = maze !! y
-- given a maze, a previous position, and a list of tuples of potential -- new positions and their wall positions, returns the solved maze, or -- None if it cannot be solved tryMoves :: [String] -> (Int, Int) -> [((Int, Int), (Int, Int))] -> Maybe [String] tryMoves _ _ [] = Nothing tryMoves maze prevPos ((newPos,wallPos):more) =
case solve' maze newPos prevPos of Nothing -> tryMoves maze prevPos more Just maze' -> Just $ foldl draw maze' [newPos, wallPos]
-- given a maze, a new position, and a previous position, returns -- the solved maze, or None if it cannot be solved -- (assumes goal is upper-left corner of maze) solve' :: [String] -> (Int, Int) -> (Int, Int) -> Maybe [String] solve' maze (2, 1) _ = Just maze solve' maze (x, y) prevPos =
let newPositions = [(x, y - 2), (x + 4, y), (x, y + 2), (x - 4, y)] notPrev pos' = pos' /= prevPos newPositions' = filter notPrev newPositions wallPositions = map (average (x,y)) newPositions' zipped = zip newPositions' wallPositions legalMoves = filter (notBlocked maze) zipped in tryMoves maze (x,y) legalMoves
-- given a maze, returns a solved maze, or None if it cannot be solved -- (starts at lower right corner and goes to upper left corner) solve :: [String] -> Maybe [String] solve maze = solve' (draw maze start) start (-1, -1)
where startx = (length $ head maze) - 3 starty = (length maze) - 2 start = (startx, starty)
-- takes unsolved maze on standard input, prints solved maze on standard output main _ = do
isin <- stdin isrin <- InputStreamReader.new isin brin <- BufferedReader.fromISR isrin lns <- BufferedReader.getlines brin printStr $ unlines $ fromMaybe ["can't solve"] $ solve lns</lang>
- Output:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | * | * * * * * | | | | | | + * +---+---+ * +---+ * +---+ + + + +---+---+---+ + + + + + | * | * * * * * | | * | | | | * * * * * | | | | + * + * +---+---+ + * + +---+ +---+---+ * +---+ * + +---+---+---+ + | * * * | | | * | | | * * * * * | * * * | | * * * * * | | +---+---+ + + + * + + +---+ * +---+---+ * +---+---+ * +---+ * + + | | | * | | | * | | * * * | * * * * * | * * * | | + + +---+---+---+ * + +---+ + * + + * +---+ * +---+---+ * +---+ + | | | * * * * * * * | | * | * * * * * | | * * * * * | + + + * +---+---+---+---+---+---+ * +---+---+---+---+ + +---+---+ * + | | | * * * | * * * * * | * * * | * * * | * * * | | | * | + +---+---+ * + * +---+ * + * + * +---+ * + * + * +---+ +---+ + + * + | | | * | * | * * * | * | * * * | * * * | * * * | | | | | * | + + + + * + * + * +---+ * +---+ * +---+---+---+ * + + + +---+ * + | | * * * | * * * * * | * * * * * * * * * | | * | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ runtime 0.249 wallclock seconds.
Go
Generates maze, picks start and finish cells randomly, solves, prints. <lang go>package main
import (
"bytes" "fmt" "math/rand" "time"
)
type maze struct {
c2 [][]byte // cells by row h2 [][]byte // horizontal walls by row (ignore first row) v2 [][]byte // vertical walls by row (ignore first of each column)
}
func newMaze(rows, cols int) *maze {
c := make([]byte, rows*cols) // all cells h := bytes.Repeat([]byte{'-'}, rows*cols) // all horizontal walls v := bytes.Repeat([]byte{'|'}, rows*cols) // all vertical walls c2 := make([][]byte, rows) // cells by row h2 := make([][]byte, rows) // horizontal walls by row v2 := make([][]byte, rows) // vertical walls by row for i := range h2 { c2[i] = c[i*cols : (i+1)*cols] h2[i] = h[i*cols : (i+1)*cols] v2[i] = v[i*cols : (i+1)*cols] } return &maze{c2, h2, v2}
}
func (m *maze) String() string {
hWall := []byte("+---") hOpen := []byte("+ ") vWall := []byte("| ") vOpen := []byte(" ") rightCorner := []byte("+\n") rightWall := []byte("|\n") var b []byte for r, hw := range m.h2 { for _, h := range hw { if h == '-' || r == 0 { b = append(b, hWall...) } else { b = append(b, hOpen...) if h != '-' && h != 0 { b[len(b)-2] = h } } } b = append(b, rightCorner...) for c, vw := range m.v2[r] { if vw == '|' || c == 0 { b = append(b, vWall...) } else { b = append(b, vOpen...) if vw != '|' && vw != 0 { b[len(b)-4] = vw } } if m.c2[r][c] != 0 { b[len(b)-2] = m.c2[r][c] } } b = append(b, rightWall...) } for _ = range m.h2[0] { b = append(b, hWall...) } b = append(b, rightCorner...) return string(b)
}
func (m *maze) gen() {
m.g2(rand.Intn(len(m.c2)), rand.Intn(len(m.c2[0])))
}
const (
up = iota dn rt lf
)
func (m *maze) g2(r, c int) {
m.c2[r][c] = ' ' for _, dir := range rand.Perm(4) { switch dir { case up: if r > 0 && m.c2[r-1][c] == 0 { m.h2[r][c] = 0 m.g2(r-1, c) } case lf: if c > 0 && m.c2[r][c-1] == 0 { m.v2[r][c] = 0 m.g2(r, c-1) } case dn: if r < len(m.c2)-1 && m.c2[r+1][c] == 0 { m.h2[r+1][c] = 0 m.g2(r+1, c) } case rt: if c < len(m.c2[0])-1 && m.c2[r][c+1] == 0 { m.v2[r][c+1] = 0 m.g2(r, c+1) } } }
}
func main() {
rand.Seed(time.Now().UnixNano()) const height = 4 const width = 7 m := newMaze(height, width) m.gen() m.solve( rand.Intn(height), rand.Intn(width), rand.Intn(height), rand.Intn(width)) fmt.Print(m)
}
func (m *maze) solve(ra, ca, rz, cz int) {
var rSolve func(ra, ca, dir int) bool rSolve = func(r, c, dir int) bool { if r == rz && c == cz { m.c2[r][c] = 'F' return true } if dir != dn && m.h2[r][c] == 0 { if rSolve(r-1, c, up) { m.c2[r][c] = '^' m.h2[r][c] = '^' return true } } if dir != up && r+1 < len(m.h2) && m.h2[r+1][c] == 0 { if rSolve(r+1, c, dn) { m.c2[r][c] = 'v' m.h2[r+1][c] = 'v' return true } } if dir != lf && c+1 < len(m.v2[0]) && m.v2[r][c+1] == 0 { if rSolve(r, c+1, rt) { m.c2[r][c] = '>' m.v2[r][c+1] = '>' return true } } if dir != rt && m.v2[r][c] == 0 { if rSolve(r, c-1, lf) { m.c2[r][c] = '<' m.v2[r][c] = '<' return true } } return false } rSolve(ra, ca, -1) m.c2[ra][ca] = 'S'
}</lang> Example output:
+---+---+---+---+---+---+---+ | | v < < < < < < | + +---+ + v + +---+ ^ + | | F < < | | ^ | +---+---+---+---+ +---+ ^ + | | | ^ | + +---+---+ +---+ + ^ + | | | S | +---+---+---+---+---+---+---+
Haskell
On standard input, takes a maze made up of "+", "|", and "---" (i. e. each cell is two lines high and four characters wide), such as produced by the Haskell or Java generators.
<lang haskell>#!/usr/bin/runhaskell
import Data.Maybe
-- given two points, returns the average of them average :: (Int, Int) -> (Int, Int) -> (Int, Int) average (x, y) (x', y') = ((x + x') `div` 2, (y + y') `div` 2)
-- given a maze and a tuple of position and wall position, returns -- true if the wall position is not blocked (first position is unused) notBlocked :: [String] -> ((Int, Int), (Int, Int)) -> Bool notBlocked maze (_, (x, y)) = ' ' == (maze !! y) !! x
-- given a list, a position, and an element, returns a new list -- with the new element substituted at the position -- (it seems such a function should exist in the standard library; -- I must be missing it) substitute :: [a] -> Int -> a -> [a] substitute orig pos el =
let (before, after) = splitAt pos orig in before ++ [el] ++ tail after
-- given a maze and a position, draw a '*' at that position in the maze draw :: [String] -> (Int, Int) -> [String] draw maze (x,y) = substitute maze y $ substitute row x '*'
where row = maze !! y
-- given a maze, a previous position, and a list of tuples of potential -- new positions and their wall positions, returns the solved maze, or -- None if it cannot be solved tryMoves :: [String] -> (Int, Int) -> [((Int, Int), (Int, Int))] -> Maybe [String] tryMoves _ _ [] = Nothing tryMoves maze prevPos ((newPos,wallPos):more) =
case solve' maze newPos prevPos of Nothing -> tryMoves maze prevPos more Just maze' -> Just $ foldl draw maze' [newPos, wallPos]
-- given a maze, a new position, and a previous position, returns -- the solved maze, or None if it cannot be solved -- (assumes goal is upper-left corner of maze) solve' :: [String] -> (Int, Int) -> (Int, Int) -> Maybe [String] solve' maze (2, 1) _ = Just maze solve' maze pos@(x, y) prevPos =
let newPositions = [(x, y - 2), (x + 4, y), (x, y + 2), (x - 4, y)] notPrev pos' = pos' /= prevPos newPositions' = filter notPrev newPositions wallPositions = map (average pos) newPositions' zipped = zip newPositions' wallPositions legalMoves = filter (notBlocked maze) zipped in tryMoves maze pos legalMoves
-- given a maze, returns a solved maze, or None if it cannot be solved -- (starts at lower right corner and goes to upper left corner) solve :: [String] -> Maybe [String] solve maze = solve' (draw maze start) start (-1, -1)
where startx = length (head maze) - 3 starty = length maze - 2 start = (startx, starty)
-- takes unsolved maze on standard input, prints solved maze on standard output main = interact main'
where main' x = unlines $ fromMaybe ["can't solve"] $ solve $ lines x</lang>
- Output:
+---+---+---+---+---+---+---+---+---+---+---+ | * | | | | + * + +---+ + +---+ +---+ +---+ + | * | | | | | | | + * +---+ + +---+ +---+ +---+---+ + | * | | | | | | + * +---+---+---+ +---+ + + + + + | * * * * * * * | | | | | +---+---+---+ * +---+ +---+---+---+ + + | | * * * | | | | | + +---+ +---+ * + + +---+ + +---+ | | | * * * | | | | | +---+---+ + * +---+---+---+ + +---+ + | | * * * * * | | | | + +---+---+---+---+ * +---+ +---+---+ + | * * * * * * * * * * * | +---+---+---+---+---+---+---+---+---+---+---+
Icon and Unicon
The following code works with the solution from Maze Generation.
Replace the main with this: <lang Icon>procedure main(A)
/mh := \A[1] | 12 /mw := \A[2] | 16 mz := DisplayMaze(GenerateMaze(mh,mw)) WriteImage(mz.filename) # save file WAttrib(mz.window,"canvas=normal") # show it until Event() == &lpress # wait for left mouse press Solver(mz.maze) DisplayMazeSolution(mz) WriteImage(mz.filename ?:= (="maze-", "maze-solved-" || tab(0))) until Event() == &lpress # wait close(mz.window)
end</lang>
And include this after the Generator and Display procedures. <lang Icon>procedure Solver(r,c) static maze,h,w,rd
if type(r) == "list" then { # ------------------- Top Level (r == maze) h := *(maze := r) # height w := *maze[1] # width every r := 1 to h & c := 1 to w do # remove breadcrumbs maze[r,c] := iand(maze[r,c],NORTH+EAST+SOUTH+WEST+START+FINISH) every ((r := 1 | h) & (c := 1 to w)) | # search perimiter ((r := 1 to h) & (c := 1 | w)) do if iand(maze[r,c],START) > 0 then break # until start found Solver(r,c) # recurse through maze return 1(.maze,maze := &null) # return maze and reset } else # ------------------- Recurse way through maze if iand(x := maze[r,c],SEEN) = 0 then { # in bounds and not seen? (iand(x,FINISH) > 0, maze[r,c] +:= PATH, return ) # at finish? - done! maze[r,c] +:= SEEN # drop bread crumb (iand(x,NORTH) > 0, Solver(r-1,c), maze[r,c] +:= PATH, return) (iand(x,EAST) > 0, Solver(r,c+1), maze[r,c] +:= PATH, return) (iand(x,SOUTH) > 0, Solver(r+1,c), maze[r,c] +:= PATH, return) (iand(x,WEST) > 0, Solver(r,c-1), maze[r,c] +:= PATH, return) }
end
procedure DisplayMazeSolution(mz) #: draw marked PATH &window := mz.window maze := mz.maze WAttrib("dx="||(dxy:=BORDER+CELL/2),"dy="||dxy) every (r := 1 to *maze) & (c := 1 to *maze[1]) do {
if fg ~=== "blue" then Fg(fg := "blue") if iand(maze[r,c],START) > 0 then Fg(fg := "red") if iand(maze[r,c],PATH) > 0 then FillCircle(x := CELL*(c-1),y := CELL*(r-1),rad := CELL/5) }
return mz end</lang>
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 finds all solutions in the maze and works if there are multiple target cells or multiple paths to those targets. The shortest solution path is then marked and displayed.
<lang unicon>global qMice, goodMice, region, qMiceLock
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 qMice := set() # Active mice goodMice := set() # Mice that found solutions startPos := findStart(mz.maze)
insert(qMice,QMouse(mz.maze,startPos)) # Start first quantum mouse # block until all quantum mice have finished critical qMiceLock: while *qMice > 0 do wait(qMiceLock)
# Mark the best path into the maze and display it. if setPath(mz.maze, goodMice) then { DisplayMazeSolution(mz) WriteImage(mz.filename ?:= (="maze-", "maze-solved-" || tab(0))) until Event() == &lpress # wait close(mz.window) } else write("No path found for maze!")
end
record 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
- A "Quantum-mouse" for traversing mazes.
class QMouse(maze, loc, path, mouse, val)
method getPath(); return path; end
method atEnd() return 0 < iand(val, FINISH) end
method goNorth() if 0 < iand(val,NORTH) then return visit(loc.r-1, loc.c) end
method goSouth() if 0 < iand(val,SOUTH) then return visit(loc.r+1, loc.c) end
method goEast() if 0 < iand(val,EAST) then return visit(loc.r, loc.c+1) end
method goWest() if 0 < iand(val,WEST) then return visit(loc.r, loc.c-1) end
method visit(r,c) critical region: if 0 = iand(maze[r][c],SEEN) then { maze[r][c] +:= SEEN unlock(region) return Position(r,c) } end
initially (m, l, p)
initial { region := mutex(maze) qMiceLock := mutex() } maze := m loc := l /path := [] if \p then path := copy(p) put(path, loc) val := maze[loc.r][loc.c] | fail mouse := thread { if not atEnd() then { # Spawn more mice to look for finish insert(qMice, QMouse(maze, goNorth(), path)) insert(qMice, QMouse(maze, goSouth(), path)) insert(qMice, QMouse(maze, goEast(), path)) insert(qMice, QMouse(maze, goWest(), path)) delete(qMice, self) # This mouse didn't find a finish } else { insert(goodMice, self) # This mouse found a finish delete(qMice, self) } }
end
procedure clearMaze(maze)
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)
clearMaze(maze) # Remove breadcrumbs h := *maze w := *maze[1] every ((r := 1 | h) & (c := 1 to w)) | # search perimeter ((r := 1 to h) & (c := 1 | w)) do if iand(maze[r,c],START) > 0 then return Position(r,c)
end
procedure setPath(maze, mice)
minPathLen := *maze * *maze[1] + 1 every m := !mice do if minPathLen >:= *m.getPath() then bestPath := m.getPath() if \bestPath then { every p := !bestPath do maze[p.r][p.c] +:= PATH return }
end</lang>
J
<lang J> NB. source Dijkstra_equal_weights graph NB. NB. + +---+---+ NB. | 0 1 2 | (sample cell numbers) NB. +---+ + + NB. | 3 4 | 5 NB. +---+---+---+ NB. NB. graph =: 1;0 2 4;1 5;4;1 3;2 NB. The graph is a vector of boxed vectors of neighbors.
Dijkstra_equal_weights =: 4 : 0
dist =. previous =. #&_ n =. # graph =. y [ source =. x dist =. 0 source } dist Q =. 0 while. #Q do. u =. {.Q Q =. }.Q if. _ = u{dist do. break. end. for_v. >u{graph do. if. -. v e. previous do. alt =. >: u { dist if. alt < v { dist do. dist =. alt v } dist previous =. u v } previous if. v e. Q do. echo 'belch' else. Q =. Q,v end. end. end. end. end. dist;previous
)
path =. 3 : 0
p =. <:#y while. _ > {:p do. p =. p,y{~{:p end. |.}:p
)
solve=:3 :0
NB. convert walls to graph shape =. }.@$@:> ew =. (,.&0 ,: 0&,.)@>@{. NB. east west doors ns =. (, &0 ,: 0&, )@>@{: cell_offsets =. 1 _1 1 _1 * 2 # 1 , {:@shape cell_numbers =. i.@shape neighbors =. (cell_numbers +"_ _1 cell_offsets *"_1 (ew , ns))y graph =. (|:@(,/"_1) <@-."1 0 ,@i.@shape)neighbors NB. list of boxed neighbors NB. solve it path , > {: 0 Dijkstra_equal_weights graph
)
display=:3 :0 NB. Monadic display copied from maze generation task
size=. >.&$&>/y text=. (}:1 3$~2*1+{:size)#"1":size$<' ' 'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y ' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text
a=. display y size=. >.&$&>/y columns=. {: size cells =. <"1(1 2&p.@<.@(%&columns) ,. 2 4&p.@(columns&|))x '+' cells } a NB. exercise, replace cells with a gerund to draw arrows on the path.
)
4 (display~ solve)@maze 9
┌ ┬───┬───┬───┬───┬───┬───┬───┬───┐ │ + │ │ │ ├ ┼───┼ ┼ ┼ ┼───┼ ┼ ┼ ┤ │ + + │ │ │ │ │ ├───┼ ┼───┼───┼───┼───┼───┼ ┼───┤ │ │ + + + │ + + + │ │ ├ ┼───┼───┼ ┼ ┼───┼ ┼───┼───┤ │ + + │ + + + └───┴───┴───┴───┴───┴───┴───┴───┴───┘
</lang>
Java
<lang java>import java.io.*; import java.util.*;
public class MazeSolver {
/** * Reads a file into an array of strings, one per line. */ private static String[] readLines (InputStream f) throws IOException { BufferedReader r = new BufferedReader (new InputStreamReader (f, "US-ASCII")); ArrayList<String> lines = new ArrayList<String>(); String line; while ((line = r.readLine()) != null) lines.add (line); return lines.toArray(new String[0]); }
/** * Makes the maze half as wide (i. e. "+---+" becomes "+-+"), so that * each cell in the maze is the same size horizontally as vertically. * (Versus the expanded version, which looks better visually.) * Also, converts each line of the maze from a String to a * char[], because we'll want mutability when drawing the solution later. */ private static char[][] decimateHorizontally (String[] lines) { final int width = (lines[0].length() + 1) / 2; char[][] c = new char[lines.length][width]; for (int i = 0 ; i < lines.length ; i++) for (int j = 0 ; j < width ; j++) c[i][j] = lines[i].charAt (j * 2); return c; }
/** * Given the maze, the x and y coordinates (which must be odd), * and the direction we came from, return true if the maze is * solvable, and draw the solution if so. */ private static boolean solveMazeRecursively (char[][] maze, int x, int y, int d) { boolean ok = false; for (int i = 0 ; i < 4 && !ok ; i++) if (i != d) switch (i) { // 0 = up, 1 = right, 2 = down, 3 = left case 0: if (maze[y-1][x] == ' ') ok = solveMazeRecursively (maze, x, y - 2, 2); break; case 1: if (maze[y][x+1] == ' ') ok = solveMazeRecursively (maze, x + 2, y, 3); break; case 2: if (maze[y+1][x] == ' ') ok = solveMazeRecursively (maze, x, y + 2, 0); break; case 3: if (maze[y][x-1] == ' ') ok = solveMazeRecursively (maze, x - 2, y, 1); break; } // check for end condition if (x == 1 && y == 1) ok = true; // once we have found a solution, draw it as we unwind the recursion if (ok) { maze[y][x] = '*'; switch (d) { case 0: maze[y-1][x] = '*'; break; case 1: maze[y][x+1] = '*'; break; case 2: maze[y+1][x] = '*'; break; case 3: maze[y][x-1] = '*'; break; } } return ok; }
/** * Solve the maze and draw the solution. For simplicity, * assumes the starting point is the lower right, and the * ending point is the upper left. */ private static void solveMaze (char[][] maze) { solveMazeRecursively (maze, maze[0].length - 2, maze.length - 2, -1); }
/** * Opposite of decimateHorizontally(). Adds extra characters to make * the maze "look right", and converts each line from char[] to * String at the same time. */ private static String[] expandHorizontally (char[][] maze) { char[] tmp = new char[3]; String[] lines = new String[maze.length]; for (int i = 0 ; i < maze.length ; i++) { StringBuilder sb = new StringBuilder(maze[i].length * 2); for (int j = 0 ; j < maze[i].length ; j++) if (j % 2 == 0) sb.append (maze[i][j]); else { tmp[0] = tmp[1] = tmp[2] = maze[i][j]; if (tmp[1] == '*') tmp[0] = tmp[2] = ' '; sb.append (tmp); } lines[i] = sb.toString(); } return lines; }
/** * Accepts a maze as generated by: * http://rosettacode.org/wiki/Maze_generation#Java * in a file whose name is specified as a command-line argument, * or on standard input if no argument is specified. */ public static void main (String[] args) throws IOException { InputStream f = (args.length > 0 ? new FileInputStream (args[0]) : System.in); String[] lines = readLines (f); char[][] maze = decimateHorizontally (lines); solveMaze (maze); String[] solvedLines = expandHorizontally (maze); for (int i = 0 ; i < solvedLines.length ; i++) System.out.println (solvedLines[i]); }
}</lang>
- Output:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | * | | | * * * * * | | + * + + +---+ +---+---+ + +---+ * +---+ * +---+ +---+ | * | | | | * * * | | | * * * | * * * | | + * + +---+ + + * + * + +---+ +---+ * +---+ * +---+ + | * | | | * | * | | * * * | | * | | + * +---+---+ +---+ * + * +---+---+ + * +---+ + * + + + | * | * * * | | * | * | * * * | | * | | * | | | + * + * + * +---+ + * + * + * + * +---+ * +---+ + * + +---+ | * * * | * | | * | * * * | * * * * * | | * | | +---+---+ * +---+---+ * +---+---+---+---+---+ +---+ * +---+ + | | * * * | * * * | | | * * * | | + +---+---+ * + * +---+ +---+---+ + +---+ +---+ * + + | * * * * * * * | * | | | | | | | * * * | + * +---+---+---+ * + + +---+ +---+ + + +---+---+ * + | * * * * * * * * * | | | * | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Mathematica
Graph
Solving the maze generated in Maze_generation#Graph: <lang mathematica>HighlightGraph[maze, PathGraph@FindShortestPath[maze, 1, 273]]</lang>
- Output:
Perl 6
(Includes maze generation code.) <lang perl6>constant mapping = :OPEN(' '), :N< ╵ >, :E< ╶ >, :NE< └ >, :S< ╷ >, :NS< │ >, :ES< ┌ >, :NES< ├ >, :W< ╴ >, :NW< ┘ >, :EW< ─ >, :NEW< ┴ >, :SW< ┐ >, :NSW< ┤ >, :ESW< ┬ >, :NESW< ┼ >, :TODO< x >, :TRIED< · >;
enum Code (mapping.map: *.key); my @code = mapping.map: *.value;
enum Direction <DeadEnd Up Right Down Left>;
sub gen_maze ( $X,
$Y, $start_x = (^$X).pick * 2 + 1, $start_y = (^$Y).pick * 2 + 1 )
{
my @maze; push @maze, [ ES, -N, (ESW, EW) xx $X - 1, SW ]; push @maze, [ (NS, TODO) xx $X, NS ]; for 1 ..^ $Y {
push @maze, [ NES, EW, (NESW, EW) xx $X - 1, NSW ]; push @maze, [ (NS, TODO) xx $X, NS ];
} push @maze, [ NE, (EW, NEW) xx $X - 1, -NS, NW ]; @maze[$start_y][$start_x] = OPEN;
my @stack; my $current = [$start_x, $start_y]; loop { if my $dir = pick_direction( $current ) { @stack.push: $current; $current = move( $dir, $current ); } else { last unless @stack; $current = @stack.pop; } } return @maze;
sub pick_direction([$x,$y]) {
my @neighbors = (Up if @maze[$y - 2][$x]), (Down if @maze[$y + 2][$x]), (Left if @maze[$y][$x - 2]), (Right if @maze[$y][$x + 2]); @neighbors.pick or DeadEnd;
}
sub move ($dir, @cur) {
my ($x,$y) = @cur; given $dir { when Up { @maze[--$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y--][$x+1] -= W; } when Down { @maze[++$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y++][$x+1] -= W; } when Left { @maze[$y][--$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x--] -= N; } when Right { @maze[$y][++$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x++] -= N; } } @maze[$y][$x] = 0; [$x,$y];
}
}
sub display (@maze) {
for @maze -> @y {
for @y -> $w, $c { print @code[abs $w]; if $c >= 0 { print @code[$c] x 3 } else { print ' ', @code[abs $c], ' ' } } say @code[@y[*-1]];
}
}
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 );</lang>
- Output:
┌ ╵ ────┬───────────────┬───────────────┬───────────────────────────────┬───────────┬───────────────┬───────────────┐ │ ╵ · · │ ╷ ╴ ╴ ╴ ╴ │ │ ╷ ╴ ╴ · · · · · · · · · · · · │ ╷ ╴ ╴ · · │ · · · · · · · │ · · · · · · · │ │ ╵ ╶───┘ ╷ ╶───┐ ╵ ╷ │ ╷ ╶───────┤ ╷ ╷ ╵ ╶───────┬───────┐ · ┌───┘ ╷ ╷ ╵ ╷ · │ · ╶───┬───╴ · │ · ╷ · ┌───╴ · │ │ ╵ ╴ ╴ ╴ ╴ · · │ ╵ │ │ │ │ ╷ │ ╵ ╴ ╴ ╴ ╴ │ ╷ ╴ ╴ │ · │ ╷ ╴ ╴ │ ╵ │ · │ · · · │ · · · │ · │ · │ · · · │ │ · ┌───────────┤ ╵ │ └───┴───────╴ │ ╷ ├───────┐ ╵ ╵ ╷ ╷ ╵ └───┘ ╷ ┌───┘ ╵ │ · │ · ╷ · │ · ┌───┴───┘ · │ · ╶───┤ │ · │ ╶ ╶ ╶ ╶ ╷ │ ╵ │ │ ╷ │ │ ╵ ╴ ╴ │ ╵ ╴ ╴ ╴ ╴ │ ╶ ╶ ╵ │ · │ · │ · │ · │ · · · · · │ · · · │ │ · │ ╵ ╶───┐ ╷ ╵ ╵ ├───────────────╴ │ ╷ └───╴ └───────┼───┬───────┤ ╵ ┌───┤ · ├───┘ · │ · │ · ╷ · ┌───┴───┐ · │ │ · │ ╵ ╴ ╴ │ ╶ ╶ ╵ │ │ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╷ │ · │ ╶ ╶ ╷ │ ╵ │ · │ · │ · · · │ · │ · │ · │ · · · │ · │ │ · └───┐ ╵ ├───────┴───────┐ ╶───────┴───────┬───────╴ ╷ │ · │ ╵ ╷ ╷ │ ╵ │ · │ · │ · ┌───┤ · │ · │ · │ · ╷ · ╵ · │ │ · · · │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │ │ ╷ ╴ ╴ ╴ ╴ │ · │ ╵ │ ╷ │ ╵ │ · │ · │ · │ · │ · │ · │ · │ · │ · · · │ ├───╴ · │ ╵ │ ╷ ╶───────┐ ╵ ├───────────────┐ │ ╷ ╶───┬───┘ · │ ╵ │ ╷ ╵ ╵ │ · ╵ · ╵ · │ · ╵ · └───┘ · │ · ├───────┤ │ · · · │ ╵ │ ╶ ╶ ╶ ╶ ╷ │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │ │ ╶ ╶ ╷ │ · · · │ ╵ │ ╶ ╶ ╵ │ · · · · · │ · · · · · · · │ · │ · · · │ │ · ┌───┤ ╵ └───────╴ ╷ │ ╵ ╵ ╷ ┌───────┐ ╵ │ └───┐ ╷ └───┐ · │ ╵ ├───────┼───────┬───┴───────┬───┬───┘ · ├───╴ · │ │ · │ · │ ╵ ╴ ╴ ╴ ╴ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ ╵ │ │ ╶ ╶ ╷ │ · │ ╵ │ ╷ ╴ ╴ │ ╷ ╴ ╴ │ ╷ ╴ ╴ ╴ ╴ │ · │ · · · │ · · · │ │ · ╵ · ├───────────────┴───────┴───┐ · │ ╵ └───────┴───┐ ╷ │ · │ ╵ ╵ ╷ ╷ ╵ ╵ ╷ ╷ ╵ │ ╷ ┌───╴ ╵ │ · │ · ╶───┤ · ╶───┤ │ · · · │ · · · · · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ · · │ ╷ │ · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ ╵ │ ╷ │ ╶ ╶ ╵ │ · │ · · · │ · · · │ ├───┐ · │ · ┌───────────╴ · ┌───┐ · │ · └───┬───╴ ╵ ┌───┘ ╷ │ · ├───────┴───────┤ ╵ ╵ ╷ │ ╵ ╶───┤ · └───┐ · │ · ╷ · │ │ · │ · │ · │ · · · · · · · │ · │ · │ · · · │ ╶ ╶ ╵ │ ╷ ╴ ╴ │ · │ · · · · · · · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ · │ · │ · │ │ · │ · └───┘ · ┌───────────┘ · │ · ├───╴ · │ ╵ ┌───┘ ╷ ┌───┘ · │ · ╷ · ┌───╴ · └───────┴───┐ ╵ └───┐ · ╵ · ├───┘ · │ │ · │ · · · · · │ · · · · · · · │ · │ · · · │ ╵ │ ╷ ╴ ╴ │ · · · │ · │ · │ · · · · · · · · · │ ╵ ╴ ╴ │ · · · │ · · · │ │ · ├───────╴ · ├───┐ · ┌───┐ · ╵ · │ · ╶───┤ ╵ ╵ ╷ ┌───┘ · ╶───┤ · │ · └───┬───╴ · ┌───────┤ · ╷ ╵ │ · ╶───┘ · ╷ · │ │ · │ · · · · · │ │ · │ · │ · · · │ · · · │ ╵ ╴ ╴ │ · · · · · │ · │ · · · │ · · · │ ╶ ╶ ╷ │ · │ ╵ │ · · · · · │ · │ │ · ╵ · ┌───────┘ │ · ╵ · └───────┤ · ╷ · └───────┴───────┐ · ╵ · └───┐ · └───┐ · │ ╵ ╷ ╷ └───┘ ╵ ├───────────┤ · │ │ · · · │ │ · · · · · · · │ · │ · · · · · · · · · │ · · · · · │ · · · │ · │ ╵ │ ╶ ╶ ╶ ╶ ╵ │ ╷ ╴ ╴ ╴ ╴ │ · │ │ · ╶───┤ ╶───────┴───┬───────┐ · ├───┘ · ┌───────────┐ · ├───────────┴───╴ · │ · │ ╵ └───────┐ · │ ╷ ┌───╴ ╵ │ · │ │ · · · │ │ · · · │ · │ · · · │ · · · · · │ · │ · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ │ · │ ╷ │ ╶ ╶ ╵ │ · │ ├───┐ · ├───────┬───╴ │ · ╷ · │ · │ · ┌───┤ · ╶───────┤ · │ · ╶───────┬───┐ · ├───┴───────┐ ╵ └───┘ ╷ │ ╵ ┌───┴───┤ │ · │ · │ │ │ · │ · │ · │ · │ · │ · · · · · │ · │ · · · · · │ · │ · │ │ ╵ ╴ ╴ ╴ ╴ │ ╵ │ ╷ ╴ ╴ │ │ · │ · │ ╷ ╵ ┌───┘ · │ · ╵ · ╵ · │ · ╵ · ┌───┐ · ╵ · └───────╴ · │ · ╵ · │ ┌───╴ └───────┐ · │ ╵ ╵ ╷ ╷ ╵ │ │ · │ · │ │ │ · · · │ · · · · · │ · · · │ · │ · · · · · · · · · │ · · · │ │ │ · │ ╵ ╴ ╴ │ ╵ │ │ · │ · │ └───┬───┴───────┴───┬───────┤ · ┌───┘ · ├───────────────────┴───────┤ └───────────┐ └───┴───────┤ ╵ │ │ · │ · │ │ │ │ · │ · · · │ │ │ │ ╵ │ │ · ╵ · ├───┐ │ ╶───────┐ ╵ ╷ │ · ╵ · ╷ · │ ╶───────────────────┐ └───┬───────┐ └───────┬───┐ │ ╵ │ │ · · · │ · │ │ │ │ │ · · · │ · │ │ │ │ │ │ │ ╵ │ │ · ╶───┤ · │ └───────┐ ├───────┤ └───┬───┴───┼───────────┬───────┐ ├───┐ ╵ ╷ ├───────┐ │ │ │ ╵ │ │ · · · │ · │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╵ │ ├───╴ · ╵ · └───────┐ ╵ │ ╷ └───╴ ╵ ╷ ╵ ┌───╴ ╵ ╷ ╵ │ └───────┘ ╵ ╷ ╵ │ ╵ ╵ ╵ │ │ · · · · · · · · · │ │ │ │ │ │ │ │ │ ╵ │ └───────────────────┴───────┴───┴───────────────┴───────┴───────────┴───────┴───────────────────┴───────┴──────── │ ┘
PicoLisp
<lang PicoLisp>(de shortestPath (Goal This Maze)
(let (Path NIL Best NIL Dir " > ") (recur (This Path Dir) (when (and This (not (: mark))) (push 'Path (cons This Dir)) (if (== Goal This) (unless (and Best (>= (length Path) (length Best))) (setq Best Path) ) (=: mark T) (recurse (: west) Path " > ") (recurse (: east) Path " < ") (recurse (: south) Path " \^ ") (recurse (: north) Path " v ") (=: mark NIL) ) ) ) (disp Maze 0 '((Fld) (if (asoq Fld Best) (cdr @) " ")) ) ) )</lang>
Using the maze produced in Maze generation#PicoLisp, this finds the shortest path from the top-left cell 'a8' to the bottom-right exit 'k1':
: (shortestPath 'a8 'k1 (maze 11 8)) + +---+---+---+---+---+---+---+---+---+---+ 8 | > > v | > v | | + + + + + + +---+ +---+---+ + 7 | | | > ^ | v | | | | | +---+ +---+---+ + + +---+ + + + 6 | | | v | | | | | + +---+ +---+ +---+---+---+ + +---+ 5 | | | > > > v | | | +---+ +---+ +---+---+---+ +---+---+ + 4 | | | | | v | > > v | + +---+ +---+ +---+ + + +---+ + 3 | | | | | v | ^ < | v | + +---+---+ + + + + +---+ + + 2 | | | | | | v | > ^ | v | + + + +---+ + +---+ + +---+ + 1 | | | > ^ | > +---+---+---+---+---+---+---+---+---+---+---+ a b c d e f g h i j k
Prolog
Works with SWI-Prolog and XPCE.
<lang Prolog>:- dynamic cell/2.
- - dynamic maze/3.
- - dynamic path/1.
maze_solve(Lig,Col) :- retractall(cell(_,_)), retractall(maze(_,_,_)), retractall(path(_)),
% initialisation of the neighbours of the cells forall(between(0, Lig, I), ( forall(between(0, Col, J), assert(maze(I, J, []))))),
% creation of the window of the maze new(D, window('Maze')), forall(between(0,Lig, I), (XL is 50, YL is I * 30 + 50, XR is Col * 30 + 50, new(L, line(XL, YL, XR, YL)), send(D, display, L))),
forall(between(0,Col, I), (XT is 50 + I * 30, YT is 50, YB is Lig * 30 + 50, new(L, line(XT, YT, XT, YB)), send(D, display, L))),
SX is Col * 30 + 100, SY is Lig * 30 + 100, send(D, size, new(_, size(SX, SY))), L0 is random(Lig), C0 is random(Col), assert(cell(L0, C0)), \+search(D, Lig, Col, L0, C0), send(D, open),
% we look for a path from cell(0, 0) to cell(Lig-1, Col-1) % creation of the entrance erase_line(D, -1, 0, 0, 0),
% creation of the exit Lig1 is Lig-1, Col1 is Col-1, erase_line(D, Lig1, Col1, Lig, Col1),
% seraching the path assert(path([[0, 0], [-1, 0]])), walk(Lig, Col), path(P), display_path(D, P).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% walk(Lig, Col) :- path([[L, C] | _R]), L is Lig - 1, C is Col - 1, retract(path(P)), assert(path([[Lig, C]|P])).
walk(Lig, Col) :- retract(path([[L, C] | R])), maze(L, C, Edge), member([L1, C1], Edge), \+member([L1, C1], R), assert(path([[L1,C1], [L, C] | R])), walk(Lig, Col).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% display_path(_, []).
display_path(D, [[L, C] | R]):- new(B, box(10,10)), send(B, fill_pattern, new(_, colour(@default, 0,0,0))), X is C * 30 + 60, Y is L * 30 + 60, send(D, display, B, point(X,Y)), display_path(D, R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
search(D, Lig, Col, L, C) :-
Dir is random(4),
nextcell(Dir, Lig, Col, L, C, L1, C1),
assert(cell(L1,C1)),
assert(cur(L1,C1)),
retract(maze(L, C, Edge)), assert(maze(L, C, [[L1, C1] | Edge])), retract(maze(L1, C1, Edge1)), assert(maze(L1, C1, [[L, C] | Edge1])),
erase_line(D, L, C, L1, C1), search(D, Lig, Col, L1, C1).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% erase_line(D, L, C, L, C1) :- ( C < C1 -> C2 = C1; C2 = C), XT is C2 * 30 + 50, YT is L * 30 + 51, YR is (L+1) * 30 + 50, new(Line, line(XT, YT, XT, YR)), send(Line, colour, white), send(D, display, Line).
erase_line(D, L, C, L1, C) :- XT is 51 + C * 30, XR is 50 + (C + 1) * 30, ( L < L1 -> L2 is L1; L2 is L), YT is L2 * 30 + 50, new(Line, line(XT, YT, XR, YT)), send(Line, colour, white), send(D, display, Line).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
nextcell(Dir, Lig, Col, L, C, L1, C1) :-
next(Dir, Lig, Col, L, C, L1, C1);
( Dir1 is (Dir+3) mod 4,
next(Dir1, Lig, Col, L, C, L1, C1));
( Dir2 is (Dir+1) mod 4,
next(Dir2, Lig, Col, L, C, L1, C1));
( Dir3 is (Dir+2) mod 4,
next(Dir3, Lig, Col, L, C, L1, C1)).
% 0 => northward next(0, _Lig, _Col, L, C, L1, C) :- L > 0, L1 is L - 1, \+cell(L1, C).
% 1 => rightward next(1, _Lig, Col, L, C, L, C1) :- C < Col - 1, C1 is C + 1, \+cell(L, C1).
% 2 => southward next(2, Lig, _Col, L, C, L1, C) :- L < Lig - 1, L1 is L + 1, \+cell(L1, C).
% 3 => leftward next(2, _Lig, _Col, L, C, L, C1) :- C > 0, C1 is C - 1, \+cell(L, C1).
PureBasic
<lang PureBasic>;code from the maze generation task is place here in its entirety before the rest of the code
Procedure displayMazePath(Array maze(2), List Path.POINT())
Protected x, y, vWall.s, hWall.s Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2) Protected Dim mazeOutput.mazeOutput(mazeHeight) Protected Dim mazeRow.mazeOutput(0) Static pathChars.s = "@^>v<" For y = 0 To mazeHeight makeDisplayMazeRow(mazeRow(), maze(), y): mazeOutput(y) = mazeRow(0) Next If ListSize(path()) FirstElement(path()) Protected prevPath.POINT = path() While NextElement(path()) x = path()\x - prevPath\x y = path()\y - prevPath\y Select x Case -1: dirTaken = #dir_W Case 1: dirTaken = #dir_E Default If y < 0 dirTaken = #dir_N Else dirTaken = #dir_S EndIf EndSelect hWall = mazeOutput(prevPath\y)\hWall mazeOutput(prevPath\y)\hWall = Left(hWall, prevPath\x * #cellDWidth + 2) + Mid(pathChars, dirTaken + 1, 1) + Right(hWall, Len(hWall) - (prevPath\x * #cellDWidth + 3)) prevPath = path() Wend hWall = mazeOutput(prevPath\y)\hWall mazeOutput(prevPath\y)\hWall = Left(hWall, prevPath\x * #cellDWidth + 2) + Mid(pathChars, #dir_ID + 1, 1) + Right(hWall, Len(hWall) - (prevPath\x * #cellDWidth + 3)) For y = 0 To mazeHeight PrintN(mazeOutput(y)\vWall): PrintN(mazeOutput(y)\hWall) Next EndIf
EndProcedure
Procedure solveMaze(Array maze(2), *start.POINT, *finish.POINT, List Path.POINT())
Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2) Dim visited(mazeWidth + 1, mazeHeight + 1) ;includes padding for easy border detection Protected i ;mark outside border as already visited (off limits) For i = 1 To mazeWidth visited(i, 0) = #True: visited(i, mazeHeight + 1) = #True Next For i = 1 To mazeHeight visited(0, i) = #True: visited(mazeWidth + 1, i) = #True Next Protected x = *start\x, y = *start\y, nextCellDir visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True ClearList(path()) Repeat If x = *finish\x And y = *finish\y AddElement(path()) path()\x = x: path()\y = y Break ;success EndIf nextCellDir = #firstDir - 1 For i = #firstDir To #numDirs If Not visited(x + offset(#visited, i)\x, y + offset(#visited, i)\y) If maze(x + offset(#wall, i)\x, y + offset(#wall, i)\y) & wallvalue(i) <> #Null nextCellDir = i: Break ;exit for/next search EndIf EndIf Next If nextCellDir >= #firstDir visited(x + offset(#visited, nextCellDir)\x, y + offset(#visited, nextCellDir)\y) = #True AddElement(path()) path()\x = x: path()\y = y x + offset(#maze, nextCellDir)\x: y + offset(#maze, nextCellDir)\y ElseIf ListSize(path()) > 0 x = path()\x: y = path()\y DeleteElement(path()) Else Break EndIf ForEver
EndProcedure
- demonstration
If OpenConsole()
Define.POINT start, finish start\x = Random(mazeWidth - 1): start\y = Random(mazeHeight - 1) finish\x = Random(mazeWidth - 1): finish\y = Random(mazeHeight - 1) NewList Path.POINT() solveMaze(maze(), start, finish, path()) If ListSize(path()) > 0 PrintN("Solution found for path between (" + Str(start\x) + ", " + Str(start\y) + ") and (" + Str(finish\x) + ", " + Str(finish\y) + ")") displayMazePath(maze(), path()) Else PrintN("No solution found for path between (" + Str(start\x) + ", " + Str(start\y) + ") and (" + Str(finish\x) + ", " + Str(finish\y) + ")") EndIf Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() CloseConsole()
EndIf</lang> Using the maze produced in Maze generation#PureBasic, this additional code will find and display the path between two random maze cells. A working example requires combining the two code listings by placing the 'maze generation' code at the beginning of the 'maze solving' code.
Sample output:
Solution found for path between (3, 2) and (7, 1) +---+---+---+---+---+---+---+---+---+---+ | v < < < < | | v < < | + +---+---+---+ + + +---+ +---+ | > v | ^ | | v | @ | ^ < | +---+ +---+---+ + + + +---+ + | | v | > ^ | v | ^ | ^ | + + + +---+---+---+ + +---+ + | v < | | > ^ | > ^ | + +---+---+---+---+ +---+ + + + | v | | | | ^ | | + +---+ + +---+---+---+---+ +---+ | > > v | | > v | ^ < | +---+---+ +---+---+---+ + +---+ + | > > > > ^ | > > ^ | +---+---+---+---+---+---+---+---+---+---+
Python
<lang Python>
- python 3
def Dijkstra(Graph, source):
+ +---+---+ | 0 1 2 | +---+ + + | 3 4 | 5 +---+---+---+
>>> graph = ( # or ones on the diagonal ... (0,1,0,0,0,0,), ... (1,0,1,0,1,0,), ... (0,1,0,0,0,1,), ... (0,0,0,0,1,0,), ... (0,1,0,1,0,0,), ... (0,0,1,0,0,0,), ... ) ... >>> Dijkstra(graph, 0) ([0, 1, 2, 3, 2, 3], [1e+140, 0, 1, 4, 1, 2]) >>> display_solution([1e+140, 0, 1, 4, 1, 2]) 5<2<1<0 # Graph[u][v] is the weight from u to v (however 0 means infinity) infinity = float('infinity') n = len(graph) dist = [infinity]*n # Unknown distance function from source to v previous = [infinity]*n # Previous node in optimal path from source dist[source] = 0 # Distance from source to source Q = list(range(n)) # All nodes in the graph are unoptimized - thus are in Q while Q: # The main loop u = min(Q, key=lambda n:dist[n]) # vertex in Q with smallest dist[] Q.remove(u) if dist[u] == infinity: break # all remaining vertices are inaccessible from source for v in range(n): # each neighbor v of u if Graph[u][v] and (v in Q): # where v has not yet been visited alt = dist[u] + Graph[u][v] if alt < dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u return dist,previous
def display_solution(predecessor):
cell = len(predecessor)-1 while cell: print(cell,end='<') cell = predecessor[cell] print(0)
</lang>
Racket
Following function returns a path between two cells in a maze which is created by the build-maze function (See Maze generation).
<lang racket>
- 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)))))
</lang>
Reading a maze from a file <lang racket>
- 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))))
</lang>
Printing out a maze with a path between two given cells <lang racket>
- 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))
</lang>
Example:
-> (define m (build-maze 14 7)) -> (with-output-to-file "maze" (λ () (show-maze m))) -> (show-maze (read-maze "maze")) +---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | + +---+---+---+---+ + + + +---+ +---+ + + | | | | | | | | | | +---+ + +---+ +---+ + + + +---+ +---+ + | | | | | | | | | | + + + + +---+---+---+ + + + + + +---+ | | | | | | | | | | + +---+ + + + +---+---+ + +---+---+---+ + | | | | | | | | | | + + +---+---+ +---+---+ + +---+---+ + + + | | | | | | | | + +---+---+---+ + + +---+---+---+ +---+---+ + | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+ -> (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. <lang ruby>class Maze
# Solve via breadth-first algorithm. # Each queue entry is a path, that is list of coordinates with the # last coordinate being the one that shall be visited next. def solve queue = [] path = nil
# Enqueue start position. enqueue_cell queue, [], @start_x, @start_y
# Loop as long as there are cells to visit and no solution has # been found yet. while !queue.empty? && !path path = solve_visit_cell queue end
# Clean up. reset_visiting_state
puts "No solution found?!" unless path
# Mark the cells that make up the shortest path. for x, y in path @path[y][x] = true end end
private
# Maze solving visiting method. def solve_visit_cell(queue) # Get the next path. path = queue.shift # The cell to visit is the last entry in the path. x, y = path.last
# Have we reached the end yet? if x == @end_x && y == @end_y # Yes, we have! return path end
# Mark cell as visited. @visited[y][x] = true
# Left new_x = x - 1 if move_valid?(new_x, y) && !@vertical_walls[y][new_x] enqueue_cell queue, path, new_x, y end
# Right new_x = x + 1 if move_valid?(new_x, y) && !@vertical_walls[y][x] enqueue_cell queue, path, new_x, y end
# Top new_y = y - 1 if move_valid?(x, new_y) && !@horizontal_walls[new_y][x] enqueue_cell queue, path, x, new_y end
# Bottom new_y = y + 1 if move_valid?(x, new_y) && !@horizontal_walls[y][x] enqueue_cell queue, path, x, new_y end
# No solution yet. return nil end
# Enqueue a new coordinate to visit. def enqueue_cell(queue, path, x, y) # Copy the current path, add the new coordinates and enqueue # the new path. path = path.dup path << [x, y] queue << path end
end
- Demonstration:
maze = Maze.new 20, 10 maze.solve maze.print </lang> Example output:
+---+---+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+ | | | o o o o o | | o o | o o o | | + +---+ +---+ + + +---+---+---+ + + +---+ + +---+ +---+ + | | | | | o | | o o | | | o o | | o | | + + + +---+---+ + + +---+ +---+ +---+ +---+---+ + + +---+ | | | | | o o | o o | | | | o o | | + + +---+---+ +---+---+ + +---+---+ + +---+ + + +---+---+ + | | | | o | o o o | | | | o o o o | + +---+---+ +---+---+ + +---+---+ +---+---+ +---+ +---+---+---+ + | | | | o o | | o | | o o | o | +---+---+ +---+ + + +---+ + + +---+---+---+---+ +---+ + + + | | | | | o o | o o o | | o o | o o | + + +---+ +---+---+---+---+---+ +---+---+ + +---+---+ +---+---+---+ | | | | o | | o | | | o | | + +---+ +---+---+---+---+---+ + +---+ + +---+ + + +---+---+ + | | | | | o o o | o o | | o | | + + +---+---+ + + +---+---+---+---+ +---+ +---+---+ + +---+---+ | | | | | | o o o o | o o | o o o | | + + +---+ +---+ +---+ + +---+---+---+ +---+ +---+---+---+---+ + | | | o o o | o o o | +---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
Tcl
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).
<lang tcl>oo::define maze {
method solve {} {
### Initialization of visited matrix and location/path queue set visited [lrepeat $x [lrepeat $y 0]] set queue {0 0 {}}
### Loop to do the searching ### while 1 { # Check for running out of path; an error in maze construction if {[llength $queue] == 0} { error "cannot reach finish" } # Visit the next square from the queue set queue [lassign $queue cx cy path] if {[lindex $visited $cx $cy]} continue lset visited $cx $cy 1 lappend path $cx $cy # Check for reaching the goal if {$cx == $x-1 && $cy == $y-1} break # Add the square in each direction to the queue if a move there is legal foreach {dx dy} {0 1 1 0 0 -1 -1 0} { set nx [expr {$cx + $dx}]; set ny [expr {$cy + $dy}] if { $nx >= 0 && $nx < $x && $ny >= 0 && $ny < $y && ($dx && idx($verti, min($cx,$nx), $cy) || $dy && idx($horiz, $cx, min($cy,$ny))) } then { lappend queue $nx $ny $path } } }
### Loop to set up the path rendering ### # (-2,-2) is just a marker that isn't next to the maze at all, so # guaranteeing the use of the last 'else' clause foreach {cx cy} $path {nx ny} [concat [lrange $path 2 end] -2 -2] { if {$nx-$cx == 1} { lset content $cx $cy "v" } elseif {$nx-$cx == -1} { lset content $cx $cy "^" } elseif {$ny-$cy == -1} { lset content $cx $cy "<" } else { lset content $cx $cy ">" } }
### Return the path ### return $path
}
}
- Do the solution (we ignore the returned path here...)
m solve
- Print it out
puts [m view]</lang> Example output:
+ +---+---+---+---+---+---+---+---+---+---+ | v | | + +---+ +---+---+---+---+---+---+---+ + | v | | > v | > v | | | + + +---+ + + + + + +---+ + | v | > ^ | v | ^ | v | | | | + +---+ +---+ + + + +---+ +---+ | v | > ^ | v < | ^ | v | | | | + + +---+ +---+ + + +---+ + + | > ^ | v < | > ^ | v | | | +---+---+ +---+ +---+ +---+ +---+---+ | v < < | > ^ | v < | > > > v | + +---+---+ +---+ +---+ +---+---+ + | > v | ^ < | > > ^ | | v | +---+ +---+---+ +---+---+---+ + + + | > > > ^ | | > +---+---+---+---+---+---+---+---+---+---+---+