Intuition First: A Maze With a Ball of String#
Backtracking is how you'd solve a hedge maze. At each junction you pick a path and walk on, unrolling a ball of string behind you. The instant you hit a dead end, you don't panic or teleport. You follow your string back to the last junction and try a door you haven't opened yet. Explore a choice fully, and if it fails, undo it cleanly and try the next one.
That disciplined loop of choose, explore, un-choose is the entire idea. It's exactly how a program fills in a Sudoku grid, places N queens so none attack each other, or generates every valid combination: try a move, recurse, and rewind the moment it leads nowhere.
The Concept#
Backtracking is a systematic way to explore every possible sequence of decisions while abandoning any path the moment it violates a constraint. The core template is three steps repeated at each level of recursion:
- Choose: pick the next candidate (a column for the queen, a digit for a Sudoku cell, a direction in a maze).
- Explore: recurse deeper, trusting the same function to handle the next level.
- Un-choose: undo the choice completely so shared state is clean for the next candidate.
If you picture the space of all choices as a tree, backtracking is depth-first search on that decision tree, with an early-exit rule: if a partial assignment already breaks a constraint, cut the whole subtree. That pruning is what separates backtracking from plain brute force.
The Pattern in Code#
Every backtracking function follows this skeleton:
Don't skip the undo step. Without it, earlier choices bleed into later branches and produce wrong results. With it, every candidate at each level starts from an identical clean slate.
N-Queens: Classic Backtracking#
Place N queens on an N×N chessboard so that no two threaten each other (no shared row, column, or diagonal).
Strategy: place exactly one queen per row. For row r, try every column c. Before placing, check three sets:
cols: columns already occupied.diag: occupied "top-left to bottom-right" diagonals (identified byr - c).anti: occupied "top-right to bottom-left" anti-diagonals (identified byr + c).
If c is safe, add it to all three sets, recurse to row r + 1, then remove it from all three sets. That's the undo step.
Let's take the example in this visualization: a 4×4 board. It's the smallest interesting case, since N = 2 and N = 3 have no solution at all.
Press play and watch the first attempt fail completely. A queen in row 0, column 0 forces row 1 into column 2 or 3, and from either of those row 2 has no legal column left: every square is taken by a column, a diagonal or an anti-diagonal. The search rewinds all the way back to row 0, restoring the three sets at each level as it goes, and starts again from column 1. That second attempt runs straight through: columns 1, 3, 0, 2. Everything you see between the two attempts is the un-choose step doing its job.
Sudoku Solver#
Fill a 9×9 grid so every row, column, and 3×3 box contains the digits 1 to 9 exactly once.
Strategy: scan cells left-to-right, top-to-bottom. At each empty cell, try digits 1 to 9. Check the row set, column set, and box set. If valid, fill the cell, recurse, and clear the cell when the call returns (undo). If all cells are filled, the puzzle is solved.
The structure is identical to N-Queens: the only difference is that there are more constraint sets and each "choice" is a digit rather than a column. Pruning is aggressive. Most digits fail immediately, keeping the search tree shallow.
The lab below loads one of a small set of solvable 9×9 puzzles; the given clues render in a different colour from the digits the solver writes, so you can always tell the two apart. Press play and watch the cursor sweep left to right, top to bottom, filling in the first digit that survives all three constraint checks. When a cell has no surviving digit, the solver clears it and returns to the previous cell to resume it from where it left off. It's the same rewind you just watched on the chessboard, only here it happens dozens of times and is over in a blink.
Tower of Hanoi: Pure Recursion#
Move N disks from peg A to peg C, using peg B as an auxiliary, never placing a larger disk on top of a smaller one.
Unlike the previous two problems, Tower of Hanoi has no backtracking, because every move is forced. It is an example of pure recursion: the solution falls out of the recursive decomposition with no need to undo anything.
The key insight is that moving N disks reduces to three subproblems:
- Move N−1 disks from A to B (using C).
- Move the largest disk from A to C.
- Move N−1 disks from B to C (using A).
The total number of moves is exactly 2^N − 1. This exponential count is unavoidable; the problem has no smarter solution.
Let's take the example in this visualization: three disks on peg A, so 2³ − 1 = 7 moves exactly. Press play and count them. Notice what is not happening: no move is ever tried and withdrawn, and no state is ever restored. The disks only ever go forward. That is the difference between recursion and backtracking, and this lab is here as the control case for the three that surround it.
Rat in a Maze#
A rat starts at the top-left corner of an N×N grid and must reach the bottom-right corner. Blocked cells are impassable. Find all paths (or one path) using only down and right moves (or all four directions in the full variant).
Strategy: mark the current cell as visited, try each valid direction, recurse. If the end is reached, record the path. On return from each direction, unmark the cell. This is the undo step. Without it, a cell visited on one failed path would look occupied to sibling paths.
This problem cleanly illustrates why the un-choose step matters: shared state (the visited grid) must be restored so that distinct paths are explored independently.
The lab below builds a fresh 6×6 maze each time the page loads, with roughly a third of the cells blocked and always at least one route from the top-left corner to the bottom-right. Press play and watch the rat commit to down first at every junction, because that is the first direction in the offset list. When it runs out of maze the recursion unwinds: the abandoned corridor changes colour behind it and the rat reappears at the junction above, free to try right next. That recolouring is the un-choose step made visible. The cell comes off the current path, and that is what gives the junction above a clean slate for its remaining directions.
Complexity Analysis#
| Problem | Time (worst case) | Pruning effect |
|---|---|---|
| N-Queens | O(N!) | Column/diagonal checks prune large subtrees |
| Sudoku | O(9^81) theoretical | Constraint sets prune most branches instantly |
| Tower of Hanoi | O(2^N) | No choices; every move is forced |
| Rat in a Maze | O(4^(N²)) | Visited marks prune cycles |
Backtracking is exponential in the worst case. Pruning does not change the theoretical upper bound, but it dramatically shrinks the practical search space, making these problems tractable for typical input sizes (N ≤ 15 for N-Queens, standard 9×9 Sudoku, small mazes).
What to Remember#
- Choose / explore / un-choose is the template. Every backtracking problem (permutations, combinations, subsets, constraint satisfaction) uses this exact skeleton.
- Undo is not optional. Failing to un-choose corrupts shared state and produces incorrect results on sibling branches. Make the undo the very next line after the recursive call.
- Prune early. Check constraints before recursing, not after. Every invalid candidate pruned avoids an entire subtree of wasted work.
- Backtracking is DFS on the decision tree. The recursion depth equals the number of choices made so far; the branching factor equals the number of candidates at each level. This mental model tells you the worst-case space (the depth of the recursion stack, O(N) for most problems).
- Tower of Hanoi is the exception. It uses recursion without backtracking, a reminder that not every recursive algorithm needs an undo step.