TAOCP Vol 4B: Combinatorial Algorithms, Part 2 · Week 117
TAOCP 7.2.2 Backtrack Programming (part 1): reading guide
Part 1 covers the core backtracking framework: building solutions one choice at a time and undoing choices on failure, illustrated by the n-queens problem and other classic puzzles, with data structures that make undo cheap.
Time About 8 hours this week
Why it matters
Backtracking solves constraint problems from sudoku to scheduling to regex matching. It is also a constant source of LeetCode problems.
Before you start
- 7.2.1 Generating Basic Combinatorial Patterns
How to approach it
Implement n-queens with bitmasks and count solutions up to n = 14 or so. Then apply the same framework to a word puzzle or Langford pairs.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Forgetting to undo state on the way back.
- Choosing a bad order of variables; always try the most constrained choice first.