TAOCP Vol 4B: Combinatorial Algorithms, Part 2 · Week 120
TAOCP 7.2.2.1 Dancing Links (part 2): reading guide
Part 2 covers extending exact cover with secondary items and colors, which allows items to be covered at most once or shared when they agree, enabling things like word puzzles and more flexible constraints.
Time About 9 hours this week
Why it matters
These extensions make dancing links a general-purpose constraint solver rather than a sudoku trick.
Before you start
- 7.2.2.1 part 1
How to approach it
Add secondary items and colors to your solver. Model a small crossword-filling or word-square problem with it.
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
- Mixing up primary and secondary items in your model.