How to solve any maze: wall following, Trémaux and the shortest path
Some mazes give way to a simple rule you can follow with your eyes closed. Others need a little bookkeeping. A few methods, each over a century old, cover every maze you will meet, and knowing which to use saves a lot of wandering.
Two kinds of maze
Before choosing a method, it helps to know which kind of maze you are in.
- Perfect mazes have exactly one path between any two points. There are no loops and no closed-off areas. Most printed puzzle mazes are perfect.
- Braided mazes have loops: you can walk in a circle and come back to where you started. Hedge mazes in gardens are often like this on purpose, because loops defeat the simplest method. Many puzzle games start from a perfect maze and open a few walls to add some loops.
The wall follower
Put one hand on a wall, say the right, and keep walking without ever taking it off. At every junction you take the rightmost turn; at a dead end you turn around and follow the wall back.
In a perfect maze this always works, from any entrance to any exit on the outer edge. The reason is that the walls of a perfect maze are all connected into one piece, so following one of them eventually traces the whole boundary, and the exit is on that boundary.
It fails when walls are not connected. In a maze with loops, you can start beside a wall that is an island in the middle, an outline with paths all around it, and walk around it forever. It also fails if the goal is in the middle of the maze rather than on the edge. And it is rarely the shortest route: you walk into every dead end on your side.
Trémaux's method: works in every maze
In the 19th century the French engineer Charles Pierre Trémaux described a method that always finds the way out, loops or not. You only need a way to mark passages, like chalk or, on paper, a pencil.
- Mark each passage as you enter it and as you leave it. Each passage can have zero, one or two marks.
- At a junction you have not visited before, take any unmarked passage.
- If you come to a junction you have already visited, and the passage you came along has only one mark, turn around and go back the way you came.
- Otherwise, take a passage with the fewest marks, never one with two.
A passage with two marks is finished: you went in and came back. When you reach the exit, the passages with exactly one mark form a route from the start to the exit. Trémaux's method is essentially what computer scientists now call depth-first search.
Dead-end filling: when you can see the whole maze
On paper you have an advantage over someone inside a hedge maze: you can see everything. Dead-end filling uses this.
- Find every dead end.
- From each one, shade the passage back towards the rest of the maze until you reach a junction.
- Shading can create new dead ends. Keep going until there are none left except the start and the exit.
What remains unshaded is the solution. In a perfect maze it is the only path; in a maze with loops, every unshaded route is a way through. It is slow on a large maze but almost impossible to get wrong, and it is satisfying to watch the answer appear.
Finding the shortest path
When moves count, you want the shortest route, not just any route. The reliable way to find it is a breadth-first search: spread out from the start in all directions at once, one step at a time.
- Write 0 in the starting cell.
- Write 1 in every open cell next to it, then 2 in every unnumbered cell next to a 1, and so on.
- When the exit gets a number, that number is the length of the shortest route.
- To trace the route, walk back from the exit, always stepping to a neighbour with a number one lower.
This is how satnavs and computer games find routes, with extra tricks for speed. For a person, a lighter version works well: look ahead from the exit and the start at the same time, and notice where the two "fronts" meet.
Practical tips for paper and screen mazes
- Start from the exit. Many puzzle makers hide their traps near the start, where you naturally begin. Working backwards often avoids them.
- Look for the long corridors. In generated mazes, the true path often runs along long straight stretches, with dead ends branching off it.
- Count before you commit. When a fork leads to two similar-looking areas, trace each a few steps with your eye before moving.
- Check both ends of a bottleneck. If a single gap connects two halves of the maze, the solution must pass through it, which splits one hard maze into two easier ones.
Try it daily
Mazework publishes one new maze every day, the same for everyone. Each swipe or arrow key glides you along a corridor until the next junction, and your score is the number of moves, so the best route is the one with the fewest turns, not always the fewest steps. The daily mazes have a few loops, more as the week goes on, which is exactly where the wall follower starts to cost moves. Filling dead ends with your eyes first, then tracing what is left, is the way to a low score.