Maze-solving algorithm: Difference between revisions

Revision as of 20:30, 12 December 2016

Revision as of 20:43, 12 December 2016

Line 30:

== Trémaux's algorithm ==

[[File:Maze tremaux.gif|left|thumb| Trémaux's algorithm. Blue line segments show marks on the paths of the maze; red dots show junctions or dead ends with at least one marked path.]]

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 isworks asaccording follows:{{dubious|date=Decemberto 2016}}the following rules:

#* Mark each path once, when you enterfollow 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, takethat anhas arbitraryno path,marks marking(other than the pathone on the edge by which you arrivedentered), onchoose andan thearbitrary unmarked path, youfollow it, and mark tookit.

* Otherwise:

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

#** If possible go back the waypath you came, markingin thaton pathhas twiceonly (onceone for arrivingmark, turn around and oncereturn along that path, marking forit leaving)again.

#** OtherwiseIf (ifnot, thechoose patharbitrarily youone arrivedof onthe alreadyremaining had a mark) pick a random pathpaths with the fewest number of marks (ie zero if possible, otherwiseelse one);, youfollow will mark thethat path you arrived on with a second mark, and mark the one you leave on as usualit.

When you finally reach the solution, paths marked exactly once will indicate a 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>