Maze solving algorithms: wall follower, Trémaux, and A*

Every maze solving algorithm belongs to one of two families. The first is for a traveler inside the maze with no map: random mouse, wall follower, Pledge, and Trémaux's algorithm. The second is for a solver who can see the whole maze at once: dead-end filling, breadth-first search, depth-first search, Dijkstra, and A*. Pick the family first and the right algorithm mostly picks itself.

That distinction is the whole post, really. Everything below is detail: how each algorithm works, which ones guarantee a solution, which ones guarantee the shortest solution, and which one actually runs in production for the answer keys on this site.

One scope note before we start. If you are solving a maze by hand and want practical tricks rather than code, start with how to solve a maze; this post is the technical companion to it. And if you came here for how mazes are built rather than solved, that lives in behind the scenes: deterministic maze generation.

the two families: travelers and cartographers

Imagine two people handed the same maze.

The first is standing at the entrance. Hedges over their head, no phone, no drone. They can only see the corridor they are in, and anything they learn they must either remember or scratch into the dirt. Wikipedia calls these "algorithms for use inside the maze," and they are the right mental model for robots, micromouse competitions, and anyone physically lost in a hedge maze.

The second person has the maze printed on a sheet of paper. They see every wall, every junction, every dead end at once. That overhead view unlocks a completely different set of tools, because you can now plan instead of explore.

The families do not compete; they answer different questions. A traveler asks "how do I get out of here?" A cartographer asks "what is the best route?" Confusing the two is the most common mistake in forum threads about the "best" maze algorithm.

algorithms for inside the maze

random mouse

Walk straight until you hit a junction, then pick a direction at random. That is the entire algorithm. It needs no memory at all, it will eventually find the exit in any maze, and "eventually" is doing heroic work in that sentence. On anything bigger than a toy maze it can revisit the same corridor hundreds of times. It exists mostly as a baseline to make every other algorithm look good.

wall follower (the hand-on-wall rule)

Put one hand on a wall at the entrance and never let go. In pseudocode, the right-hand version looks like this:

put your right hand on the wall at the entrance
while not at the exit:
  if you can turn right, turn right and step forward
  else if you can go straight, step forward
  else if you can turn left, turn left and step forward
  else turn around            # dead end

Wall following is guaranteed to work if the maze is simply connected, meaning all its walls connect to the outer boundary. Our maze generator produces exactly this kind of maze (a "perfect" maze, one route between any two points), so on any maze printed from this site the trick genuinely works.

It fails in two situations worth knowing. If the maze has detached wall sections, loops, or an island goal, your hand can trace a loop of wall forever without touching the piece of wall that leads out. And if you start in the middle of an unknown maze rather than at the entrance, you may be following a wall section that never connects to the exit at all. It is also slow: on a perfect maze the right-hand rule is essentially a depth-first traversal that visits every limb on your side of the solution path. When my husband insisted on it at Hampton Court it did get us to the center — by which point our six-year-old had loudly rated the whole experience "boring," which is its own kind of review.

the pledge algorithm

The Pledge algorithm, named after Jon Pledge of Exeter who worked it out as a schoolboy, fixes the detached-wall problem for one specific goal: escaping to the outside.

Pick a compass direction and walk that way. When you hit a wall, put a hand on it and follow it while counting your turns: clockwise positive, counterclockwise negative. When you are facing your chosen direction again and your turn counter reads exactly zero, let go of the wall and resume walking straight. The counter is the clever part. A trap shaped like a letter G will spin a naive follower forever, but a full loop leaves the counter at 360, not zero, so Pledge keeps its hand on the wall and slides out from underneath the trap. It escapes any finite 2-D maze from any starting point. What it cannot do is find a goal inside the maze; it is an exit algorithm, not a search algorithm.

trémaux's algorithm

Trémaux's algorithm is the one I would teach a person who might actually get lost somewhere. Invented by Charles Pierre Trémaux, a 19th-century French telegraph engineer, it needs only something to mark the floor with, and it is guaranteed to work in any maze with well-defined passages, loops and all.

The rules operate on passage entrances, each of which is unvisited, marked once, or marked twice:

1. At a new junction, pick any unmarked entrance.
2. If you arrive at a junction you have seen before (its other entrances carry marks), turn around and go back the way you came, unless that entrance already has two marks.
3. Never enter a passage with two marks. Mark every entrance you pass through, in or out.

