Revision as of 01:07, 13 December 2016 edit Grj23 (talk \| contribs) 199 edits →Trémaux's algorithm: Changed diagram to one that follows algorithm more clearly (the markings at the intersection are clearer and there is no continuous path) ← Previous edit		Revision as of 01:44, 13 December 2016 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,647 edits →Trémaux's algorithm: rewrite caption to clarify what the dots and crosses actually mean Next edit →
Line 30: == Trémaux's algorithm == [[File:Tremaux Maze Solving Algorithm.gif\|thumb\| Trémaux's algorithm. ~~Green~~The ~~dot~~large isgreen ~~trying to~~dot ~~get from~~shows the ~~top-left~~current toposition, the ~~bottom-right.~~small ~~Dots~~blue ~~and~~dots ~~crosses~~show ~~are~~single ~~marked~~marks on paths, and the ~~routes~~red ~~following~~crosses ~~the~~show double ~~algorithm~~marks. Once ~~done~~the exit is found, the route is traced through the ~~single~~singly-marked ~~dots~~paths.]] 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:

Maze-solving algorithm: Difference between revisions