Maze-solving algorithm - Misplaced Pages

This is an old revision of this page, as edited by 82.0.89.208 (talk) at 19:01, 8 January 2010 (→Pledge algorithm). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Revision as of 19:01, 8 January 2010 by 82.0.89.208 (talk) (→Pledge algorithm)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

There are a number of different maze solving algorithms, that is, automated methods for the solving of mazes. A few important maze solving algorithms are explained below. The random mouse, wall follower, pledge, and Tremaux 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 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 .

Random mouse algorithm

This is a trivial method that can be implemented by a very unintelligent robot or perhaps a mouse. It is simply to proceed in a straight line until a junction is reached, and then to make a random decision about the next direction to follow.

Wall follower

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, 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. This strategy works best when implemented immediately upon entering the maze.

Another perspective into why wall following works is topological. If the walls are connected, then they may be deformed into a loop or circle . Then wall following reduces to walking around a circle from start to finish.

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.

Wall-following can be done in 3D or higher dimensional mazes if its higher dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can then be applied. However, unlike in 2D, this requires that the current orientation be known, to determine which direction is the first on the left or right.

Pledge algorithm

Disjoint mazes can still be solved with the wall follower method, if the entrance and exit to the maze are on the outer walls of the maze. If however, the solver starts inside the maze, it might be on a section disjoint from the exit, and wall followers will continually go around their ring. The Pledge algorithm (named after Jon Pledge of Exeter) can solve this problem (see "Turtle Geometry: the computer as a medium for exploring mathematics", Abelson & diSessa, 1980).

The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted. When the solver is facing the original direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction.

Note that the hand is removed from the wall only when both "sum of turns made" and "current heading" are at zero. This allows the algorithm to avoid traps shaped like an upper case letter "G". Assuming the algorithm turns left at the first wall, one gets turned around a full 360 degrees by the walls. An algorithm that only keeps track of "current heading" leads into an infinite loop as it leaves the lower rightmost wall heading left and runs into the curved section on the left hand side again. The Pledge algorithm does not leave the rightmost wall due to the "sum of turns made" not being zero at that point. It follows the wall all the way around, finally leaving it heading left outside and just underneath the letter shape.

This algorithm is Fuked!Dont do it. This algorithm allows a person with a compass to find his way from any point inside to an outer exit of any finite and fair two-dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it.

Tremaux's algorithm

Tremaux's algorithm is an efficient method to find the way out of a maze that requires drawing a line on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages. On arriving at a junction, pick a direction and mark it and the direction you came from. When arriving at a marked junction pick an unmarked passage if possible. If it is not possible to pick an unmarked passage take a marked one, marking it again (you can pick the path you came from). Never pick a twice marked path, where you will never need to take any passage more than twice. If there is no exit, this method will take you back to the start. Tremaux's algorithm effectively implements a depth-first search.

Dead-end filling

Dead-end filling is an algorithm for solving mazes that looks at the entire maze at once. It can be used for solving mazes on paper or with a computer program, but it is not useful to a person inside an unknown maze. The method is to 1) find all of the dead-ends in the maze, and then 2) "fill in" the path from each dead-end until the first junction met. A video of dead-end filling in action can be seen here: .

Dead-end filling cannot accidentally "cut off" the start from the finish since each step of the process preserves the topology of the maze. Furthermore, the process won't stop "too soon" since the end result cannot contain any dead-ends. Thus if dead-end filling is done on a perfect maze (maze with no loops), then only the solution will remain. If it is done on a partially braid maze (maze with some loops), then every possible solution will remain but nothing more.

Shortest path algorithm

When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. This algorithm find the shortest path by implementing a breadth-first search. The algorithm uses a 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

External links

Think Labyrinth: Maze algorithms (details on these and other maze solving algorithms)
MazeBlog: How to Solve Mazes
Maze generation and solving Java applet
Maze generator and solver, in C# - print out mazes in various shapes on paper.

Categories: