Maze Generator
Every maze from this generator is a perfect maze: there are no loops, every cell can be reached, and there is exactly one route between the entrance and the exit. That structure is why the classic solving methods always work here.
Wall following
Put your pencil on the entrance and keep the wall on your right (or left, but be consistent) at every junction. You will trace every corridor on that side of the maze and eventually arrive at the exit. It works because, in a maze with no loops, the walls form one connected surface and following it must eventually visit every opening in the outer wall. It is slow, because you also visit every dead end on the way, but it never fails.
Dead-end filling
Look for any cell with only one open side. Shade it in and treat it as a wall. Repeat. Each fill can expose a new dead end just behind it. When nothing is left to fill, the unshaded cells are exactly the solution. This method works from the whole maze at once rather than from the entrance, which makes it good for large printed mazes and for checking someone else's answer.
Trémaux's algorithm
Mark a corridor each time you pass along it. Never enter a corridor with two marks. At a junction, prefer an unmarked corridor; if none exist, take a corridor with one mark. If you reach a dead end, turn round (that corridor now has two marks). You will reach the exit, and the corridors with exactly one mark form the solution. This is the method to use in a maze you cannot see all of, such as a hedge maze or a text adventure.
What the generator uses
The solution overlay is produced by breadth-first search: starting from the entrance, expand into all neighbouring cells, then all of theirs, and so on until the exit is reached, remembering how each cell was first reached. In a perfect maze there is only one route so the shortest path is the only path, but breadth-first search would also find the shortest one if loops existed.
Human shortcuts
- Scan from the exit backwards; the last few cells often narrow to a single corridor.
- In a backtracker maze, corridors are long; if a passage heads away from the exit for a long stretch it is probably a dead branch.
- In a Prim maze, the solution is short; look for the corridor that keeps branching rather than the ones that end quickly.
- Circular mazes are solved most easily by working out which ring the doorway between rings is on, from the centre outward.