Maze-solving algorithm: Difference between revisions

Revision as of 19:46, 6 December 2018

Revision as of 04:32, 27 January 2019

Line 33:

== Trémaux's algorithm ==

[[File:Tremaux Maze Solving Algorithm.gif|thumb| Trémaux's algorithm. The large green dot shows the current position, the small blue dots show single marks on paths, and the red crosses show double marks. Once the exit is found, the route is traced through the singly-marked 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> but it is not guaranteed to find the shortest route.

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.