Trémaux's Algorithm maze algorithm
Trémaux's algorithm is the oldest guaranteed way out of any maze: mark every passage you walk, and never walk one more than twice.
How it works
Walk and mark each passage behind you. At a junction, take a passage you haven't marked. If you arrive at a junction you've seen before by a new passage, turn round and go back. If every way is marked, take the one marked once. Never take a passage marked twice.
It's depth-first search done on foot: it really walks back along corridors instead of jumping. It always finds the exit, loops or not, and the passages marked exactly once form a path from start to exit.
What to watch for
Watch it run down a corridor, hit a dead end and walk all the way back, its trail overwriting itself on the way.
Properties
- Shortest path
- No
- Finds the exit
- Always
- Explores
- Like DFS, walking every backtrack
- Memory
- Marks on the passages
Race it
Pick it in the race and see who reaches the exit first, or run it in the studio.
FAQ
Who was Trémaux?
Charles Pierre Trémaux, a 19th-century French engineer. His method was described by Édouard Lucas in 1882.
How is it different from the wall follower?
It marks where it's been, so it can't loop forever round an island the way a wall follower can.