When you find the exit, the entrances marked exactly once trace a route back to the start. If there is no exit, you end up back where you began with everything double-marked, which is itself an answer. A century after its invention, computer science reinvented Trémaux's method and called it depth-first search. It is DFS on foot.

algorithms for the overhead view

dead-end filling

The most satisfying algorithm on this list, and the one I recommend showing kids. Find every dead end in the maze, then fill each one in, corridor by corridor, until you reach a junction. Repeat, because filling one dead end often turns the corridor behind it into a new dead end. When nothing more can be filled, what survives is the solution. On a perfect maze exactly one path remains; on a maze with loops, every possible solution remains.

It cannot accidentally seal off the route, because filling a dead end never changes the maze's connectivity. Its one requirement is the overhead view: you cannot fill dead ends you cannot see, so it is useless to a traveler inside the hedges.

breadth-first search vs depth-first search

Model the maze as a graph, with cells as nodes and open passages as edges, and the two classic traversals both solve it. The difference is the order they explore.

DFS commits: it plunges down one corridor as far as it can, backtracks, and tries the next. It finds a path quickly and uses little bookkeeping, but the path can be absurd. BFS is patient: it explores in rings, all cells one step from the start, then two steps, then three, like a flood spreading. The first time the flood touches the exit, the path it took is provably the shortest.

Both have been shipped here. The first solver behind this site's answer keys was DFS, because it is five lines shorter and the engineer who wrote it was in a hurry. It worked, technically. Then a 25×25 maze came back with an answer key that wandered through three-quarters of the grid before exiting: a legal route, but embarrassing printed in red on a worksheet. The solver has been BFS ever since, because an answer key should show the shortest route, and BFS guarantees it on an unweighted grid. Here is the core of it in TypeScript:

type Cell = { row: number; col: number };

// canMove(a, b): true when no wall separates two adjacent cells
function solveMaze(
  rows: number,
  cols: number,
  start: Cell,
  goal: Cell,
  canMove: (a: Cell, b: Cell) => boolean
): Cell[] | null {
  const key = (c: Cell) => c.row * cols + c.col;
  const cameFrom = new Map<number, Cell | null>([[key(start), null]]);
  const queue: Cell[] = [start];
  let head = 0;

  while (head < queue.length) {
    const cur = queue[head++];
    if (cur.row === goal.row && cur.col === goal.col) {
      const path: Cell[] = [];
      for (let c: Cell | null = cur; c; c = cameFrom.get(key(c)) ?? null) {
        path.push(c);
      }
      return path.reverse(); // start to goal, guaranteed shortest
    }
    for (const [dr, dc] of [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ]) {
      const next = { row: cur.row + dr, col: cur.col + dc };
      if (next.row < 0 || next.row >= rows) continue;
      if (next.col < 0 || next.col >= cols) continue;
      if (cameFrom.has(key(next)) || !canMove(cur, next)) continue;
      cameFrom.set(key(next), cur);
      queue.push(next);
    }
  }
  return null; // exit unreachable
}

Two production notes from maintaining this. First, the head index instead of queue.shift() matters: shift() is linear time in JavaScript, and on large grids that quietly turns BFS quadratic. Second, the neighbor loop above is the easy, rectangular case. Adapting it for our hex mazes was the fiddliest afternoon of the project, because hex cells have six neighbors and the offsets differ for odd and even rows; if your hex solver ever "tunnels" diagonally through a wall, your neighbor table is wrong, and yes, that is experience talking.

The same BFS output also feeds our difficulty grading. Solution length is one of the signals behind the maze difficulty labels (how maze difficulty works explains the grading), and in the deterministic 1,200-maze sample we ran for famous mazes around the world, the hardest 10% of mazes had at least 229 solution steps. You only get numbers like that cheaply when the solver is fast enough to run over the whole corpus.

This Computerphile video is a good visual companion; it walks through turning a maze image into a graph and solving it with exactly these traversals:

dijkstra's algorithm

BFS assumes every step costs the same. The moment steps have different costs — mud in one corridor, a toll in another, terrain in a game map — you want Dijkstra's algorithm, published by Edsger Dijkstra in 1959. It works like BFS but always expands the cheapest known frontier node next, using a priority queue instead of a plain queue. For a paper maze it is overkill: with all edge weights equal, Dijkstra is BFS with extra bookkeeping. Reach for it when the maze is really a weighted graph wearing a maze costume.

