Algorithms
Backtracking: Search with Backtracking
Цели урока
- Understand the Backtracking paradigm
- Master the solution template
- Solve classic problems
- Apply pruning for optimization
Предварительные знания
- DFS
Sudoku, chess puzzles, exam scheduling - all these problems are solved with one pattern: try an option, if it doesn't work - backtrack and try another.
- Puzzles (Sudoku, crosswords)
- Compilers (parsing with backtracking)
- AI games (minimax)
- Scheduling
Lehmer names backtracking, Golomb and Baumert make it systematic
The technique of trying a partial solution and undoing the last step when it fails is old. The eight queens puzzle was posed in 1848 and solved by trial and error long before computers. The word backtracking was coined by the mathematician D. H. Lehmer in the 1950s. The first careful general treatment came in 1965, when Solomon Golomb and Leonard Baumert published Backtrack Programming, describing it as a unified method for searching a tree of partial candidates and pruning branches that cannot lead to a solution. The key idea they made precise is pruning: as soon as a partial assignment violates a constraint, the whole subtree below it is abandoned, which can cut an exponential search space down to something tractable in practice.
Idea: try → backtrack
**Backtracking** is a systematic enumeration of all options with 'backtracking' at dead ends.
**When to use Backtracking:**
- Need to find ALL solutions (or at least one)
- Solution is built step by step (choice by choice)
- Can prune 'bad' branches early (pruning)
**Backtracking = DFS on a decision tree.** Each node is a partial solution, leaves are complete solutions or dead ends.
Backtracking differs from brute force in that it:
Backtracking Template
**Example: all permutations of [1, 2, 3]**
**Don't forget UNDO!** Without backtracking, `state` will contain all choices, not just the current branch.
Why is `state.pop()` needed at the end?
Classic Problems
**1. N-Queens:**
**2. Sudoku solver:**
**3. Subsets (all subsets):**
N-Queens for n=8 has 92 solutions. Without pruning you'd check:
Optimizations: Pruning
**Pruning** is the key to backtracking efficiency.
| Problem | Without pruning | With pruning |
|---|---|---|
| N-Queens (n=8) | 16 777 216 | ~15 000 |
| Sudoku (medium) | 9^81 | ~1000 |
| TSP (n=10) | 10! = 3 628 800 | ~10 000 |
**Good pruning** can turn an exponential algorithm into a practically polynomial one!
Branch and Bound = Backtracking + ?
Backtracking
- DFS on a decision tree
- Template: choice → recurse → undo
- Pruning is critical for performance
- Branch & Bound = Backtracking + optimality
- Complexity: exponential, but pruning helps
Related Topics
Backtracking is the foundation of many algorithms.
- DFS — Backtracking = DFS on a decision tree
- Dynamic Programming — When subproblems overlap
Связанные уроки
- alg-13-dfs — Backtracking is DFS over a state-space tree
- alg-32-branch-bound — Adding bounds turns backtracking into branch and bound
- alg-21-dp — Both explore subproblems; DP caches, backtracking discards
- crypto-11-classical-cryptanalysis — Breaking ciphers tries keys and backtracks on failure
- comp-01-intro