Week 121 of 125
TAOCP 7.2.2.1 Dancing Links (part 3)
Sign up or sign in to tick these off and give this week a due date.
-
Part 3 covers multiplicities (items covered a range of times), further refinements, and a large set of applications like polyomino and pentomino packing and other puzzles.
Time About 9 hours this week
Why it matters
This is where you see how far one data structure trick can go, and how modeling a problem well matters more than raw speed.
Before you start
- 7.2.2.1 part 2
How to approach it
Pick one application (pentominoes on a 6x10 board is classic) and solve it with your solver. Count solutions and compare with the known number.
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
- Not breaking symmetry, which multiplies run time and solution counts.