Maze solving: Difference between revisions

 

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.

 

=={{header|Ada}}==

The maze is read from the standard input. The size of the maze is hardwired into the program (see the constants X_Size and Y_Size).

 

 

procedure Maze_Solver is

Search(Maze, X, Y) ; -- Will output *all* Solutions.

-- If there is no output, there is no solution.

 

{{out|Example output:}}

+---+---+---+---+---+---+---+---+---+---+-*-+

</pre>

 

=={{header|BBC BASIC}}==

[[Image:mazesolve_bbc.gif|right]]

Maze generation code also included.

MazeHeight% = 9

MazeCell% = 50

ENDIF

NEXT

 

=={{header|C}}==

See [[Maze_generation#C|Maze generation]] for combined gen/solve code.

 

=={{header|C++}}==

 

[[File:maze_solving_cpp.png|300px]]

#include <windows.h>

#include <iostream>

}

//--------------------------------------------------------------------------------------------------

 

=={{header|D}}==

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;

 

if (maze[s.y + (d.y / 2)][s.x + (d.x / 2)] == ' ' &&

maze[s.y + d.y][s.x + d.x] == ' ') {

maze[s.y + d.y][s.x + d.x] = pathSymbol;

if (solveMaze(maze, V2(s.x + d.x, s.y + d.y), end))

maze[end.y][end.x] = 'E';

writefln("%-(%s\n%)", maze);

{{out}}

<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

| . . . . . . S | | |

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>

 

=={{header|EGL}}==

 

// First and last columns/rows are "dead" cells. Makes generating

end

 

{{out|Output example (for 10x10 maze)}}

<pre>

| * * | E | * * |

+---+---+---+---+---+---+---+---+---+---+

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

-module( maze_solving ).

 

{ok, Cells} -> {ok, Cells}

end.

{{out}}

<pre>

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

brin <- BufferedReader.fromISR isrin

lns <- BufferedReader.getlines brin

 

{{out}}

=={{header|Go}}==

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

 

import (

rSolve(ra, ca, -1)

m.c2[ra][ca] = 'S'

{{out|Example output:}}

<pre>

 

<!-- ugh, syntax colorer seems to not understand that single quote (prime) can be part of an identifier -->

 

 

-- given two points, returns the average of them

average :: (Int, Int) -> (Int, Int) -> (Int, Int)

 

-- given a maze and a tuple of position and wall position, returns

-- given a maze and a position, draw a '*' at that position in the maze

draw :: [String] -> (Int, Int) -> [String]

 

-- given a maze, a previous position, and a list of tuples of potential

-- new positions and their wall positions, returns the solved maze, or

-- None if it cannot be solved

tryMoves _ _ [] = Nothing

 

-- given a maze, a new position, and a previous position, returns

-- the solved maze, or None if it cannot be solved

-- (assumes goal is upper-left corner of maze)

let newPositions = [(x, y - 2), (x + 4, y), (x, y + 2), (x - 4, y)]

legalMoves = filter (notBlocked maze) zipped

in tryMoves maze pos legalMoves

-- (starts at lower right corner and goes to upper left corner)

solve :: [String] -> Maybe [String]

 

-- takes unsolved maze on standard input, prints solved maze on standard output

{{out}}

<pre>

+---+---+---+---+---+---+---+---+---+---+---+

 

Replace the main with this:

/mh := \A[1] | 12

/mw := \A[2] | 16

until Event() == &lpress # wait

close(mz.window)

 

And include this after the Generator and Display procedures.

static maze,h,w,rd

 

}

return mz

 

The following Unicon-only solution is a variant of the above. It shares the same

cyclic paths. The shortest solution path is then marked and displayed.

 

 

import Utils # To get 'Args' singleton class

procedure waitForCompletion()

critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)

 

=={{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

maze=:4 :0

assert.0<:n=.<:x*y

'o' cells } a NB. exercise, replace cells with a gerund to draw arrows on the path.

)

Example:<pre>

4 (display~ solve)@maze 20

 

=={{header|Java}}==

import java.util.*;

 

System.out.println (solvedLines[i]);

}

{{out}}

<pre>

</pre>

 

===Graph===

Solving the maze generated in [[Maze_generation#Graph]]:

{{Out}}

[[File:MathematicaMazeGraphSolving.png]]

=={{header|Perl}}==

This example includes maze generation code.

#!perl

use strict;

print "Could not solve!\n";

}

{{out}}

<pre>Here is the maze:

+--+--+--+--+--+--+--+--+--+--+

</pre>

 

 

 

 

 

 

 

{{out}}

 

=={{header|PicoLisp}}==

(let (Path NIL Best NIL Dir " > ")

(recur (This Path Dir)

(=: mark NIL) ) ) )

(disp Maze 0

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

Works with SWI-Prolog and XPCE.

 

:- dynamic maze/3.

:- dynamic path/1.

\+cell(L, C1).

 

output : [[File:Prolog-Maze-solved.jpg]]

 

=={{header|PureBasic}}==

 

Procedure displayMazePath(Array maze(2), List Path.POINT())

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

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.

 

 

=={{header|Python}}==

# python 3

 

cell = predecessor[cell]

print(0)

 

=={{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)

(append-map (next-turn (list p1))

(alternatives p1 (list p1)))))

 

Reading a maze from a file

;; Reads the maze from the textual form

;; read-maze :: File-path -> Maze

1))

(maze N M tbl))))

 

Printing out a maze with a path between two given cells

;; Shows a maze with a path connecting two given cells

(define (show-path m p1 p2)

(displayln "+"))

(newline))

 

Example:

| * * * * * | | * * * * |

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

</pre>

 

=={{header|Ruby}}==

This solution extends the [[Maze generation#Ruby|maze generator script]]. To get a working script, copy &amp; paste both parts into one file.

# Solve via breadth-first algorithm.

# Each queue entry is a path, that is list of coordinates with the

maze = Maze.new 20, 10

maze.solve

 

Example output:

| * * | * * | | |

+---+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

</pre>

 

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

m solve

# Print it out

Example output:

<pre>

| > > > ^ | | >

+---+---+---+---+---+---+---+---+---+---+---+

</pre>

 

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,*]) } // "+---" --> "+-*-"

ver[endy][endx] =munge(ver[endy][endx],"E");

foreach a,b in (hor.zip(ver)) { println(a.concat(),"\n",b.concat()) }

{{out}}

<pre>