Maze solving: Difference between revisions
m
→{{header|EasyLang}}
(Emacs Lisp: Avoid non-portable shebang) |
|||
| (21 intermediate revisions by 6 users not shown) | |||
Line 15:
{{trans|Python}}
<
V n = graph.len
V dist = [Float.infinity] * n
Line 50:
]
display_solution(dijkstra(graph, 0))</
{{out}}
Line 59:
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.
<
DEFINE RIGHT="1"
DEFINE BOTTOM="2"
Line 248:
DO UNTIL CH#$FF OD
CH=$FF
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Maze_solving.png Screenshot from Atari 8-bit computer]
Line 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 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 376:
=={{header|AutoHotkey}}==
Generator and solver combined.
<
SleepTime := 0
Line 560:
}
return
#IfWinActive</
Outputs:<pre>+---+---+---+---+---+---+---+---+---+---+
| ¦¦¦¦¦ | ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦¦¦¦¦ |
Line 587:
[[Image:mazesolve_bbc.gif|right]]
Maze generation code also included.
<
MazeHeight% = 9
MazeCell% = 50
Line 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 681 ⟶ 883:
[[File:maze_solving_cpp.png|300px]]
<
#include <windows.h>
#include <iostream>
Line 1,118 ⟶ 1,320:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
=={{header|Clojure}}==
<
(:require [clojure.string :as str]))
Line 1,226 ⟶ 1,428:
(replace-cells maze (breadth-first-search maze [1 1] [19 19]) :track))
(println (maze->str solved-maze))</
{{in}}
Line 1,277 ⟶ 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,318 ⟶ 1,520:
maze[end.y][end.x] = 'E';
writefln("%-(%s\n%)", maze);
}</
{{out}}
<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Line 1,344 ⟶ 1,546:
=={{header|Delphi}}==
<p>Code requires source code of [[Maze generation#Delphi|Maze generation]]</p>
<
var
Route : TRoute;
Line 1,398 ⟶ 1,600:
begin
Main;
end.</
{{out}}
<pre>
Line 1,434 ⟶ 1,636:
=={{header|EasyLang}}==
[https://easylang.dev/show/#cod=hZTbbqMwFEXf/RVb6ksuwjUpSIk0zI8gNKJgGitgRyZNm379yBeM3RnNvCT4XIy9zt7M4oujQl4SiQoH7DCbyB45GUycMTxjI5GB0XJLRi4x1Q0kdpDkCeS17S5vWr3LHowxctWqw3xWH7+m9ouDghIA3chbbR4GpSHMtrgp+L1MHIAYMNWiQQXmIwA+UWEjkCHfYlI95Jp6RKle3ONUp0alcTqd1tCk7hyf2GFAhgHPOOARr9ZKzbsbBuyQ03L591l7F/szj5xfwSjLCSVqGObaHLxGDoksxyaTWzQOxuRIXNW80Jjqq5rDRQMss+jDPge8oEATQyvQqw95U8j9eXpU0K3shbxBLDGhUcEeqa/7ZqFrnlGhr0XC25xqb3oaO5RW9iFopLAkIo5pSzSq6J6hOeVGCZe9yVdOPmZ2nlF74Ylg/qETL5I8zCKplWnVISzNG/8WQgZp1P5nSvrU2mVfd/Y2WcDnpa8zPWmCrFjObvAOgCNHSbg2WUXwhAWJvliYnRoXKtYNJpb64ZGEgxecCzo1klT/e6v4wuvfr2yD0N3I7fqFloSSt1G9tiMG627qva3GOzezZbGkxeCrVrFofnvXMmAL9zkxljio9P1OGA6Q3+I/W6oh0n9h1eTlcF7kUCSu2Jyxhxosujzkrmo2nz4nXGccoSOXmN4fP92Vg0HkN/U7LBtTu1+GU5hHu/1aF4GKuiM+EsfjMckEUlGYfneWK8qJOwezgjyQ3w== Run it]
<syntaxhighlight>
size = 15
n = 2 * size + 1
len m[] n * n
#
background 000
proc show_maze . .
clear
for i
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) ]
show_maze
d[]
for i = 4 downto 1
d = randint 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 * randint 15 - n + n * 2 * randint 15
m_maze h
m[endpos] = 0
.
show_maze
#
proc mark pos col . .
color col
move
circle f / 3.5
.
proc solve
if found = 1
mark pos 900
sleep 0.05
if pos = endpos
found = 1
return
.
of = randint 4 - 1
for h = 1 to 4
dir = (h + of) mod1 4
posn = pos + offs[dir]
if dir <> dir0 and m[posn]
if found = 0
sleep 0.
.
.
.
sleep 1
</syntaxhighlight>
=={{header|EGL}}==
<
// First and last columns/rows are "dead" cells. Makes generating
Line 1,787 ⟶ 1,988:
end
end</
{{out|Output example (for 10x10 maze)}}
<pre>
Line 1,839 ⟶ 2,040:
{{libheader|cl-lib}}
<
(cl-defstruct maze rows cols data)
Line 2,031 ⟶ 2,232:
(print-maze maze solution)))
(solve "maze.txt")</
{{out}}
Line 2,059 ⟶ 2,260:
=={{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 ).
Line 2,099 ⟶ 2,300:
{ok, Cells} -> {ok, Cells}
end.
</syntaxhighlight>
{{out}}
<pre>
Line 2,129 ⟶ 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 2,201 ⟶ 2,402:
brin <- BufferedReader.fromISR isrin
lns <- BufferedReader.getlines brin
printStr $ unlines $ fromMaybe ["can't solve"] $ solve lns</
{{out}}
Line 2,228 ⟶ 2,429:
=={{header|Go}}==
Generates maze, picks start and finish cells randomly, solves, prints.
<
import (
Line 2,390 ⟶ 2,591:
rSolve(ra, ca, -1)
m.c2[ra][ca] = 'S'
}</
{{out|Example output:}}
<pre>
Line 2,411 ⟶ 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,479 ⟶ 2,680:
let main_ = unlines . fromMaybe ["can_t solve"] . solve . lines
in interact main_
</syntaxhighlight>
{{out}}
<pre>
Line 2,506 ⟶ 2,707:
Replace the main with this:
<
/mh := \A[1] | 12
/mw := \A[2] | 16
Line 2,518 ⟶ 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,557 ⟶ 2,758:
}
return mz
end</
The following Unicon-only solution is a variant of the above. It shares the same
Line 2,566 ⟶ 2,767:
cyclic paths. The shortest solution path is then marked and displayed.
<
import Utils # To get 'Args' singleton class
Line 2,695 ⟶ 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,796 ⟶ 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,811 ⟶ 3,012:
=={{header|Java}}==
<
import java.util.*;
Line 2,959 ⟶ 3,160:
System.out.println (solvedLines[i]);
}
}</
{{out}}
<pre>
Line 2,985 ⟶ 3,186:
Uses code from maze generation task
{{works with|Java|8}}
<
import java.awt.event.*;
import java.awt.geom.Path2D;
Line 3,166 ⟶ 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 3,307 ⟶ 3,508:
createMaze();
}
</syntaxhighlight>
HTML to test.
<pre>
Line 3,320 ⟶ 3,521:
{{trans|Python}}
<
+ +---+---+
| 1 2 3 |
Line 3,399 ⟶ 3,600:
dist, path = dijkstra(graph)
printpath(path, 6)</
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.io.File
Line 3,519 ⟶ 3,720:
val solvedLines = expandHorizontally(maze)
println(solvedLines.joinToString("\n"))
}</
{{out}}
Line 3,567 ⟶ 3,768:
===Graph===
Solving the maze generated in [[Maze_generation#Graph]]:
<
{{Out}}
[[File:MathematicaMazeGraphSolving.png]]
Line 3,573 ⟶ 3,774:
=={{header|Nim}}==
{{trans|Go}}
<
type
Line 3,729 ⟶ 3,930:
cz = rand(Height - 1)
maze.solve(ra, ca , rz, cz)
echo maze</
{{out}}
Line 3,752 ⟶ 3,953:
=={{header|Perl}}==
This example includes maze generation code.
<
#!perl
use strict;
Line 3,830 ⟶ 4,031:
print "Could not solve!\n";
}
</syntaxhighlight>
{{out}}
<pre>Here is the maze:
Line 3,880 ⟶ 4,081:
=={{header|Phix}}==
Combined generator and solver.
<!--<
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\Maze_solving.exw
Line 3,944 ⟶ 4,145:
<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>
<!--</
{{out}}
<pre>
Line 3,964 ⟶ 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,982 ⟶ 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 4,007 ⟶ 4,337:
Works with SWI-Prolog and XPCE.
<
:- dynamic maze/3.
:- dynamic path/1.
Line 4,155 ⟶ 4,485:
\+cell(L, C1).
</syntaxhighlight>
output : [[File:Prolog-Maze-solved.jpg]]
=={{header|PureBasic}}==
<
Procedure displayMazePath(Array maze(2), List Path.POINT())
Line 4,268 ⟶ 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 4,290 ⟶ 4,620:
=={{header|Python}}==
<syntaxhighlight lang="python">
# python 3
Line 4,341 ⟶ 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,363 ⟶ 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,385 ⟶ 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,411 ⟶ 4,741:
(displayln "+"))
(newline))
</syntaxhighlight>
Example:
Line 4,456 ⟶ 4,786:
{{works with|Rakudo|2017.02}}
(Includes maze generation code.)
<syntaxhighlight lang="raku"
:N< ╵ >,
:E< ╶ >,
Line 4,585 ⟶ 4,915:
}
display solve gen_maze( 29, 19 );</
{{out}}
<small><pre>┌ ╵ ────┬───────────────┬───────────────┬───────────────────────────────┬───────────┬───────────────┬───────────────┐
Line 4,628 ⟶ 4,958:
=={{header|Red}}==
(imports maze generation code, see http://rosettacode.org/wiki/Maze_generation#Red)
<
do %mazegen.red
Line 4,652 ⟶ 4,982:
visited: []
until [end = expand path/1]
print reverse path</
{{out}}
<pre>Maze width: 15
Line 4,678 ⟶ 5,008:
=={{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,752 ⟶ 5,082:
maze = Maze.new 20, 10
maze.solve
maze.print</
Example output:
Line 4,781 ⟶ 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 5,033 ⟶ 5,363:
println!("The maze, solved:");
maze.paint(true);
}</
{{out}}
Line 5,104 ⟶ 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 5,163 ⟶ 5,783:
m solve
# Print it out
puts [m view]</
Example output:
<pre>
Line 5,188 ⟶ 5,808:
{{trans|Kotlin}}
{{libheader|Wren-ioutil}}
<
import "./ioutil" for File, FileUtil
/*
Line 5,306 ⟶ 5,926:
solveMaze.call(maze)
var solvedLines = expandHorizontally.call(maze)
System.print(solvedLines.join("\n"))</
{{out}}
Line 5,333 ⟶ 5,953:
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 5,375 ⟶ 5,995:
ver[endy][endx] =munge(ver[endy][endx],"E");
foreach a,b in (hor.zip(ver)) { println(a.concat(),"\n",b.concat()) }
}</
{{out}}
<pre>
| |||