a* search

A* is Dijkstra plus a sense of direction. Published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford Research Institute, where it was developed to route Shakey the robot, it scores each frontier cell by cost-so-far *plus* an estimate of the remaining distance. On a grid maze the standard estimate is the Manhattan distance: rows away plus columns away, ignoring walls.

The effect is that the search leans toward the goal instead of flooding evenly in all directions, often exploring a fraction of the cells BFS would touch. As long as the estimate never overestimates the true remaining distance (Manhattan distance on a grid never does), A* still guarantees the shortest path. That combination of speed and a guarantee is why A* is the default in game pathfinding and robotics. For a single small maze the difference is academic; for a thousand-cell grid solved sixty times a second, it is the whole game.

which maze solving algorithm should you use?

cheat sheet: guarantees and costs

where these algorithms show up in the real world

Micromouse competitions are the purest arena: palm-sized robots race through a 16×16 wall maze they have never seen, and the dominant strategy is a flood-fill variant of BFS, recomputing cell distances as new walls are discovered. The contests have run since the late 1970s and the top runs are startling to watch.

Game pathfinding is A* territory, from strategy-game unit movement to NPC navigation. Robot vacuums solve a live version of the traveler problem, mapping as they bump. And printed-circuit-board autorouting is maze solving in disguise; the classic Lee algorithm that routes traces between pins is breadth-first search wearing a lab coat.

The solver used to sit over every maze this site generates, drawing the red line on the answer key and reporting the numbers that decide whether a maze gets labeled easy or expert. It is roughly forty lines of TypeScript, and the fanciest thing in it is a queue. There is a lesson in that. The exotic algorithms are wonderful, but on an unweighted grid, patient old BFS is usually the correct amount of clever.

faq

What is the trick to solving a maze?

For a printed maze with entrance and exit on the border, the hand-on-wall rule works: pick a wall at the entrance and follow it without letting go. It is guaranteed on any fully connected ("perfect") maze, including everything from our maze generator. For more human-friendly techniques, see how to solve a maze.

What is the best algorithm for solving mazes?

There is no single best, only best for a situation. Inside an unknown maze: Trémaux's algorithm (guaranteed anywhere) or wall follower (simpler, needs connected walls). With the full maze visible and unweighted: BFS for a guaranteed shortest path. With weighted terrain or large maps: A*.

What is the fastest maze solving algorithm?

On a known, unweighted grid, BFS and A* both find the shortest path; A* is usually faster in wall-clock terms because its heuristic steers it toward the goal and it explores fewer cells. For a traveler inside the maze, nothing beats Trémaux's guarantee, though it walks some passages twice.

What is Dijkstra's algorithm for a maze?

Dijkstra's algorithm (1959) finds the cheapest route on a graph where edges have costs, by always expanding the cheapest-known frontier first. In a plain maze where every step costs the same, it behaves identically to BFS, so it only earns its keep when corridors have different costs.

Can every maze be solved by keeping your hand on the wall?

No. Wall following fails when the goal is on an "island" of wall not connected to the outer boundary, or when the maze contains passage loops around your starting point. Trémaux's algorithm handles those cases; the Pledge algorithm handles escaping them.

next step

The fastest way to make these algorithms concrete is to run them yourself on paper.

• Print a few printable mazes and race dead-end filling against the right-hand rule on the same maze. The difference is instructive.
• Generate a fresh one with the maze generator, then check your route against the BFS-drawn answer key.
• Try a hex maze if you want to feel the neighbor problem that complicates the code above.
• Curious how the mazes get built in the first place? That is deterministic maze generation, the other half of this post.

Sources and further reading:

• Maze-solving algorithm (Wikipedia)
• A* search algorithm (Wikipedia)
• Dijkstra's algorithm (Wikipedia)
• A* Search: What's in a Name? (Communications of the ACM)
• Shakey: From Conception to History (Stanford AI Lab)
• Floodfill, Micromouse (IEEE at UC Irvine)
• Think Labyrinth: maze algorithms (Walter Pullen)
• Maze Solving (Computerphile, YouTube)