TAOCP Vol 4B: Combinatorial Algorithms, Part 2 · Week 119
TAOCP 7.2.2.1 Dancing Links (part 1): reading guide
Part 1 covers the basic idea: a node removed from a doubly linked list can be put back exactly by remembering its own links, and this makes backtracking over exact cover problems (Algorithm X) very efficient.
Time About 9 hours this week
Why it matters
Dancing links is one of Knuth's most famous techniques. Exact cover models sudoku, polyomino tiling and many scheduling problems.
Before you start
- 2.2.5 Doubly Linked Lists
- 7.2.2 Backtrack Programming
How to approach it
Implement Algorithm X with dancing links in C. Test it on a small exact cover instance, then build a sudoku solver on top. Watch Knuth's Christmas lectures on dancing links if you get stuck.
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
- Restoring links in the wrong order on backtrack. It must be the exact reverse of removal.