Recursive Backtracker maze algorithm
The Recursive Backtracker carves a maze by walking to a random unvisited neighbour until it gets stuck, then backing up to the last cell with a way forward.
How it works
It is a depth-first search with random choices. Start in a corner, pick a random neighbouring cell that hasn't been visited, knock down the wall between them and step in. Keep going until every neighbour of the current cell is visited, then pop back along the path you came by (the stack) until you find a cell with an unvisited neighbour, and carry on from there. When the stack is empty, every cell is connected.
Because it always runs as far as it can before turning back, it makes long, winding corridors with relatively few dead ends. That makes the mazes look hard and gives solvers like Depth-First Search plenty of rope to get lost in. It's fast (each cell is entered once) but needs a stack as deep as the longest path.
What to watch for
Watch the glowing head snake through the grid in one long run, the colour shifting as the path gets deeper, then jump back and branch off when it hits a dead end.
Properties
- Texture
- Long, winding corridors
- Dead ends
- Few
- Uniform
- No (biased to long paths)
- Speed
- Fast, one visit per cell
- Memory
- A stack up to the whole maze
Try it
Open the studio to carve your own Recursive Backtracker maze at any size, solve it with up to four algorithms, and save the video. Or print one.
FAQ
Is the recursive backtracker the same as DFS?
Yes. It is randomized depth-first search used to build a maze instead of to search one.
Why do backtracker mazes look so twisty?
It only turns back when it is completely stuck, so it lays down very long corridors before branching.
Does it make a perfect maze?
Yes. Every cell is reached exactly once, so there is exactly one path between any two cells. This site can then knock out a few extra walls (Loops) to add shortcuts.