Backtracking
The problem
Some problems require exploring every possible combination of choices to find one (or all) that satisfy a constraint — trying every combination naively wastes enormous effort continuing down paths that were already doomed a few choices earlier, instead of abandoning them the moment they're provably invalid.
Why now
Recursion already gave the tool for exploring a problem via smaller versions of itself; backtracking is recursion with one added discipline — check a partial solution's validity at every step, and immediately abandon (backtrack from) any path that can't possibly lead to a valid answer, rather than completing it and checking at the end.
Mental model
Backtracking is a depth-first search over the space of possible choices: make a choice, recurse, and if a later step reveals the choice was wrong, undo it (backtrack) and try the next option — pruning entire branches of the choice-tree the instant they're known to fail, which is what separates backtracking from a brute-force enumeration of every possibility.
Requires
- RecursionProgramming Fundamentals
Backtracking's explore-then-undo pattern is built directly on recursion's call stack — 'backtrack' literally means returning from a recursive call and trying the next option at that level, which requires recursion's mechanics already being second nature.
- Control FlowProgramming Fundamentals
Backtracking depends on early termination and careful branching (checking constraints at every step to prune invalid paths early) — the exact branch discipline control-flow already covers, applied with more rigor.
Used in
- The N-Queens problem and constraint-satisfaction puzzles (Sudoku solvers)
- Generating all permutations, combinations, or subsets of a set
- Maze and pathfinding problems requiring all valid paths, not just one
- Compiler and parser backtracking in ambiguous grammar resolution
Projects
- Implement a Sudoku solver using backtracking, ensuring it prunes invalid placements immediately rather than filling the whole board before checking validity
- Generate all valid permutations of a string using backtracking, tracing by hand which branches get pruned early
Examples
- Placing a queen in an invalid column in N-Queens is detected and abandoned immediately, without ever trying to place the remaining queens on that doomed board
- Generating all permutations of 'abc' explores 6 valid full paths but prunes far more partial paths than it would if it exhaustively built and then validated every arrangement
Resources
- Backtracking — GeeksforGeeksarticle
Mastery checklist
- I can implement a backtracking solution that prunes invalid branches early rather than checking only complete solutions
- I can solve N-Queens or a similar constraint-satisfaction problem using backtracking
- I can explain backtracking as depth-first search with pruning over a choice tree
- I can identify when a problem's brute-force enumeration can be meaningfully pruned with backtracking