Maze-solving algorithm: Difference between revisions

Revision as of 00:55, 7 December 2016

Revision as of 19:54, 12 December 2016

Line 32:

[[File:Maze tremaux.gif|left|thumb| Trémaux's algorithm]]

Trémaux's algorithm, invented by [[Charles Pierre Trémaux]],<ref>Public conference, December 2, 2010 – by professor [[Jean Pelletier-Thibert]] in Academie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – {{ISSN|0980-6032}}) <br/>Charles Tremaux (° 1859 – † 1882) Ecole Polytechnique of Paris (X:1876), French engineer of the telegraph</ref> 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">Édouard Lucas: ''Récréations Mathématiques'' Volume I, 1882.</ref>

A path from a junction is either unvisited, marked once or marked twice. EveryThe time a directionalgorithm is chosenas 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).follows:

# Mark each path when you enter it from a junction and when you arrive at a junction.

On arriving at a junction that has not been visited before (no other marks), pick a random direction that is not marked (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).

# Never enter a path which has two marks on it.

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.

# If you arrive at a new junction, take a random path, marking the path you arrived on and the path you took.

# If you arrive at a junction that has already been marked:

#* If possible go back the way you came, marking that path twice (once for arriving, and once for leaving)

#* Otherwise (if the path you arrived on already had a mark) pick a random path with the fewest number of marks (ie zero if possible otherwise one); you will mark the path you arrived on with a second mark and mark the one you leave on as usual.

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>