Maze solving: Difference between revisions
Content deleted Content added
m fixed link |
→{{header|Uiua}}: Made the code standalone. |
||
(29 intermediate revisions by 12 users not shown) | |||
Line 11:
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 16 ⟶ 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 88 ⟶ 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 136 ⟶ 376:
=={{header|AutoHotkey}}==
Generator and solver combined.
<
SleepTime := 0
Line 320 ⟶ 560:
}
return
#IfWinActive</
Outputs:<pre>+---+---+---+---+---+---+---+---+---+---+
| ¦¦¦¦¦ | ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦¦¦¦¦ |
Line 347 ⟶ 587:
[[Image:mazesolve_bbc.gif|right]]
Maze generation code also included.
<
MazeHeight% = 9
MazeCell% = 50
Line 432 ⟶ 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 441 ⟶ 883:
[[File:maze_solving_cpp.png|300px]]
<
#include <windows.h>
#include <iostream>
Line 878 ⟶ 1,320:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
=={{header|Clojure}}==
<
(:require [clojure.string :as str]))
Line 986 ⟶ 1,428:
(replace-cells maze (breadth-first-search maze [1 1] [19 19]) :track))
(println (maze->str solved-maze))</
{{in}}
Line 1,037 ⟶ 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,078 ⟶ 1,520:
maze[end.y][end.x] = 'E';
writefln("%-(%s\n%)", maze);
}</
{{out}}
<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Line 1,104 ⟶ 1,546:
=={{header|Delphi}}==
<p>Code requires source code of [[Maze generation#Delphi|Maze generation]]</p>
<
var
Route : TRoute;
Line 1,158 ⟶ 1,600:
begin
Main;
end.</
{{out}}
<pre>
Line 1,194 ⟶ 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,547 ⟶ 1,988:
end
end</
{{out|Output example (for 10x10 maze)}}
<pre>
Line 1,596 ⟶ 2,037:
=={{header|Emacs Lisp}}==
<syntaxhighlight lang="lisp">(require 'cl-lib)
(cl-defstruct maze rows cols data)
Line 1,789 ⟶ 2,232:
(print-maze maze solution)))
(solve "maze.txt")</syntaxhighlight>
{{out}}
<pre style="height:35ex;overflow:scroll;">+ +---+---+---+---+---+---+---+---+---+
Line 1,828 ⟶ 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 1,868 ⟶ 2,300:
{ok, Cells} -> {ok, Cells}
end.
</syntaxhighlight>
{{out}}
<pre>
Line 1,898 ⟶ 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,970 ⟶ 2,402:
brin <- BufferedReader.fromISR isrin
lns <- BufferedReader.getlines brin
printStr $ unlines $ fromMaybe ["can't solve"] $ solve lns</
{{out}}
Line 1,997 ⟶ 2,429:
=={{header|Go}}==
Generates maze, picks start and finish cells randomly, solves, prints.
<
import (
Line 2,159 ⟶ 2,591:
rSolve(ra, ca, -1)
m.c2[ra][ca] = 'S'
}</
{{out|Example output:}}
<pre>
Line 2,180 ⟶ 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,248 ⟶ 2,680:
let main_ = unlines . fromMaybe ["can_t solve"] . solve . lines
in interact main_
</syntaxhighlight>
{{out}}
<pre>
Line 2,275 ⟶ 2,707:
Replace the main with this:
<
/mh := \A[1] | 12
/mw := \A[2] | 16
Line 2,287 ⟶ 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,326 ⟶ 2,758:
}
return mz
end</
The following Unicon-only solution is a variant of the above. It shares the same
Line 2,335 ⟶ 2,767:
cyclic paths. The shortest solution path is then marked and displayed.
<
import Utils # To get 'Args' singleton class
Line 2,464 ⟶ 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,565 ⟶ 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,580 ⟶ 3,012:
=={{header|Java}}==
<
import java.util.*;
Line 2,728 ⟶ 3,160:
System.out.println (solvedLines[i]);
}
}</
{{out}}
<pre>
Line 2,754 ⟶ 3,186:
Uses code from maze generation task
{{works with|Java|8}}
<
import java.awt.event.*;
import java.awt.geom.Path2D;
Line 2,935 ⟶ 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,076 ⟶ 3,508:
createMaze();
}
</syntaxhighlight>
HTML to test.
<pre>
Line 3,089 ⟶ 3,521:
{{trans|Python}}
<
+ +---+---+
| 1 2 3 |
Line 3,168 ⟶ 3,600:
dist, path = dijkstra(graph)
printpath(path, 6)</
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.io.File
Line 3,288 ⟶ 3,720:
val solvedLines = expandHorizontally(maze)
println(solvedLines.joinToString("\n"))
}</
{{out}}
Line 3,333 ⟶ 3,765:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
===Graph===
Solving the maze generated in [[Maze_generation#Graph]]:
<
{{Out}}
[[File:MathematicaMazeGraphSolving.png]]
Line 3,342 ⟶ 3,774:
=={{header|Nim}}==
{{trans|Go}}
<
type
Line 3,498 ⟶ 3,930:
cz = rand(Height - 1)
maze.solve(ra, ca , rz, cz)
echo maze</
{{out}}
Line 3,521 ⟶ 3,953:
=={{header|Perl}}==
This example includes maze generation code.
<
#!perl
use strict;
Line 3,599 ⟶ 4,031:
print "Could not solve!\n";
}
</syntaxhighlight>
{{out}}
<pre>Here is the maze:
Line 3,649 ⟶ 4,081:
=={{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,727 ⟶ 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,745 ⟶ 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,770 ⟶ 4,337:
Works with SWI-Prolog and XPCE.
<
:- dynamic maze/3.
:- dynamic path/1.
Line 3,918 ⟶ 4,485:
\+cell(L, C1).
</syntaxhighlight>
output : [[File:Prolog-Maze-solved.jpg]]
=={{header|PureBasic}}==
<
Procedure displayMazePath(Array maze(2), List Path.POINT())
Line 4,031 ⟶ 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,053 ⟶ 4,620:
=={{header|Python}}==
<syntaxhighlight lang="python">
# python 3
Line 4,104 ⟶ 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,126 ⟶ 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,148 ⟶ 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,174 ⟶ 4,741:
(displayln "+"))
(newline))
</syntaxhighlight>
Example:
Line 4,219 ⟶ 4,786:
{{works with|Rakudo|2017.02}}
(Includes maze generation code.)
<syntaxhighlight lang="raku"
:N< ╵ >,
:E< ╶ >,
Line 4,348 ⟶ 4,915:
}
display solve gen_maze( 29, 19 );</
{{out}}
<small><pre>┌ ╵ ────┬───────────────┬───────────────┬───────────────────────────────┬───────────┬───────────────┬───────────────┐
Line 4,391 ⟶ 4,958:
=={{header|Red}}==
(imports maze generation code, see http://rosettacode.org/wiki/Maze_generation#Red)
<
do %mazegen.red
Line 4,415 ⟶ 4,982:
visited: []
until [end = expand path/1]
print reverse path</
{{out}}
<pre>Maze width: 15
Line 4,441 ⟶ 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,515 ⟶ 5,082:
maze = Maze.new 20, 10
maze.solve
maze.print</
Example output:
Line 4,544 ⟶ 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,796 ⟶ 5,363:
println!("The maze, solved:");
maze.paint(true);
}</
{{out}}
Line 4,867 ⟶ 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,926 ⟶ 5,783:
m solve
# Print it out
puts [m view]</
Example output:
<pre>
Line 4,946 ⟶ 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,951 ⟶ 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,993 ⟶ 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>
|