Maze-solving algorithm: Difference between revisions

Revision as of 04:45, 6 December 2010

Revision as of 22:05, 29 January 2011

Line 30:

== Trémaux's algorithm ==

Trémaux's algorithm, invented by M.[[ 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).