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:}}

=={{header|AutoHotkey}}==

Generator and solver combined.

SleepTime := 0

 

}

return

Outputs:<pre>+---+---+---+---+---+---+---+---+---+---+

| ¦¦¦¦¦ | ¦¦¦¦¦ | ¦¦¦¦¦¦¦¦¦¦¦¦¦ |

[[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|Clojure}}==

(:require [clojure.string :as str]))

 

(replace-cells maze (breadth-first-search maze [1 1] [19 19]) :track))

 

 

{{in}}

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

 

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

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

{{out}}

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

| . . . . . . S | | |

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

 

=={{header|EasyLang}}==

 

 

.

.

.

.

posn = pos + offs[dir]

.

.

sleep 1

 

=={{header|EGL}}==

 

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

end

 

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

<pre>

 

=={{header|Emacs Lisp}}==

 

(cl-defstruct maze rows cols data)

(print-maze maze solution)))

 

 

{{out}}

<pre style="height:35ex;overflow:scroll;">+ +---+---+---+---+---+---+---+---+---+

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

 

import Data.Maybe (fromMaybe)

let main_ = unlines . fromMaybe ["can_t solve"] . solve . lines

in interact main_

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

Uses code from maze generation task

{{works with|Java|8}}

import java.awt.event.*;

import java.awt.geom.Path2D;

});

}

 

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

createMaze();

}

HTML to test.

<pre>

{{trans|Python}}

 

+ +---+---+

| 1 2 3 |

 

dist, path = dijkstra(graph)

 

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.io.File

val solvedLines = expandHorizontally(maze)

println(solvedLines.joinToString("\n"))

 

{{out}}

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

=={{header|Phix}}==

Combined generator and solver.

{{out}}

<pre>

| | o - o - o - o | | |

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

</pre>

 

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

{{works with|Rakudo|2017.02}}

(Includes maze generation code.)

:N< ╵ >,

:E< ╶ >,

}

 

{{out}}

<small><pre>┌ ╵ ────┬───────────────┬───────────────┬───────────────────────────────┬───────────┬───────────────┬───────────────┐

│ · · · · · · · · · │ │ │ │ │ │ │ │ │ ╵ │

└───────────────────┴───────┴───┴───────────────┴───────┴───────────┴───────┴───────────────────┴───────┴──────── │ ┘</pre></small>

 

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

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

println!("The maze, solved:");

maze.paint(true);

 

{{out}}

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

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

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>