Maze-solving algorithm: Difference between revisions

Revision as of 08:59, 12 September 2011

Revision as of 18:37, 16 September 2011

Line 1:

There are a number of different '''maze solving [[algorithm]]s''', that is, automated methods for the solving of [[maze]]s. A few important maze solving algorithms are explained below. The random mouse, wall follower, Pledge, and Trémaux [[algorithms]] are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the [[Cul-de-sac|dead-end]] filling and shortest path algorithms are designed to be used by a person or computer program that can see the whole maze at once.

Mazes containing no loops are known as "standard", or "perfect" mazes, and are equivalent to a [[Tree (graph theory)| ''tree'']] in graph theory. Thus many maze solving algorithms are closely related to [[graph theory]]. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree.<ref>http://www.youtube.com/watch?v=k1tSK5V1pds</ref>.

== Random mouse algorithm ==

Line 30:

== Trémaux's algorithm ==

Trémaux's algorithm, invented by [[ Charles Pierre Trémaux]], is an efficient method to find the way out of a maze that requires drawing lines on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages.<ref name="Récréations Mathématiques">Edouard Lucas: ''Récréations Mathématiques'' Volume I, 1882.</ref>

A path is either unvisited, marked once or marked twice. Every time a direction is chosen it is marked by drawing a line on the floor (from junction to junction). In the beginning a random direction is chosen (if there is more than one).

On arriving at a junction that has not been visited before (no other marks), pick a random direction (and mark the path). When arriving at a marked junction and if your current path is marked only once then turn around and walk back (and mark the path a second time). If this is not the case, pick the direction with the fewest marks (and mark it, as always).

Line 44:

[[File:MAZE 40x20 DFS no deadends.png|thumb|A maze with many solutions and no dead-ends, where it may be useful to find the shortest path]]

When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. This algorithm finds the shortest path by implementing a [[breadth-first search]]. The algorithm uses a [[queue (data structure)|queue]] to visit cells in increasing distance order from the start until the finish is reached. Each visited cell needs to keep track of its distance from the start or which adjacent cell nearer to the start caused it to be added to the queue. When the finish ___location is found, follow the path of cells backwards to the start, which is the shortest path.

== References ==

{{reflist}}

==See also==

* [[Mazes]]

* [[Maze generation algorithm]]

== References ==

{{reflist}}

==External links==