Content deleted Content added
Line 42:
** If the path you came in on has only one mark, turn around and return along that path, marking it again. In particular this case should occur whenever you reach a dead end.
** If not, choose arbitrarily one of the remaining paths with the fewest marks (zero if possible, else one), follow that path, and mark it.
The "turn around and return" rule effectively transforms any maze with loops into a simply connected one; whenever we find a path that would close a loop, we treat it as a dead end and return. Without this rule, it is possible to cut off one's access to still-unexplored parts of a maze if, instead of turning back, we arbitrarily follow another path.
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>
| |||