Maze-Solving Algorithms Explained: Wall Follower, Tremaux and Pledge

A maze-solving algorithm is just a fixed set of steps that finds the way out without any luck or guessing. The same rules a person uses with a pencil are the rules a robot or a computer program follows, only written down precisely. This guide explains the classic maze algorithms in plain language: what each one does, when it works, and when it breaks. If you want the hands-on version first, start with how to solve a maze and come back here for the theory.

The two situations every algorithm has to handle

Before the methods, one idea decides everything: is the maze simply connected or not? A simply connected maze has no loops and no islands. Every wall is joined to the outer boundary, so the walls form one big connected shape. A maze with loops or detached interior walls is multiply connected. Some algorithms only work on the first kind. Others work on any maze. Knowing the difference tells you which tool to reach for.

The wall follower algorithm

The wall follower is the most famous maze routing algorithm, and the simplest to state. Choose a side, left or right, and always keep that side's wall in contact as you move. This is the right-hand rule (or left-hand rule) you may have heard about.

As a step-by-step procedure for a solver standing in the maze, the right-hand rule is:

1. If you can turn right, turn right and step forward.
2. Otherwise, if you can go straight, go straight.
3. Otherwise, if you can turn left, turn left.
4. Otherwise, turn around (you are in a dead end) and step back.

Repeat until you reach the exit. Because a simply connected maze's walls form a single loop that includes the entrance and exit, hugging that loop is guaranteed to reach the way out. The cost is that you walk down and back out of every dead end attached to the wall you are following, so it is not the shortest route, just a route that always works.

Limitation: the wall follower fails if the goal is on an island of wall that your chosen wall never touches. On a maze with loops, it can also send you in an endless circle around an inner ring. For those, you need an algorithm that does not depend on the walls being connected.

Tremaux's algorithm

Tremaux's algorithm is the one to use when you can mark the maze as you go, which makes it ideal for solving on paper. It works on any maze, connected or not, and it always finds a path if one exists. The trick is to record how many times you have used each passage.

The rules, using marks at each passage entrance:

1. Walk forward, drawing a line behind you. When you arrive at a junction you have never visited, pick any unmarked passage and take it.
2. If walking down a passage brings you to a junction you have already visited, or to a dead end, turn around and go back, marking that passage a second time. A passage marked twice is closed; never enter it again.
3. When you reach a junction, prefer a passage with no marks. If there is none, take a passage marked only once (the one you arrived by counts), and mark it as you leave.
4. Never take a passage that already has two marks.

Follow these and you will explore the maze methodically and end up tracing the solution, never wandering in circles. The pencil-and-paper habit of dotting junctions you have fully explored is just an informal version of Tremaux.

The Pledge algorithm

The Pledge algorithm fixes the wall follower's biggest weakness: getting trapped circling an island. It is designed for the case where you cannot see the whole maze, only what is right around you, and the goal is to escape rather than to reach a specific interior point.

It works by counting turns. Pick a fixed direction to favor, say "north." Then:

1. Walk in your chosen direction until you hit a wall.
2. Follow the wall (using, for example, the right-hand rule), and keep a running count of your turns: add one for every right turn, subtract one for every left turn (or the reverse, as long as you are consistent).
3. Leave the wall and resume walking in your chosen direction only when two things are both true: you are facing your original chosen direction again, and your turn counter is back to zero.

The turn counter is what saves you. A simple wall follower can loop forever around an island because it never notices it has made a full circle. By tracking net turns, the Pledge algorithm can tell when it has gone all the way around and break free, so it escapes any maze whose exit is on the outer boundary, even with islands inside.

Dead-end filling

Dead-end filling is less like walking and more like erasing, which is why it is the favorite for solving a printable maze by hand. Instead of finding the path, it removes everything that is not the path.

1. Scan the whole maze and find every dead end (any cell with three walls around it).
2. Fill in each dead-end corridor, working from the closed tip back to the first junction.
3. Filling those corridors turns some old junctions into new dead ends. Find those and fill them too.
4. Repeat until no dead ends are left.

Whatever corridors remain unfilled form the solution. Dead-end filling finds all solution paths between start and finish at once, but it only works when you can see the entire maze, so it suits paper and computer solving rather than someone walking through a hedge maze blind.

Breadth-first and the shortest path

The algorithms above find a path. If you want the shortest path, computers use breadth-first search. Picture flooding the maze with water from the start: the water spreads one cell at a time in all open directions, and the first moment it reaches the exit, the number of steps it took is the shortest possible. Trace that wave back and you have the shortest route. This is how navigation apps and game characters route through grids, and it is why a program can solve a giant maze instantly while a person plods through corridors.

Which algorithm should you use?

• Walking a maze you cannot see all of, exit on the outer wall: wall follower, or the Pledge algorithm if there might be islands.
• Solving on paper and you can mark it: Tremaux's algorithm, or dead-end filling for the cleanest result.
• You need the shortest route, by computer: breadth-first search.

Each of these is just a disciplined version of something a careful solver already does by instinct. Want to feel the difference between them? Try the same method on an easy maze and then a dense expert maze, and watch how the algorithm holds up as the corridors multiply. The hands-on walkthrough lives in how to solve a maze.