How to Solve Any Maze: Three Algorithms That Actually Work

Three Methods, Three Centuries of Puzzle-Solving

Most maze-solving advice boils down to "try stuff and backtrack." That is technically correct but practically useless for a 41×41 grid with over 800 cells. What you actually need are algorithms — repeatable procedures that guarantee a solution regardless of maze size or topology. Here are three, ordered from simplest to most powerful, each with the history and math that makes them tick.

Method 1: The Wall Follower (Right-Hand Rule)

Place your right hand on the wall at the entrance. Walk forward, never breaking contact. At every junction, let the wall guide your turns. Eventually you reach the exit.

Why It Works — and When It Doesn't

The right-hand rule exploits a topological property of simply connected mazes — mazes where every wall segment connects to the outer boundary. In graph theory terms, the maze contains no cycles. Your hand traces the boundary of a single connected component, and since the entrance and exit both sit on that boundary, you must encounter both.

The moment a maze has an island — a wall cluster detached from the perimeter — the guarantee breaks. Your hand locks onto the island's perimeter and you loop forever, never reaching the exit. Hedge mazes like Hampton Court (built 1690) deliberately include islands to defeat wall-followers, which is why tourists still get lost there after 300+ years.

Complexity

For an n-cell simply connected maze, wall following visits at most 2n cells (each cell entered and potentially exited), giving O(n) time. Space is O(1) — you need no memory beyond your current position and which hand is on the wall.

Try It Yourself

Open a small maze in our play mode and mentally commit to only right turns. You will feel the algorithm click on a 15×15 grid. Then try a maze with loops and watch it fail — that is when you need Trémaux.

Method 2: Trémaux's Algorithm

In 1882, Charles Pierre Trémaux — a French telegraph engineer, not a mathematician — published an algorithm that solves any finite maze, including those with loops and islands. He was working on routing problems for underground telegraph cables in Paris, where tunnels formed complex networks with cycles. His insight was that you can navigate any network if you simply mark your path.

The Exact Rules

1. Enter an unvisited passage: mark it once (one line on the left wall).
2. Hit a dead end: turn around. The passage now has two marks.
3. Arrive at a junction you have never seen: pick any unmarked passage and enter it (mark it once).
4. Arrive at a junction you have visited before (you came from a passage with one mark):
   • If there is an unmarked passage, take it.
   • If all passages have at least one mark, go back the way you came (adding a second mark to that passage).
5. Never enter a passage with two marks.

These five rules guarantee that you explore every reachable passage at most twice and never get trapped in a loop. The algorithm is essentially a depth-first search executed by a person walking through physical space.

Complexity

Each edge (passage) is traversed at most twice. For a maze with E passages and V junctions, the time complexity is O(V + E). Space is O(E) — proportional to the marks you leave. On a standard grid maze where E ≈ 2n, this simplifies to O(n).

Why It Matters

Trémaux's algorithm predates the formal concept of depth-first search by nearly a century (DFS was formalized by Hopcroft and Tarjan in 1972). It is one of the earliest examples of a graph traversal algorithm, invented decades before "algorithm" entered common vocabulary.

Method 3: Dead-End Filling

This method requires something the other two don't: a bird's-eye view of the entire maze. That makes it useless in a physical hedge maze but perfect for paper puzzles or screenshots.

How It Works

1. Scan the maze for dead ends — cells with only one opening.
2. Fill (shade in) each dead-end cell, effectively turning it back into a wall.
3. Repeat. Filling dead ends exposes new dead ends at the next junction back.
4. Continue until no dead ends remain. The unfilled cells form the solution path (or paths, if the maze has multiple solutions).

Why It Excels on Paper

On a printed maze worksheet, you can spot dead ends at a glance and shade them with a pencil in seconds. A 21×21 maze typically has 80–120 dead ends; filling them all takes under two minutes and leaves a clean, unambiguous solution path. No backtracking, no confusion.

Contrast this with wall following on paper, where you must carefully trace a line through the corridors and pray you do not accidentally skip a wall. Dead-end filling is faster, cleaner, and more satisfying.

Complexity

A naive implementation scans the entire maze on each pass: O(n) per pass with up to O(n) passes, giving O(n²) worst case. But with a queue seeded with initial dead ends (each newly exposed dead end is enqueued immediately), the algorithm runs in O(n) time — each cell is processed at most once.

Choosing the Right Method

The decision is straightforward:

• Walking through a physical maze (corn maze, hedge maze)? Use wall following if you suspect no islands. Use Trémaux if you want a guarantee — bring chalk to mark passages.
• Solving on paper or screen with full visibility? Dead-end filling is fastest. Shade dead ends, read the answer.
• Programming a solver? Dead-end filling with a queue. It is trivial to implement: roughly 20 lines of code in any language.

Go Practice

Theory without practice is just trivia. Play a maze and consciously apply one method. Then print a batch and try dead-end filling with a pencil. You will internalize the algorithms faster than any textbook can teach them.