Dead-End Filling maze algorithm
Dead-End Filling solves a maze without walking it: it fills in every dead end, and the corridor behind it, until only the way through is left.
How it works
Find every cell with only one open side (other than the start and exit) and fill it in. Filling a cell can turn its neighbour into a new dead end, so keep going until there are none left. What's left unfilled is the route from start to exit.
In a perfect maze that leaves exactly one path. With loops, a few loops can survive the filling, and the shortest way through them is the answer.
What to watch for
Watch the flood start everywhere at once, creeping in from the tips of every dead end, until one clean corridor is all that's dark.
Properties
- Shortest path
- Yes, in a perfect maze
- Explores
- Almost the whole maze
- Needs
- A view of the whole maze (not usable from inside)
- Memory
- One mark per cell
Race it
Pick it in the race and see who reaches the exit first, or run it in the studio.
FAQ
Why does it fill so much of the maze?
Because it's eliminating everything that isn't the answer. In a perfect maze almost every cell is off the solution.
Can a person do this?
Yes, on paper. It's how many people solve printed mazes: shade the dead ends until the path stands out.