Maze-solving algorithm: Difference between revisions

Revision as of 11:46, 17 March 2011

Revision as of 13:15, 4 April 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 [[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 12:

The wall follower, the best-known rule for traversing mazes, is also known as either the ''left-hand rule'' or the ''right-hand rule''. If the maze is [[Simply connected space|''simply connected'']], that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the player is guaranteed not to get lost and will reach a different exit if there is one; otherwise, he or she will return to the entrance.

Another perspective into why wall following works is topological. If the walls are connected, then they may be deformed into a loop or circle <ref>http://www.youtube.com/watch?v=IIBwiGrUgzc</ref>. Then wall following reduces to walking around a circle from start to finish. To further this idea, notice that by grouping together connected components of the maze walls, the boundaries between these are precisely the solutions, even if there is more than one solution (see figures on the right).

If the maze is not simply connected (i.e. if the start or endpoints are in the center of the structure or the pathways cross over and under each other), this method will not be guaranteed to help the goal to be reached.

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

When you finally reach the solution, paths marked exactly once will indicate a direct way back to the start. If there is no exit, this method will take you back to the start where all paths are marked twice.

In this case each path is walked down exactly twice, once in each direction. The resulting [[Glossary of graph theory#Walks|walk]] is called a bidirectional double-tracing.<ref name="Eulerian Graphs and related Topics">H. Fleischner: ''Eulerian Graphs and related Topics.'' In: ''Annals of Discrete Mathematics'' No. 50 Part 1 Volume 2, 1991, page X20.</ref>

<ref name="Eulerian Graphs and related Topics">H. Fleischner: ''Eulerian Graphs and related Topics.'' In: ''Annals of Discrete Mathematics'' No. 50 Part 1 Volume 2, 1991, page X20.</ref>

== Dead-end filling ==