Content deleted Content added
→Trémaux's algorithm: Fix description |
→Trémaux's algorithm: clarify marks on paths vs marks on path-junction incidences |
||
Line 33:
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 works according to the following rules:
* Mark each path once, when you follow it. The marks need to be visible at both ends of the path. Therefore, if they are being made as physical marks, rather than stored as part of a computer algorithm, the same mark should be made at both ends of the path.
* Never enter a path which has two marks on it.
* If you arrive at a junction that has no marks (other than the one on the edge by which you entered), choose an arbitrary unmarked path, follow it, and mark it.
| |||