Maze solving: Difference between revisions
Content deleted Content added
(45 intermediate revisions by 16 users not shown) | |||
Line 1:
{{task|Games}}
[[Category:Recursion]]
[[Category:Puzzles]]
;Task:
For a maze generated by [[Maze generation|this task]], write a function
that finds (and displays) the shortest path between two cells.
Note that because these mazes are generated by the [[wp:Maze_generation_algorithm#Depth-first_search|Depth-first search]] algorithm, they contain no circular paths,
and a simple depth-first tree search can be used.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F dijkstra(graph, source)
V n = graph.len
V dist = [Float.infinity] * n
V previous = [-1] * n
dist[source] = 0
V Q = Array(0 .< n)
L !Q.empty
V u = min(Q, key' n -> @dist[n])
Q.remove(u)
I dist[u] == Float.infinity
L.break
L(v) 0 .< n
I graph[u][v] & (v C Q)
V alt = dist[u] + graph[u][v]
I alt < dist[v]
dist[v] = alt
previous[v] = u
R previous
F display_solution(predecessor)
V cell = predecessor.len - 1
L cell != 0
print(cell, end' ‘<’)
cell = predecessor[cell]
print(0)
V 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]
]
display_solution(dijkstra(graph, 0))</syntaxhighlight>
{{out}}
<pre>
5<2<1<0
</pre>
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.
<syntaxhighlight lang="action!">DEFINE TOP="0"
DEFINE RIGHT="1"
DEFINE BOTTOM="2"
DEFINE LEFT="3"
DEFINE WIDTH="160"
DEFINE HEIGHT="96"
DEFINE STACK_SIZE="5000"
BYTE ARRAY stack(STACK_SIZE)
INT stackSize
PROC InitStack()
stackSize=0
RETURN
BYTE FUNC IsEmpty()
IF stackSize=0 THEN
RETURN (1)
FI
RETURN (0)
BYTE FUNC IsFull()
IF stackSize>=STACK_SIZE THEN
RETURN (1)
FI
RETURN (0)
PROC Push(BYTE x,y)
IF IsFull() THEN Break() RETURN FI
stack(stackSize)=x stackSize==+1
stack(stackSize)=y stackSize==+1
RETURN
PROC Pop(BYTE POINTER x,y)
IF IsEmpty() THEN Break() RETURN FI
stackSize==-1 y^=stack(stackSize)
stackSize==-1 x^=stack(stackSize)
RETURN
PROC Push3(BYTE x,y,d)
IF IsFull() THEN Break() RETURN FI
stack(stackSize)=x stackSize==+1
stack(stackSize)=y stackSize==+1
stack(stackSize)=d stackSize==+1
RETURN
PROC Pop3(BYTE POINTER x,y,d)
IF IsEmpty() THEN Break() RETURN FI
stackSize==-1 d^=stack(stackSize)
stackSize==-1 y^=stack(stackSize)
stackSize==-1 x^=stack(stackSize)
RETURN
PROC FillScreen()
BYTE POINTER ptr ;pointer to the screen memory
INT screenSize=[3840]
ptr=PeekC(88)
SetBlock(ptr,screenSize,$55)
Color=0
Plot(0,HEIGHT-1) DrawTo(WIDTH-1,HEIGHT-1) DrawTo(WIDTH-1,0)
RETURN
PROC GetNeighbors(BYTE x,y BYTE ARRAY n BYTE POINTER count)
DEFINE WALL="1"
count^=0
IF y>2 AND Locate(x,y-2)=WALL THEN
n(count^)=TOP count^==+1
FI
IF x<WIDTH-3 AND Locate(x+2,y)=WALL THEN
n(count^)=RIGHT count^==+1
FI
IF y<HEIGHT-3 AND Locate(x,y+2)=WALL THEN
n(count^)=BOTTOM count^==+1
FI
IF x>2 AND Locate(x-2,y)=WALL THEN
n(count^)=LEFT count^==+1
FI
RETURN
PROC DrawConnection(BYTE POINTER x,y BYTE dir)
Plot(x^,y^)
IF dir=TOP THEN
y^==-2
ELSEIF dir=RIGHT THEN
x^==+2
ELSEIF dir=BOTTOM THEN
y^==+2
ELSE
x^==-2
FI
DrawTo(x^,y^)
RETURN
PROC Maze(BYTE x,y)
BYTE ARRAY stack,neighbors
BYTE dir,nCount
FillScreen()
Color=2
InitStack()
Push(x,y)
WHILE IsEmpty()=0
DO
Pop(@x,@y)
GetNeighbors(x,y,neighbors,@nCount)
IF nCount>0 THEN
Push(x,y)
dir=neighbors(Rand(nCount))
DrawConnection(@x,@y,dir)
Push(x,y)
FI
OD
RETURN
BYTE FUNC IsConnection(BYTE x,y,dir)
DEFINE WAY="2"
IF dir=TOP AND y>2 AND Locate(x,y-1)=WAY THEN
RETURN (1)
ELSEIF dir=RIGHT AND x<WIDTH-3 AND Locate(x+1,y)=WAY THEN
RETURN (1)
ELSEIF dir=BOTTOM AND y<HEIGHT-3 AND Locate(x,y+1)=WAY THEN
RETURN (1)
ELSEIF dir=LEFT AND x>2 AND Locate(x-1,y)=WAY THEN
RETURN (1)
FI
RETURN (0)
PROC Solve(BYTE x1,y1,x2,y2)
BYTE dir,x,y,lastX,lastY,back
Color=3
Plot(x1,y1)
Plot(x2,y2)
InitStack()
Push3(x1,y1,TOP)
WHILE IsEmpty()=0
DO
Pop3(@x,@y,@dir)
IF back THEN
Color=2
Plot(lastX,lastY)
DrawTo(x,y)
FI
IF IsConnection(x,y,dir) THEN
Color=3
Push3(x,y,dir+1)
DrawConnection(@x,@y,dir)
IF x=x2 AND y=y2 THEN
RETURN
FI
Push3(x,y,TOP)
back=0
ELSEIF dir<=LEFT THEN
Push3(x,y,dir+1)
back=0
ELSE
lastX=x
lastY=y
back=1
FI
OD
RETURN
PROC Main()
BYTE CH=$02FC,COLOR0=$02C4,COLOR1=$02C5,COLOR2=$02C6
BYTE x,y,x2,y2
Graphics(7+16)
COLOR0=$0A
COLOR1=$04
COLOR2=$A6
x=Rand((WIDTH RSH 1)-1) LSH 1+1
y=Rand((HEIGHT RSH 1)-1) LSH 1+1
Maze(x,y)
x=Rand((WIDTH RSH 1)-1) LSH 1+1
y=Rand((HEIGHT RSH 1)-1) LSH 1+1
x2=Rand((WIDTH RSH 1)-1) LSH 1+1
y2=Rand((HEIGHT RSH 1)-1) LSH 1+1
Solve(x,y,x2,y2)
DO UNTIL CH#$FF OD
CH=$FF
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Maze_solving.png Screenshot from Atari 8-bit computer]
=={{header|Ada}}==
Line 10 ⟶ 256:
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).
<
procedure Maze_Solver is
Line 82 ⟶ 328:
Search(Maze, X, Y) ; -- Will output *all* Solutions.
-- If there is no output, there is no solution.
end Maze_Solver;</
{{out|Example output:}}
Line 130 ⟶ 376:
=={{header|AutoHotkey}}==
Generator and solver combined.
<
SleepTime := 0
Line 314 ⟶ 560:
}
return
#IfWinActive</
Outputs:<pre>+---+---+---+---+---+---+---+---+---+---+
| ¦¦¦¦¦ | ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦¦¦¦¦ |
Line 341 ⟶ 587:
[[Image:mazesolve_bbc.gif|right]]
Maze generation code also included.
<
MazeHeight% = 9
MazeCell% = 50
Line 426 ⟶ 672:
ENDIF
NEXT
ENDPROC</
=={{header|C}}==
See [[Maze_generation#C|Maze generation]] for combined gen/solve code.
=={{header|C#}}==
{{trans|Go}}
<syntaxhighlight lang="C#">
using System;
using System.Text;
public class Maze
{
private char[,] cells;
private char[,] hWalls; // Horizontal walls
private char[,] vWalls; // Vertical walls
private Random rand = new Random();
public Maze(int rows, int cols)
{
cells = new char[rows, cols];
hWalls = new char[rows + 1, cols]; // Include walls for the bottom
vWalls = new char[rows, cols + 1]; // Include walls for the right side
// Initialize walls
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
hWalls[i, j] = '-';
vWalls[i, j] = '|';
}
}
// Set the outer walls for the bottom and right
for (int i = 0; i < cols; i++)
{
hWalls[rows, i] = '-';
}
for (int i = 0; i < rows; i++)
{
vWalls[i, cols] = '|';
}
}
public override string ToString()
{
var builder = new StringBuilder();
for (int i = 0; i < cells.GetLength(0); i++)
{
// Top walls
for (int j = 0; j < cells.GetLength(1); j++)
{
builder.Append("+");
builder.Append(hWalls[i, j] == '-' ? "---" : " ");
}
builder.AppendLine("+");
// Side walls and cells
for (int j = 0; j < cells.GetLength(1); j++)
{
builder.Append(vWalls[i, j] == '|' ? "| " : " ");
char cell = cells[i, j] == '\0' ? ' ' : cells[i, j];
builder.Append(cell + " ");
}
builder.AppendLine("|");
}
// Bottom walls
for (int j = 0; j < cells.GetLength(1); j++)
{
builder.Append("+---");
}
builder.AppendLine("+");
return builder.ToString();
}
public void Generate()
{
Generate(rand.Next(cells.GetLength(0)), rand.Next(cells.GetLength(1)));
}
private void Generate(int r, int c)
{
cells[r, c] = ' ';
int[] dirs = { 0, 1, 2, 3 };
Shuffle(dirs);
foreach (int dir in dirs)
{
switch (dir)
{
case 0: // Up
if (r > 0 && cells[r - 1, c] == '\0')
{
hWalls[r, c] = ' ';
Generate(r - 1, c);
}
break;
case 1: // Down
if (r < cells.GetLength(0) - 1 && cells[r + 1, c] == '\0')
{
hWalls[r + 1, c] = ' ';
Generate(r + 1, c);
}
break;
case 2: // Right
if (c < cells.GetLength(1) - 1 && cells[r, c + 1] == '\0')
{
vWalls[r, c + 1] = ' ';
Generate(r, c + 1);
}
break;
case 3: // Left
if (c > 0 && cells[r, c - 1] == '\0')
{
vWalls[r, c] = ' ';
Generate(r, c - 1);
}
break;
}
}
}
private void Shuffle(int[] array)
{
for (int i = array.Length - 1; i > 0; i--)
{
int j = rand.Next(i + 1);
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
public void Solve(int startRow, int startCol, int endRow, int endCol)
{
if (Solve(startRow, startCol, endRow, endCol, -1))
{
cells[startRow, startCol] = 'S';
cells[endRow, endCol] = 'F';
}
}
private bool Solve(int r, int c, int endRow, int endCol, int dir)
{
if (r == endRow && c == endCol) return true;
// Up
if (dir != 1 && r > 0 && hWalls[r, c] == ' ' && Solve(r - 1, c, endRow, endCol, 0))
{
cells[r, c] = '^';
return true;
}
// Down
if (dir != 0 && r < cells.GetLength(0) - 1 && hWalls[r + 1, c] == ' ' && Solve(r + 1, c, endRow, endCol, 1))
{
cells[r, c] = 'v';
return true;
}
// Right
if (dir != 3 && c < cells.GetLength(1) - 1 && vWalls[r, c + 1] == ' ' && Solve(r, c + 1, endRow, endCol, 2))
{
cells[r, c] = '>';
return true;
}
// Left
if (dir != 2 && c > 0 && vWalls[r, c] == ' ' && Solve(r, c - 1, endRow, endCol, 3))
{
cells[r, c] = '<';
return true;
}
return false;
}
}
class Program
{
static void Main(string[] args)
{
var maze = new Maze(4, 7);
maze.Generate();
Random rand = new Random();
maze.Solve(rand.Next(4), rand.Next(7), rand.Next(4), rand.Next(7));
Console.WriteLine(maze);
}
}
</syntaxhighlight>
{{out}}
<pre>
+---+---+---+---+---+---+---+
| | | v S |
+ +---+ +---+ + +---+
| | | | > v |
+---+---+ + +---+---+ +
| | | | F |
+ +---+---+ + + + +
| | |
+---+---+---+---+---+---+---+
</pre>
=={{header|C++}}==
Line 435 ⟶ 883:
[[File:maze_solving_cpp.png|300px]]
<
#include <windows.h>
#include <iostream>
Line 872 ⟶ 1,320:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
=={{header|Clojure}}==
<
(:require [clojure.string :as str]))
Line 980 ⟶ 1,428:
(replace-cells maze (breadth-first-search maze [1 1] [19 19]) :track))
(println (maze->str solved-maze))</
{{in}}
Line 1,031 ⟶ 1,479:
{{incorrect|D|Is output double spaced, with only two dots above the E rather than 4, see comment [[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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.
<
std.file, std.conv;
Line 1,072 ⟶ 1,520:
maze[end.y][end.x] = 'E';
writefln("%-(%s\n%)", maze);
}</
{{out}}
<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Line 1,095 ⟶ 1,543:
| . . . . . . S | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>
=={{header|Delphi}}==
<p>Code requires source code of [[Maze generation#Delphi|Maze generation]]</p>
<syntaxhighlight lang="pascal">procedure SolveMaze(var AMaze: TMaze; const S, E: TPoint);
var
Route : TRoute;
Position : TPoint;
V : TPoint; // delta vector
begin
ClearVisited(AMaze);
Position := S;
Route := TStack<TPoint>.Create;
with Position do
try
AMaze[x, y].Visited := True;
repeat
if (y > 0) and not AMaze[x, y-1].Visited and AMaze[x, y].PassTop then V := Point(0, -1) else
if (x < mwidth-1) and not AMaze[x+1, y].Visited and AMaze[x+1, y].PassLeft then V := Point(1, 0) else
if (y < mheight-1) and not AMaze[x, y+1].Visited and AMaze[x, y+1].PassTop then V := Point(0, 1) else
if (x > 0) and not AMaze[x-1, y].Visited and AMaze[x, y].PassLeft then V := Point(-1, 0) else
begin
if Route.Count = 0 then Exit; // we are back at start so no way found
Position := Route.Pop; // step back
Continue;
end;
Route.Push(Position); // save current position to route
Offset(V); // move forward
AMaze[x, y].Visited := True;
until Position = E; // solved
ClearVisited(AMaze);
while Route.Count > 0 do // Route to Maze
with Route.Pop do
AMaze[x, y].Visited := True;
finally
Route.Free;
end;
end;
procedure Main;
var
Maze: TMaze;
S, E: TPoint;
begin
Randomize;
PrepareMaze(Maze);
S := Point(Random(mwidth), Random(mheight));
E := Point(Random(mwidth), Random(mheight));
SolveMaze(Maze, S, E);
Write(MazeToString(Maze, S, E));
ReadLn;
end;
begin
Main;
end.</syntaxhighlight>
{{out}}
<pre>
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | S * * | |
+ + + +---+ + +---+---+---+ + +---+---+ +---+---+---+---+---+---+ +---+ + +
| | | | | | | | | | * | | | | |
+ + +---+ + +---+ +---+ +---+ + +---+ + +---+ +---+---+ +---+ + + +
| | | | | | | * * * | | | | | |
+ + +---+ +---+---+---+ +---+---+---+ +---+---+ +---+---+---+---+---+ +---+---+ +
| | | * * * * * | * | | | | | | |
+ +---+ +---+ +---+---+---+ +---+---+ + + +---+ + + +---+---+ + + +---+
| | | | * * * | | * * * | * * | | | | | | | |
+ + +---+ +---+---+ + +---+---+ +---+ +---+ + +---+---+---+ +---+ + + +
| | | | * | | * * * | | | | | |
+---+---+ +---+ + + + +---+ +---+---+---+ +---+---+ + + +---+ +---+---+ +
| | | | | * | | | | | | | | |
+ + + + +---+ + +---+ +---+---+ + +---+ +---+ + +---+ +---+ +---+---+
| | | | E * | * * | | | | | | | | | | |
+ +---+---+ +---+ +---+ + + + +---+ +---+ +---+---+ + +---+---+---+---+ +
| | | | * | * | | | | | | |
+ +---+ +---+ + +---+ +---+---+---+ +---+ +---+ + +---+---+ +---+ +---+---+
| | | | * * | * | | | | | | |
+---+---+ + + + + + + +---+---+---+ +---+ +---+---+ + +---+ +---+---+ +
| | | | | * * | | | | | | |
+ +---+---+ + +---+---+---+---+ + + +---+---+---+ +---+---+---+ +---+---+---+ +
| | | | | | | | | | |
+---+ +---+ +---+ + +---+---+---+ +---+ +---+ +---+---+ +---+---+ +---+---+---+
| | | | | | | | | | | | | | |
+ + + +---+ + +---+---+ + + + +---+ + + + + + + + + +---+ +
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|EasyLang}}==
[https://easylang.online/show/#cod=hVTbbqMwFHz3V4zUl1yEa1KQEmnZH0FoRcE0VsCOTJo2/fqVLxi7u9p9SfCcCz5zZpjFF0eFvCQSFQ7YYTbIHjkZDM4YnrGRyMBouSUjl5jqBhI7SPIE8tp2lzet3mUPxhi5atVhPquPX1P7xUFBCYBu5K02D4PSEKYtbgq+l8EBiAFTLRpUYB4B8IkKG4EM+RaT6iHX0CMK9eIehzo1Ko3T6bRCk7pzfGKHARkGPOOAR3xaMzXvbhiwQ07L5d9H7Sz2Zx45v4JRlhNK1DDMtbl4jRwSWY5NJrdoHBmTY+Kq5oWNqb6qOQwayDKHPvQ54AUFmpi0Ar36kDeF3N+nRwXdyl5NEAskNCrYG/V13yzkmmdU6GuR0G0utTc1jd1JK/sAGiUsgYjGtCTaVDRmKE5po4TL3sQrpx6zOk9Re+GJXv4hE6+RPKwiyZVp1iEczRv/BiGDNGL/MyR9aK2yrzt7l3je89KnmZIEJyspZ7d1N77jjZIwNFkV8ISFEH2xVHZqXDixVjBYaoZHAgcjOAt0aiSp+PdW7oUXvz/ZAqG7kdvzCy0JJW+jem1HDNba1BtbjXduNstiPYvBZ61S0fz2rmUgLcxzYiyxT+nrnSwcQb7Ff1qqYRV/YaXktXBetFAklticsYcaLHN5iF3VbD57TrXONUJHFjG1P366iYM75DfpO1Y2Jne/7KYwj7b9mhfxFFVH9Egcj8ckEoiKYPrdVi4pJ+4ezMrxQMhv Run it]
<syntaxhighlight lang=text>
n = 2 * size + 1
f = 100 / (n - 0.5)
len m[] n * n
#
background 000
proc show_maze . .
clear
if m[i] = 0
y = (i - 1) div n
color 999
move x * f - f / 2 y * f - f / 2
rect f * 1.5 f * 1.5
sleep 0.01
.
offs[] = [ 1 n -1 (-n) ]
proc
show_maze
for i = 4 downto 1
d = random i
dir = offs[d[d]]
d[d] = d[i]
if m[pos + dir] = 1 and m[pos + 2 * dir] = 1
m[pos + dir] = 0
m_maze pos + 2 * dir
.
.
endpos = n * n - 1
proc make_maze . .
for i = 1 to len m[]
.
for
m[
h = 2 * random 15 - n + n * 2 * random 15
m_maze h
m[endpos] = 0
.
make_maze
show_maze
#
proc mark pos col . .
x
y = (pos
color
move x * f + f / 4 y * f + f / 4
circle f / 3.5
.
proc solve
if found = 1
mark
sleep
if pos = endpos
return
.
of = random 4 - 1
for h = 1 to 4
dir = (h + of) mod1 4
posn = pos + offs[dir]
if dir <> dir0 and m[posn]
if found =
sleep 0.08
.
.
.
sleep 1
solve 0 n + 2
</syntaxhighlight>
=={{header|EGL}}==
<
// First and last columns/rows are "dead" cells. Makes generating
Line 1,457 ⟶ 1,988:
end
end</
{{out|Output example (for 10x10 maze)}}
<pre>
Line 1,505 ⟶ 2,036:
</pre>
=={{header|
{{libheader|cl-lib}}
<syntaxhighlight lang="lisp">(require 'cl-lib)
(cl-defstruct maze rows cols data)
Line 1,763 ⟶ 2,232:
(print-maze maze solution)))
(solve "maze.txt")</syntaxhighlight>
{{out}}
<pre style="height:35ex;overflow:scroll;">+ +---+---+---+---+---+---+---+---+---+
Line 1,798 ⟶ 2,256:
| | | * |
+---+---+---+---+---+---+---+---+---+ +
</pre>
=={{header|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.
<syntaxhighlight lang="erlang">
-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.
</syntaxhighlight>
{{out}}
<pre>
8> maze_solving:task().
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| . . . . | . . . . | . . . . | |
+---+ +---+---+ + +---+---+ + +---+---+ + +---+ +
| . . | | . . | | . . | | . . | |
+ +---+ + +---+---+ +---+---+---+ + +---+ +---+ +
| . | | | | | . | | |
+ +---+ +---+---+ + + +---+---+ +---+---+ + +---+
| . . | | | | | | | . . | . | |
+ + + + + +---+ + +---+---+---+ + + +---+ +
| | . | | | S . | . . | |
+---+ +---+---+ +---+---+---+ +---+---+---+ +---+---+ +
| . . | . . | | . . | | | | |
+ + + + +---+ + + + + +---+ + + +---+---+
| . | | . | . | | . | . | | G . | | | |
+ +---+ + +---+---+ + +---+---+ + +---+---+---+ +
| . . . | . . . . | . . . . | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
Line 1,807 ⟶ 2,330:
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 [[Maze generation#Haskell|Haskell]] or [[Maze generation#Java|Java]] generators.
<
import frege.IO
Line 1,879 ⟶ 2,402:
brin <- BufferedReader.fromISR isrin
lns <- BufferedReader.getlines brin
printStr $ unlines $ fromMaybe ["can't solve"] $ solve lns</
{{out}}
Line 1,906 ⟶ 2,429:
=={{header|Go}}==
Generates maze, picks start and finish cells randomly, solves, prints.
<
import (
Line 2,068 ⟶ 2,591:
rSolve(ra, ca, -1)
m.c2[ra][ca] = 'S'
}</
{{out|Example output:}}
<pre>
Line 2,089 ⟶ 2,612:
<!-- ugh, syntax colorer seems to not understand that single quote (prime) can be part of an identifier -->
<
import Data.Maybe (fromMaybe)
Line 2,157 ⟶ 2,680:
let main_ = unlines . fromMaybe ["can_t solve"] . solve . lines
in interact main_
</syntaxhighlight>
{{out}}
<pre>
Line 2,184 ⟶ 2,707:
Replace the main with this:
<
/mh := \A[1] | 12
/mw := \A[2] | 16
Line 2,196 ⟶ 2,719:
until Event() == &lpress # wait
close(mz.window)
end</
And include this after the Generator and Display procedures.
<
static maze,h,w,rd
Line 2,235 ⟶ 2,758:
}
return mz
end</
The following Unicon-only solution is a variant of the above. It shares the same
Line 2,244 ⟶ 2,767:
cyclic paths. The shortest solution path is then marked and displayed.
<
import Utils # To get 'Args' singleton class
Line 2,373 ⟶ 2,896:
procedure waitForCompletion()
critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)
end</
=={{header|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
<syntaxhighlight lang="j">
maze=:4 :0
assert.0<:n=.<:x*y
Line 2,474 ⟶ 2,997:
'o' cells } a NB. exercise, replace cells with a gerund to draw arrows on the path.
)
</syntaxhighlight>
Example:<pre>
4 (display~ solve)@maze 20
Line 2,489 ⟶ 3,012:
=={{header|Java}}==
<
import java.util.*;
Line 2,637 ⟶ 3,160:
System.out.println (solvedLines[i]);
}
}</
{{out}}
<pre>
Line 2,663 ⟶ 3,186:
Uses code from maze generation task
{{works with|Java|8}}
<
import java.awt.event.*;
import java.awt.geom.Path2D;
Line 2,844 ⟶ 3,367:
});
}
}</
=={{header|JavaScript}}==
Animated: generating and solving.<br />To start solving, click to choose a 'start' and an 'end' points.
<br />Go [http://paulo-jorente.de/tests/mazesolver/ 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() {
Line 2,985 ⟶ 3,508:
createMaze();
}
</syntaxhighlight>
HTML to test.
<pre>
Line 2,998 ⟶ 3,521:
{{trans|Python}}
<
+ +---+---+
| 1 2 3 |
Line 3,077 ⟶ 3,600:
dist, path = dijkstra(graph)
printpath(path, 6)</
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.io.File
Line 3,197 ⟶ 3,720:
val solvedLines = expandHorizontally(maze)
println(solvedLines.joinToString("\n"))
}</
{{out}}
Line 3,242 ⟶ 3,765:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
===Graph===
Solving the maze generated in [[Maze_generation#Graph]]:
<
{{Out}}
[[File:MathematicaMazeGraphSolving.png]]
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import random, strutils
type
Direction {.pure.} = enum None, Up, Left, Down, Right
Maze = object
cells: seq[string]
hwalls: seq[string]
vwalls: seq[string]
####################################################################################################
# Maze creation.
func initMaze(rows, cols: Positive): Maze =
## Initialize a maze description.
var h = repeat('-', cols)
var v = repeat("|", cols)
for i in 0..<rows:
result.cells.add newString(cols)
result.hwalls.add h
result.vwalls.add v
proc gen(maze: var Maze; r, c: Natural) =
## Generate a maze starting from point (r, c).
maze.cells[r][c] = ' '
var dirs = [Up, Left, Down, Right]
dirs.shuffle()
for dir in dirs:
case dir
of None:
discard
of Up:
if r > 0 and maze.cells[r-1][c] == '\0':
maze.hwalls[r][c] = chr(0)
maze.gen(r-1, c)
of Left:
if c > 0 and maze.cells[r][c-1] == '\0':
maze.vwalls[r][c] = chr(0)
maze.gen(r, c-1)
of Down:
if r < maze.cells.high and maze.cells[r+1][c] == '\0':
maze.hwalls[r+1][c] = chr(0)
maze.gen(r+1, c)
of Right:
if c < maze.cells[0].high and maze.cells[r][c+1] == '\0':
maze.vwalls[r][c+1] = chr(0)
maze.gen(r, c+1)
proc gen(maze: var Maze) =
## Generate a maze, choosing a random starting point.
maze.gen(rand(maze.cells.high), rand(maze.cells[0].high))
####################################################################################################
# Maze solving.
proc solve(maze: var Maze; ra, ca, rz, cz: Natural) =
## Solve a maze by finding the path from point (ra, ca) to point (rz, cz).
proc rsolve(maze: var Maze; r, c: Natural; dir: Direction): bool {.discardable.} =
## Recursive solver.
if r == rz and c == cz:
maze.cells[r][c] = 'F'
return true
if dir != Down and maze.hwalls[r][c] == '\0':
if maze.rSolve(r-1, c, Up):
maze.cells[r][c] = '^'
maze.hwalls[r][c] = '^'
return true
if dir != Up and r < maze.hwalls.high and maze.hwalls[r+1][c] == '\0':
if maze.rSolve(r+1, c, Down):
maze.cells[r][c] = 'v'
maze.hwalls[r+1][c] = 'v'
return true
if dir != Left and c < maze.vwalls[0].high and maze.vwalls[r][c+1] == '\0':
if maze.rSolve(r, c+1, Right):
maze.cells[r][c] = '>'
maze.vwalls[r][c+1] = '>'
return true
if dir != Right and maze.vwalls[r][c] == '\0':
if maze.rSolve(r, c-1, Left):
maze.cells[r][c] = '<'
maze.vwalls[r][c] = '<'
return true
maze.rsolve(ra, ca, None)
maze.cells[ra][ca] = 'S'
####################################################################################################
# Maze display.
func `$`(maze: Maze): string =
## Return the string representation fo a maze.
const
HWall = "+---"
HOpen = "+ "
VWall = "| "
VOpen = " "
RightCorner = "+\n"
RightWall = "|\n"
for r, hw in maze.hwalls:
for h in hw:
if h == '-' or r == 0:
result.add HWall
else:
result.add HOpen
if h notin {'-', '\0'}: result[^2] = h
result.add RightCorner
for c, vw in maze.vwalls[r]:
if vw == '|' or c == 0:
result.add VWall
else:
result.add VOpen
if vw notin {'|', '\0'}: result[^4] = vw
if maze.cells[r][c] != '\0': result[^2] = maze.cells[r][c]
result.add RightWall
for _ in 1..maze.hwalls[0].len:
result.add HWall
result.add RightCorner
#———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
const
Width = 8
Height = 8
randomize()
var maze = initMaze(Width, Height)
maze.gen()
var ra, rz = rand(Width - 1)
var ca, cz = rand(Height - 1)
while rz == ra and cz == ca:
# Make sur starting and ending points are different.
rz = rand(Width - 1)
cz = rand(Height - 1)
maze.solve(ra, ca , rz, cz)
echo maze</syntaxhighlight>
{{out}}
<pre>+---+---+---+---+---+---+---+---+
| | > > > > > > > > > > v |
+ + ^ +---+---+---+---+ v + +
| | ^ < < | | v | |
+ +---+ ^ + +---+ + v +---+
| | ^ | | | > > v |
+ +---+ ^ +---+---+ +---+ v +
| | ^ | | v |
+---+ + ^ + + +---+---+ v +
| | ^ | | | v |
+ +---+ ^ +---+---+ + + v +
| > > > > ^ | | | | v |
+ ^ +---+---+ + +---+ + v +
| ^ < < | F | | v |
+---+ ^ + ^ +---+---+---+---+ v +
| S | ^ < < < < < < < < < < |
+---+---+---+---+---+---+---+---+</pre>
=={{header|Perl}}==
This example includes maze generation code.
<
#!perl
use strict;
Line 3,329 ⟶ 4,031:
print "Could not solve!\n";
}
</syntaxhighlight>
{{out}}
<pre>Here is the maze:
Line 3,376 ⟶ 4,078:
+--+--+--+--+--+--+--+--+--+--+
</pre>
=={{header|Phix}}==
Combined generator and solver.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\Maze_solving.exw
-- =============================
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wall</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"---"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">cell</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"|"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">" ? "</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wall</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">cell</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">amaze</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- mark cell visited</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">4</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">h</span> <span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'?'</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- knock down wall</span>
<span style="color: #000000;">amaze</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dy</span> <span style="color: #000080;font-style:italic;">-- door location (in a wall!)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">solve_maze</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"-:-:"</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- mark path</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">}={</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'o'</span> <span style="color: #000080;font-style:italic;">-- mark cell</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solve_maze</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- unmark cell</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- unmark path</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">heads</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- toin coss 50:50 true(1)/false(0)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{(</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">amaze</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- mark start pos</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'*'</span>
<span style="color: #000080;font-style:italic;">-- add a random door (heads=rhs/lhs, tails=top/btm)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">heads</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">heads</span><span style="color: #0000FF;">()*</span><span style="color: #000000;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #008080;">else</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">heads</span><span style="color: #0000FF;">()*</span><span style="color: #000000;">h</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solve_maze</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,630 ⟶ 4,165:
| | o - o - o - o | | |
+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">main =>
Maze0 = ["+---+---+---+---+---+---+---+---+",
"| | | | |",
"+ + + +---+ + +---+ +",
"| | | | | |",
"+---+---+ + +---+---+ + +",
"| | | | |",
"+---+ + + +---+---+---+ +",
"| | | | |",
"+ + + +---+---+---+ + +",
"| | | | | |",
"+ + + +---+ +---+---+ +",
"| | | | | |",
"+ +---+---+ +---+---+---+ +",
"| | | |",
"+ +---+ +---+ + +---+ +",
"| | | |",
"+---+---+---+---+---+---+---+---+"],
MaxR = len(Maze0) div 2,
MaxC = len(Maze0[1]) div 4,
Maze = new_array(MaxR,MaxC),
foreach (R in 1..MaxR, C in 1..MaxC)
Maze[R,C] = 0
end,
fill_maze(Maze0,Maze,1),
solve_maze(Maze,(1,1),(MaxR,MaxC),Cost,Plan),
OutputMaze = new_array(MaxR,MaxC),
foreach ((R,C) in Plan)
OutputMaze[R,C] = '*'
end,
output_maze(Maze0,OutputMaze,1).
fill_maze([Line1,Line2|Maze0],Maze,R) =>
fill_maze_cols(Line1,Maze,R,1),
fill_maze_cols(Line2,Maze,R,1),
fill_maze(Maze0,Maze,R+1).
fill_maze(_,_,_) => true.
fill_maze_cols(['+',' ',' ',' '|Line],Maze,R,C) =>
Maze[R,C] := Maze[R,C] \/ 4, % up
Maze[R-1,C] := Maze[R-1,C] \/ 8, % down
fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols([' ',' ',' ',' '|Line],Maze,R,C) =>
Maze[R,C] := Maze[R,C] \/ 1, % left
Maze[R,C-1] := Maze[R,C-1] \/ 2, % right
fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols([_,_,_,_|Line],Maze,R,C) =>
fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols(_,_,_,_) => true.
table (+,+,+,min,-)
solve_maze(_Maze,FPos,FPos,Cost,Plan) =>
Cost = 0,
Plan = [FPos].
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 1 == 1, % left
solve_maze(Maze,(R,C-1),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 2 == 2, % right
solve_maze(Maze,(R,C+1),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 4 == 4, % up
solve_maze(Maze,(R-1,C),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 8 == 8, % down
solve_maze(Maze,(R+1,C),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
output_maze([Line1,Line2|Maze0],Maze,R) =>
output_maze_cols(Line1,Maze,R,1),
output_maze_cols(Line2,Maze,R,1),
output_maze(Maze0,Maze,R+1).
output_maze([Line],_,_) => println(Line).
output_maze_cols([' ',' ',' ',' '|Line],Maze,R,C) =>
if Maze[R,C] == '*' then
print(" * ")
else
print(" ")
end,
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(['|',' ',' ',' '|Line],Maze,R,C) =>
if Maze[R,C] == '*' then
print("| * ")
else
print("| ")
end,
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(['+',' ',' ',' '|Line],Maze,R,C) =>
if Maze[R,C] == '*' && Maze[R-1,C] == '*' then
print("+ * ")
else
print("+ ")
end,
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols([C1,C2,C3,C4|Line],Maze,R,C) =>
printf("%c%c%c%c",C1,C3,C3,C4),
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(Line,_,_,_) => println(Line).
</syntaxhighlight>
{{out}}
<pre>
+---+---+---+---+---+---+---+---+
| * | * * | | |
+ * + * + * +---+ + +---+ +
| * * | * | | | |
+---+---+ * + +---+---+ + +
| | * | | |
+---+ + * + +---+---+---+ +
| | * | | |
+ + + * +---+---+---+ + +
| | | * | | |
+ + + * +---+ +---+---+ +
| | | * * | | |
+ +---+---+ * +---+---+---+ +
| | * * | * * * |
+ +---+ +---+ * + * +---+ * +
| | * * | * |
+---+---+---+---+---+---+---+---+
</pre>
=={{header|PicoLisp}}==
<
(let (Path NIL Best NIL Dir " > ")
(recur (This Path Dir)
Line 3,648 ⟶ 4,312:
(=: 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':
<pre>: (shortestPath 'a8 'k1 (maze 11 8))
Line 3,673 ⟶ 4,337:
Works with SWI-Prolog and XPCE.
<
:- dynamic maze/3.
:- dynamic path/1.
Line 3,821 ⟶ 4,485:
\+cell(L, C1).
</syntaxhighlight>
output : [[File:Prolog-Maze-solved.jpg]]
=={{header|PureBasic}}==
<
Procedure displayMazePath(Array maze(2), List Path.POINT())
Line 3,934 ⟶ 4,598:
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.
Line 3,956 ⟶ 4,620:
=={{header|Python}}==
<syntaxhighlight lang="python">
# python 3
Line 4,007 ⟶ 4,671:
cell = predecessor[cell]
print(0)
</syntaxhighlight>
=={{header|Racket}}==
Following function returns a path between two cells in a maze which is created by the <tt>build-maze</tt> function (See [[Maze_generation#Racket|Maze generation]]).
<
;; Returns a path connecting two given cells in the maze
;; find-path :: Maze Cell Cell -> (Listof Cell)
Line 4,029 ⟶ 4,693:
(append-map (next-turn (list p1))
(alternatives p1 (list p1)))))
</syntaxhighlight>
Reading a maze from a file
<
;; Reads the maze from the textual form
;; read-maze :: File-path -> Maze
Line 4,051 ⟶ 4,715:
1))
(maze N M tbl))))
</syntaxhighlight>
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)
Line 4,077 ⟶ 4,741:
(displayln "+"))
(newline))
</syntaxhighlight>
Example:
Line 4,116 ⟶ 4,780:
| * * * * * | | * * * * |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2017.02}}
(Includes maze generation code.)
<syntaxhighlight lang="raku" line>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 );</syntaxhighlight>
{{out}}
<small><pre>┌ ╵ ────┬───────────────┬───────────────┬───────────────────────────────┬───────────┬───────────────┬───────────────┐
│ ╵ · · │ ╷ ╴ ╴ ╴ ╴ │ │ ╷ ╴ ╴ · · · · · · · · · · · · │ ╷ ╴ ╴ · · │ · · · · · · · │ · · · · · · · │
│ ╵ ╶───┘ ╷ ╶───┐ ╵ ╷ │ ╷ ╶───────┤ ╷ ╷ ╵ ╶───────┬───────┐ · ┌───┘ ╷ ╷ ╵ ╷ · │ · ╶───┬───╴ · │ · ╷ · ┌───╴ · │
│ ╵ ╴ ╴ ╴ ╴ · · │ ╵ │ │ │ │ ╷ │ ╵ ╴ ╴ ╴ ╴ │ ╷ ╴ ╴ │ · │ ╷ ╴ ╴ │ ╵ │ · │ · · · │ · · · │ · │ · │ · · · │
│ · ┌───────────┤ ╵ │ └───┴───────╴ │ ╷ ├───────┐ ╵ ╵ ╷ ╷ ╵ └───┘ ╷ ┌───┘ ╵ │ · │ · ╷ · │ · ┌───┴───┘ · │ · ╶───┤
│ · │ ╶ ╶ ╶ ╶ ╷ │ ╵ │ │ ╷ │ │ ╵ ╴ ╴ │ ╵ ╴ ╴ ╴ ╴ │ ╶ ╶ ╵ │ · │ · │ · │ · │ · · · · · │ · · · │
│ · │ ╵ ╶───┐ ╷ ╵ ╵ ├───────────────╴ │ ╷ └───╴ └───────┼───┬───────┤ ╵ ┌───┤ · ├───┘ · │ · │ · ╷ · ┌───┴───┐ · │
│ · │ ╵ ╴ ╴ │ ╶ ╶ ╵ │ │ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╶ ╷ │ · │ ╶ ╶ ╷ │ ╵ │ · │ · │ · · · │ · │ · │ · │ · · · │ · │
│ · └───┐ ╵ ├───────┴───────┐ ╶───────┴───────┬───────╴ ╷ │ · │ ╵ ╷ ╷ │ ╵ │ · │ · │ · ┌───┤ · │ · │ · │ · ╷ · ╵ · │
│ · · · │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │ │ ╷ ╴ ╴ ╴ ╴ │ · │ ╵ │ ╷ │ ╵ │ · │ · │ · │ · │ · │ · │ · │ · │ · · · │
├───╴ · │ ╵ │ ╷ ╶───────┐ ╵ ├───────────────┐ │ ╷ ╶───┬───┘ · │ ╵ │ ╷ ╵ ╵ │ · ╵ · ╵ · │ · ╵ · └───┘ · │ · ├───────┤
│ · · · │ ╵ │ ╶ ╶ ╶ ╶ ╷ │ ╵ │ ╷ ╴ ╴ ╴ ╴ ╴ ╴ │ │ ╶ ╶ ╷ │ · · · │ ╵ │ ╶ ╶ ╵ │ · · · · · │ · · · · · · · │ · │ · · · │
│ · ┌───┤ ╵ └───────╴ ╷ │ ╵ ╵ ╷ ┌───────┐ ╵ │ └───┐ ╷ └───┐ · │ ╵ ├───────┼───────┬───┴───────┬───┬───┘ · ├───╴ · │
│ · │ · │ ╵ ╴ ╴ ╴ ╴ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ ╵ │ │ ╶ ╶ ╷ │ · │ ╵ │ ╷ ╴ ╴ │ ╷ ╴ ╴ │ ╷ ╴ ╴ ╴ ╴ │ · │ · · · │ · · · │
│ · ╵ · ├───────────────┴───────┴───┐ · │ ╵ └───────┴───┐ ╷ │ · │ ╵ ╵ ╷ ╷ ╵ ╵ ╷ ╷ ╵ │ ╷ ┌───╴ ╵ │ · │ · ╶───┤ · ╶───┤
│ · · · │ · · · · · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ · · │ ╷ │ · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ ╵ │ ╷ │ ╶ ╶ ╵ │ · │ · · · │ · · · │
├───┐ · │ · ┌───────────╴ · ┌───┐ · │ · └───┬───╴ ╵ ┌───┘ ╷ │ · ├───────┴───────┤ ╵ ╵ ╷ │ ╵ ╶───┤ · └───┐ · │ · ╷ · │
│ · │ · │ · │ · · · · · · · │ · │ · │ · · · │ ╶ ╶ ╵ │ ╷ ╴ ╴ │ · │ · · · · · · · │ ╵ ╴ ╴ │ ╵ ╴ ╴ │ · · · │ · │ · │ · │
│ · │ · └───┘ · ┌───────────┘ · │ · ├───╴ · │ ╵ ┌───┘ ╷ ┌───┘ · │ · ╷ · ┌───╴ · └───────┴───┐ ╵ └───┐ · ╵ · ├───┘ · │
│ · │ · · · · · │ · · · · · · · │ · │ · · · │ ╵ │ ╷ ╴ ╴ │ · · · │ · │ · │ · · · · · · · · · │ ╵ ╴ ╴ │ · · · │ · · · │
│ · ├───────╴ · ├───┐ · ┌───┐ · ╵ · │ · ╶───┤ ╵ ╵ ╷ ┌───┘ · ╶───┤ · │ · └───┬───╴ · ┌───────┤ · ╷ ╵ │ · ╶───┘ · ╷ · │
│ · │ · · · · · │ │ · │ · │ · · · │ · · · │ ╵ ╴ ╴ │ · · · · · │ · │ · · · │ · · · │ ╶ ╶ ╷ │ · │ ╵ │ · · · · · │ · │
│ · ╵ · ┌───────┘ │ · ╵ · └───────┤ · ╷ · └───────┴───────┐ · ╵ · └───┐ · └───┐ · │ ╵ ╷ ╷ └───┘ ╵ ├───────────┤ · │
│ · · · │ │ · · · · · · · │ · │ · · · · · · · · · │ · · · · · │ · · · │ · │ ╵ │ ╶ ╶ ╶ ╶ ╵ │ ╷ ╴ ╴ ╴ ╴ │ · │
│ · ╶───┤ ╶───────┴───┬───────┐ · ├───┘ · ┌───────────┐ · ├───────────┴───╴ · │ · │ ╵ └───────┐ · │ ╷ ┌───╴ ╵ │ · │
│ · · · │ │ · · · │ · │ · · · │ · · · · · │ · │ · · · · · · · · · │ · │ ╵ ╴ ╴ ╴ ╴ │ · │ ╷ │ ╶ ╶ ╵ │ · │
├───┐ · ├───────┬───╴ │ · ╷ · │ · │ · ┌───┤ · ╶───────┤ · │ · ╶───────┬───┐ · ├───┴───────┐ ╵ └───┘ ╷ │ ╵ ┌───┴───┤
│ · │ · │ │ │ · │ · │ · │ · │ · │ · · · · · │ · │ · · · · · │ · │ · │ │ ╵ ╴ ╴ ╴ ╴ │ ╵ │ ╷ ╴ ╴ │
│ · │ · │ ╷ ╵ ┌───┘ · │ · ╵ · ╵ · │ · ╵ · ┌───┐ · ╵ · └───────╴ · │ · ╵ · │ ┌───╴ └───────┐ · │ ╵ ╵ ╷ ╷ ╵ │
│ · │ · │ │ │ · · · │ · · · · · │ · · · │ · │ · · · · · · · · · │ · · · │ │ │ · │ ╵ ╴ ╴ │ ╵ │
│ · │ · │ └───┬───┴───────┴───┬───────┤ · ┌───┘ · ├───────────────────┴───────┤ └───────────┐ └───┴───────┤ ╵ │
│ · │ · │ │ │ │ · │ · · · │ │ │ │ ╵ │
│ · ╵ · ├───┐ │ ╶───────┐ ╵ ╷ │ · ╵ · ╷ · │ ╶───────────────────┐ └───┬───────┐ └───────┬───┐ │ ╵ │
│ · · · │ · │ │ │ │ │ · · · │ · │ │ │ │ │ │ │ ╵ │
│ · ╶───┤ · │ └───────┐ ├───────┤ └───┬───┴───┼───────────┬───────┐ ├───┐ ╵ ╷ ├───────┐ │ │ │ ╵ │
│ · · · │ · │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╵ │
├───╴ · ╵ · └───────┐ ╵ │ ╷ └───╴ ╵ ╷ ╵ ┌───╴ ╵ ╷ ╵ │ └───────┘ ╵ ╷ ╵ │ ╵ ╵ ╵ │
│ · · · · · · · · · │ │ │ │ │ │ │ │ │ ╵ │
└───────────────────┴───────┴───┴───────────────┴───────┴───────────┴───────┴───────────────────┴───────┴──────── │ ┘</pre></small>
=={{header|Red}}==
(imports maze generation code, see http://rosettacode.org/wiki/Maze_generation#Red)
<syntaxhighlight lang="red">Red ["Maze solver"]
do %mazegen.red
print [
"start:" start: random size - 1x1
"end:" end: random size - 1x1
]
isnew?: function [pos] [not find visited pos]
open?: function [pos d] [
o: pos/y * size/x + pos/x + 1
0 = pick walls/:o d
]
expand: function [pos][
either any [
all [pos/x > 0 isnew? p: pos - 1x0 open? p 1]
all [pos/x < (size/x - 1) isnew? p: pos + 1x0 open? pos 1]
all [pos/y > 0 isnew? p: pos - 0x1 open? p 2]
all [pos/y < (size/y - 1) isnew? p: pos + 0x1 open? pos 2]
][append visited p insert path p][remove path]
path/1
]
path: reduce [start]
visited: []
until [end = expand path/1]
print reverse path</syntaxhighlight>
{{out}}
<pre>Maze width: 15
Maze height: 15
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | | | _ |_ | _ _ _|
| _|_| |_ _| | | _| |_ | |
| |_ _| _ _| | _ _ _|_ _| |
|_ |_ | | _ _|_ _| _ | |
| _| _| | | _ _ _|_ _|_|
|_ _ _| _ _| |_| _ _ |_| |
| _| _|_ _ _ | | _|_ _ _| |
| | _| _ _ |_ |_ _ | | |
| _| _| _|_ |_ _ _|_ _| |
|_ | | _ | _| _ _ |_| |
| |_ _| | |_ _ _| | | _| |
| | _ _| |_ _ _ | |_ _|_ |_|
| |_ | |_ |_ _ _|_ _ _ |_ |
| _| | |_ | | | _| |
|_ _ _ _|_ _|_ _|_ _|_ _ _ _|_|
start: 2x4 end: 12x3
2x4 3x4 3x3 2x3 2x2 3x2 3x1 3x0 4x0 4x1 5x1 5x0 6x0 7x0 7x1 7x2 7x3 6x3 5x3 5x4 5x5 4x5 3x5 3x6 2x6 2x7 1x7 1x8 0x8 0x9 1x9 1x10 2x10 2x9 2x8 3x8 3x7 4x7 5x7 6x7 6x8 7x8 7x9 6x9 6x10 7x10 8x10 8x9 9x9 10x9 11x9 11x10 11x11 10x11 10x10 9x10 9x11 9x12 10x12 11x12 12x12 12x13 11x13 11x14 12x14 13x14 13x13 14x13 14x12 13x12 13x11 12x11 12x10 13x10 13x9 14x9 14x8 14x7 14x6 14x5 13x5 13x6 12x6 11x6 11x5 10x5 9x5 8x5 8x6 8x7 7x7 7x6 6x6 6x5 6x4 7x4 8x4 9x4 10x4 10x3 11x3 12x3
</pre>
=={{header|Ruby}}==
This solution extends the [[Maze generation#Ruby|maze generator script]]. To get a working script, copy & paste both parts into one file.
<
# Solve via breadth-first algorithm.
# Each queue entry is a path, that is list of coordinates with the
Line 4,194 ⟶ 5,082:
maze = Maze.new 20, 10
maze.solve
maze.print</
Example output:
Line 4,223 ⟶ 5,111:
=={{header|Rust}}==
This solution reuses the [[Maze generation#Rust|maze generator Rust code]]. The modified and new parts are marked with the label "MAZE SOLVING".Uses the [https://crates.io/crates/rand rand] library.
<
const WIDTH: usize = 16;
Line 4,475 ⟶ 5,363:
println!("The maze, solved:");
maze.paint(true);
}</
{{out}}
Line 4,546 ⟶ 5,434:
| * * | * * | * * * | * * * |
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>
=={{header|Swift}}==
{{works with|Swift|3}}
The following requires the use of the implementation for [[Maze generation#Swift|generation task]]. Assumes there will be no circular paths through the maze as the problem suggests.
<pre>
enum errors: Error {
//Occurs when a start or end position is given that is outside of bounds
case IndexOutsideMazeBoundary
}
///Used to solve any maze generated by the swift implementation of maze generator at:
///https://www.rosettacode.org/wiki/Maze_generation#Swift
class MazeSolver {
///your starting index position in the maze
var startPos: (Int, Int)
/// the end index position you are trying to reach within the maze
var endPos: (Int, Int)
/// a maze of [[INT]] where each value is between 1 and 14.
/// each number representing a
var maze: [[Int]]
var visitedSpaces: [(Int, Int)]
init(maze: [[Int]]) {
self.startPos = (0, 0)
self.endPos = (0, 0)
/// a maze that consists of a array of ints from 1-14 organized to
/// create a maze like structure.
/// Each number represents where the walls and paths will be
/// ex. 2 only has a path south and 12 has paths E or W
self.maze = maze
/// spaces each branch has visited to stop from searching previously explored
/// areas of the maze
self.visitedSpaces = []
}
/// determine if the user has previously visited the given location within the maze
func visited(position: (Int, Int)) -> Bool {
return visitedSpaces.contains(where: {$0 == position})
}
/// used to translate the mazes number scheme to a list of directions available
/// for each number. DirectionDiff for N would be (0, -1) for example
func getDirections(positionValue: Int) -> [(Int, Int)] {
switch positionValue {
case 1:
return [Direction.north.diff]
case 2:
return [Direction.south.diff]
case 3:
return [Direction.north.diff, Direction.south.diff]
case 4:
return [Direction.east.diff]
case 5:
return [Direction.north.diff, Direction.east.diff]
case 6:
return [Direction.south.diff, Direction.east.diff]
case 7:
return [Direction.north.diff, Direction.east.diff, Direction.south.diff]
case 8:
return [Direction.west.diff]
case 9:
return [Direction.north.diff, Direction.west.diff]
case 10:
return [Direction.west.diff, Direction.south.diff]
case 11:
return [Direction.north.diff, Direction.south.diff, Direction.west.diff]
case 12:
return [Direction.west.diff, Direction.east.diff]
case 13:
return [Direction.north.diff, Direction.east.diff, Direction.west.diff]
case 14:
return [Direction.east.diff, Direction.south.diff, Direction.west.diff]
default:
return []
}
}
/// calculate and return all paths branching from the current position that haven't been explored yet
func availablePaths(currentPosition: (Int, Int), lastPos: (Int, Int)) -> [(Int, Int)] {
/// all available paths to be returned
var paths: [(Int, Int)] = []
/// the maze contents at the given position (ie the maze number)
let positionValue = maze[currentPosition.0][ currentPosition.1]
/// used to build the new path positions and check them before they
/// are added to paths
var workingPos: (Int, Int)
// is the maze at a dead end and not our first position
if ([1, 2, 4, 8].contains(positionValue) && currentPosition != lastPos) {
return []
}
/// the directions available based on the maze contents of our
/// current position
let directions: [(Int, Int)] = getDirections(positionValue: positionValue)
/// build the paths
for pos in directions {
workingPos = (currentPosition.0 + pos.0, currentPosition.1 + pos.1)
if (currentPosition == lastPos || (workingPos != lastPos && !visited(position: workingPos))) {
paths.append(workingPos)
}
}
return paths
}
/// prints a model of the maze with
/// O representing the start point
/// X representing the end point
/// * representing traveled space
/// NOTE: starting pos and end pos represent indexes and thus start at 0
func solveAndDisplay(startPos: (Int, Int), endPos: (Int, Int)) throws {
if (startPos.0 >= maze.count || startPos.1 >= maze[0].count) {
throw errors.IndexOutsideMazeBoundary
}
/// the position you are beginning at in the maze
self.startPos = startPos
/// the position you wish to get to within the maze
self.endPos = endPos
/// spaces each branch has visited to stop from searching previously explored
/// areas of the maze
self.visitedSpaces = []
self.displaySolvedMaze(finalPath: solveMaze(startpos: startPos, pathSoFar: [])!)
}
/// recursively solves our maze
private func solveMaze(startpos: (Int, Int), pathSoFar: [(Int, Int)]) -> [(Int, Int)]? {
/// marks our current position in the maze
var currentPos: (Int, Int) = startpos
/// saves the spaces visited on this current branch
var currVisitedSpaces : [(Int, Int)] = [startpos]
/// the final path (or the path so far if the end pos has not been reached)
/// from the start position to the end position
var finalPath: [(Int, Int)] = pathSoFar
/// all possible paths from our current position that have not been explored
var possiblePaths: [(Int, Int)] = availablePaths(currentPosition: startpos, lastPos: pathSoFar.last ?? startpos)
// move through the maze until you come to a position that has been explored, the end position, or a dead end (the
// possible paths array is empty)
while (!possiblePaths.isEmpty) {
// found the final path
guard (currentPos != self.endPos) else {
finalPath.append(contentsOf: currVisitedSpaces)
return finalPath
}
// multiple valid paths from current position found
// recursively call new branches for each valid path
if (possiblePaths.count > 1) {
visitedSpaces.append(contentsOf: currVisitedSpaces)
finalPath.append(contentsOf: currVisitedSpaces)
// for each valid path recursively call each path
// and if it contains the final path
// ie it found the endpoint, return that path
for pos in possiblePaths {
let path = solveMaze(startpos: pos, pathSoFar: finalPath)
if (path != nil) {
return path
}
}
// otherwise this branch and it's sub-branches
// are dead-ends so kill this branch
return nil
}
// continue moving along the only path available
else {
// update current path to our only available next
// position
currentPos = possiblePaths[0]
// calculate the available paths from our new
// current position
possiblePaths = availablePaths(currentPosition: currentPos, lastPos: currVisitedSpaces.last ?? currentPos)
// update the visited spaces for this branch
currVisitedSpaces.append(currentPos)
}
}
// if our new current position is the endpos return our final path
if (currentPos == self.endPos) {
finalPath.append(contentsOf: currVisitedSpaces)
return finalPath
}
else {
return nil
}
}
// Reference: https://www.rosettacode.org/wiki/Maze_generation#Swift
// adapts the display method used in the swift implementation of the maze generator we used for this app to display the maze
// solved
func displaySolvedMaze(finalPath: [(Int, Int)]) {
/// all cells are 3 wide in the x axis
let cellWidth = 3
for j in 0..<y {
// Draw top edge
// if mark corner with +, add either (cell width) spaces or - to the topedge var dependin on if it is a wall or not
var topEdge = ""
for i in 0..<x {
topEdge += "+"
topEdge += String(repeating: (maze[i][j] & Direction.north.rawValue) == 0 ? "-" : " ", count: cellWidth)
}
topEdge += "+"
print(topEdge)
// Draw left edge
//through the center of the cell if is a wall add | if not a space
// then if it is travelled add " * " otherwise just 3 spaces then
//cap it with a | at the end for the right most wall
var leftEdge = ""
for i in 0..<x {
leftEdge += (maze[i][j] & Direction.west.rawValue) == 0 ? "|" : " "
if (finalPath.first! == (i, j)) {
leftEdge += " O "
}
else if (finalPath.last! == (i, j)) {
leftEdge += " X "
}
else {
if (finalPath.contains(where: {$0 == (i, j)})) {
leftEdge += " * "
}
else {
leftEdge += String(repeating: " ", count: cellWidth)
}
}
}
leftEdge += "|"
print(leftEdge)
}
// Draw bottom edge
// adds + on corners and _ everywhere else
var bottomEdge = ""
for _ in 0..<x {
bottomEdge += "+"
bottomEdge += String(repeating: "-", count: cellWidth)
}
bottomEdge += "+"
print(bottomEdge)
}
}
</pre>
<pre>
example implementation using the aforementioned maze generator code for the swift implementation on rosettaCode
let x = 20
let y = 10
let maze = MazeGenerator(x, y)
var solver: MazeSolver = MazeSolver(maze: maze.maze)
do {
// making sure the start and end pos are within the maze boundary
try solver.solveAndDisplay(startPos: (0, 0), endPos: (5, 5))
}
catch errors.IndexOutsideMazeBoundary {
print("[ERROR] given start or end point outside of bounds")
}
</pre>
{{out}}<pre>
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| O * | | * * | * * | * * * * * * * * * | |
+---+ + +---+ + + + + +---+---+---+---+---+---+---+ + +---+ +
| * * | | * | * * | * | * | | * * | * * * * | | |
+ +---+---+ + +---+---+ + +---+ + + + +---+---+---+---+ + +
| * | | * | | * * | * * * | * | * * | | |
+ +---+ + + + + +---+---+---+ + +---+---+---+ +---+---+---+ +
| * | | | * * | * * | * * | * * * * | | |
+ + +---+ +---+ +---+ + + +---+---+---+---+ + +---+ +---+ +
| * | | | * * | * | | * | * * * | * * | | | | |
+ + + +---+ +---+ + +---+ + +---+ + +---+ + + + +---+
| * | | | | X * | * * | * | * | * * | | | | | |
+ + +---+ +---+ +---+---+ + + +---+---+---+ + + +---+---+ +
| * | | | | | * | * | * * * | | | |
+ +---+ +---+ +---+---+ + + +---+---+ + +---+---+---+ + + +
| * * | | * * | * * * | | | | |
+---+ + +---+---+---+---+---+---+---+ +---+---+ + +---+ + +---+ +
| | * | | * * * * | * * | * * | | | | | | |
+ + +---+---+ +---+---+ + + +---+ + + + + +---+---+---+ +
| * * * * | * * | * * * | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
This script assumes that the contents of the [[Maze generation#Tcl|generation task]] have already been <code>source</code>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 <tt>queue</tt> variable being used as a queue).
<
method solve {} {
### Initialization of visited matrix and location/path queue
Line 4,605 ⟶ 5,783:
m solve
# Print it out
puts [m view]</
Example output:
<pre>
Line 4,625 ⟶ 5,803:
| > > > ^ | | >
+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|Uiua}}==
Just add the following lines to the end of [https://rosettacode.org/wiki/Maze_generation#Uiua the generator]. It shows you the maze that has been solved with the path highlighted, the list of moves, and the total path length.
<syntaxhighlight lang="uiua">
# You can delete from here to SOLVE THE MAZE
# if you're appending this to the maze generator code.
# Experimental!
["+-+-+-+-+-+-+"
"|. . .|. . .|"
"+-+-+ + + + +"
"|.|. .|.|.|.|"
"+ + +-+-+ + +"
"|.|. . . .|.|"
"+ +-+-+-+-+ +"
"|. . . . . .|"
"+-+-+-+-+-+-+"]
H ← 4
W ← 6
Nfour ← +⊙¤[¯2_0 2_0 0_2 0_¯2] # Gives N4
InBounds ← ▽⊸≡(↧⊃(/↧≥1_1|/↧< +1 × 2 H_W))
GetWall ← -:⊡1:÷2/-.
# S O L V E T H E M A Z E #
.
Start ← 1_1
End ← -Start ×2 H_W
Heur ← /+⌵-End # Manhattan distance.
# (pos grid) -> 1-4 next steps, in bounds, without walls in the way.
Ns ← ≡⊡1▽:⟜(≡(=@ ⊡)⊙¤≡GetWall)≡⊟¤:InBounds Nfour.
astar(Ns|Heur|≍End) Start # Solve (costs = 1 => djikstra)
$"_ moves" ⊙⟜(⍜(⊡|+33)):°□⊢
</syntaxhighlight>
{{out}}
<pre>
╭─
╷ "+-+-+-+-+-+-+"
"|O O O|. O O|"
"+-+-+ + + + +"
"|.|O O|.|O|O|"
"+ + +-+-+ + +"
"|.|O O O O|O|"
"+ +-+-+-+-+ +"
"|. . . . . O|"
"+-+-+-+-+-+-+"
╯
╭─
╷ 1 1
1 3
1 5
3 5
3 3
5 3
5 5
5 7
5 9
3 9
1 9
1 11
3 11
5 11
7 11
╯
"14 moves"
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-ioutil}}
<syntaxhighlight lang="wren">import "os" for Process
import "./ioutil" for File, FileUtil
/*
* 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
* character list, because we'll want mutability when drawing the solution later.
*/
var decimateHorizontally = Fn.new { |lines|
var width = ((lines[0].count + 1)/2).floor
var c = List.filled(lines.count, null)
for (i in 0...lines.count) {
c[i] = List.filled(width, null)
for (j in 0...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.
*/
var solveMazeRecursively // recursive function
solveMazeRecursively = Fn.new { |maze, x, y, d|
var ok = false
var i = 0
while (i < 4 && !ok) {
if (i != d) {
// 0 = up, 1 = right, 2 = down, 3 = left
if (i == 0) {
if (maze[y - 1][x] == " ") ok = solveMazeRecursively.call(maze, x, y - 2, 2)
} else if (i == 1) {
if (maze[y][x + 1] == " ") ok = solveMazeRecursively.call(maze, x + 2, y, 3)
} else if (i == 2) {
if (maze[y + 1][x] == " ") ok = solveMazeRecursively.call(maze, x, y + 2, 0)
} else if (i == 3) {
if (maze[y][x - 1] == " ") ok = solveMazeRecursively.call(maze, x - 2, y, 1)
}
}
i = i + 1
}
// 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] = "*"
if (d == 0) {
maze[y - 1][x] = "*"
} else if (d == 1) {
maze[y][x + 1] = "*"
} else if (d == 2) {
maze[y + 1][x] = "*"
} else if (d == 3) {
maze[y][x - 1] = "*"
}
}
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.
*/
var solveMaze = Fn.new { |maze|
solveMazeRecursively.call(maze, maze[0].count - 2, maze.count - 2, -1)
}
/*
* Opposite of decimateHorizontally(). Adds extra characters to make
* the maze "look right", and converts each line from a char list to a
* string at the same time.
*/
var expandHorizontally = Fn.new { |maze|
var tmp = List.filled(3, " ")
var lines = List.filled(maze.count, null)
for (i in 0...maze.count) {
var sb = ""
for (j in 0...maze[i].count) {
if (j % 2 == 0) {
sb = sb + maze[i][j]
} else {
for (k in 0..2) tmp[k] = maze[i][j]
if (tmp[1] == "*") {
tmp[0] = " "
tmp[2] = " "
}
sb = sb + tmp.join()
}
}
lines[i] = sb
}
return lines
}
/*
* Accepts a maze as generated by:
* http://rosettacode.org/wiki/Maze_generation#Wren
* in a file whose name is specified as a command-line argument.
*/
var args = Process.arguments
if (args.count != 1) {
System.print("The maze file to be read should be passed as a single command line argument.")
return
}
if (!File.exists(args[0])) {
System.print("Sorry %(args[0]) does not exist.")
return
}
var lines = FileUtil.readLines(args[0]).where { |l| l != "" }.toList
var maze = decimateHorizontally.call(lines)
solveMaze.call(maze)
var solvedLines = expandHorizontally.call(maze)
System.print(solvedLines.join("\n"))</syntaxhighlight>
{{out}}
Using the same maze.txt as the Kotlin example:
<pre>
+---+---+---+---+---+---+---+---+
| * * * * * | * * * * * | |
+---+---+ * + + * +---+ * + +
| | * | | * | | * * * |
+ + + * +---+ * + +---+ * +
| | | * | * * * | * |
+ + + * + * +---+---+---+ * +
| | | * | * * * * * * * | * |
+---+ + * +---+---+---+ * + * +
| | * | * * * * * | * | * |
+ +---+ * + * +---+ * + * + * +
| | * * * | * * * | * * * | * |
+ + * +---+---+ * +---+---+ * +
| * * * | * * * | * * * | * * * |
+ * +---+ * + * +---+ * + * +---+
| * * * * * | * * * * * | * * * |
+---+---+---+---+---+---+---+---+
</pre>
Line 4,630 ⟶ 6,018:
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.
<
fcn munge(a,b){ String(a[0,2],b,a[3,*]) } // "+---" --> "+-*-"
Line 4,672 ⟶ 6,060:
ver[endy][endx] =munge(ver[endy][endx],"E");
foreach a,b in (hor.zip(ver)) { println(a.concat(),"\n",b.concat()) }
}</
{{out}}
<pre>
|