Maze solution #3 Tremaux's Algorithm - Hsanokklis/2023-2024-Tech-journal GitHub Wiki
Charles Pierre Trémaux invented an algorithm for solving mazes. The algorithm is as follows:
-
As you walk down the maze, draw a line on the path.
-
At a dead end, turn around and walk back the way you came.
-
At a junction you've not seen before, take any new path.
-
At junction you have been to before:
-
If you are on a new path, turn back the way you came.
-
If you are on a path you've marked before, take a new path if you can.
-
Never go down a path already marked with two lines.
-
When your path reaches a junction, you choose an exit.
Tremaux completely explores all those squares that can be reached down that exit without crossing your path, then returns to the junction through that exit. On returning to the junction Tremaux chooses another new exit to explore if there is one. When Tremaux has finished exploring all the exits from a junction it leaves the junction through the exit from which it arrived. Since Tremaux does this at the very start node, it will solve any maze Tremaux's algorithm satisfies correctness because it works on every maze. It is also reasonably fast (especially compared to the random algorithm). The one limitation is that it does require you to record a mark at every branch. Tremaux's algorithm was generalized later on to an algorithm called "depth first search" that has been used to solve a wide range of problems.
Jamis Buck has written a really entertaining explanation of Tremaux's Algorithm. It is highly entertaining and will help you master algorithms!
https://blog.jamisbuck.org/2014/05/12/tremauxs-algorithm.html
https://blog.jamisbuck.org/2014/04/22/a-new-adventure.html#start