Maze-solving algorithm: Difference between revisions

Revision as of 20:05, 12 December 2016

Revision as of 20:10, 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. The algorithm is as follows:{{dubious}}

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

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

# If you arrive at a new junction, take aan randomarbitrary 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)