Maze-solving algorithm: Difference between revisions

Revision as of 07:09, 26 July 2010

Revision as of 10:26, 26 August 2010

Line 31:

Tremaux's algorithm 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.

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>