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:
The undo step is crucial. 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 — the undo step.
Watch the algorithm place queens row by row, back up when a conflict is detected, and try the next column. Notice how the three sets are restored on every undo.
Sudoku Solver
Fill a 9×9 grid so every row, column, and 3×3 box contains the digits 1–9 exactly once.
Strategy: scan cells left-to-right, top-to-bottom. At each empty cell, try digits 1–9. Check the row set, column set, and box set. If valid, fill the cell, recurse, and — when returning — clear the cell (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.
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 — 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.
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.
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 — 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).
Key Takeaways
- 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.