# TAOCP 7.2.2.1 Dancing Links (part 3)

> Study guide to TAOCP 7.2.2.1 Dancing Links (part 3). Part 3 covers the rest of pages 79 to 97 of 7.2.2.1. It adds color controls: secondary items may be…

Week 139 of the cracked.guide path. Time budget: about 5 hours. 101 exercises, rated .

Part 3 covers the rest of pages 79 to 97 of 7.2.2.1. It adds color controls: secondary items may be shared by several options if they all give the same color (XCC, Algorithm C), which handles word puzzles, MacMahon tiles and general constraint satisfaction. Then it introduces multiplicity: primary items covered between a lower and upper number of times (MCC), implemented by Algorithm M with a new dance step that tweaks lists instead of removing items.

## 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 2

## How to approach it

Add colors to your solver (Algorithm C): purify instead of cover when an option gives a secondary item a color. Model a word square or the zebra puzzle as XCC and solve it. Read Algorithm M for the ideas; implementing it is optional.

## Exercises

This week takes 78 to 178 from the first set (101 in all): color controls (Algorithm C, word puzzles, MacMahon tiles, partridge puzzles, about 78 to 161) and multiplicities (Algorithm M, about 162 to 178). Pick a few modeling exercises from each block.

Worth your time:

- 80 (rated 19): Run Algorithm C by hand on the small colored example until it finds a solution.
- 101 (rated 25, recommended): Formulate the zebra puzzle as an exact cover problem with colors.
- 117 (rated 24, recommended): Encode graph coloring as exact cover with secondary items per edge, then improve it using cliques.
- 169 (rated 22, recommended): Find all t-element independent sets of a graph as a multiplicity problem.

## Common traps

- Expecting colors to be free. A colored item is hidden, not covered, so it can still need purification work on every branch.

## Links

- [Knuth's TAOCP page (editions, errata, MIX/MMIX)](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
- [Vol 4B errata (plain text, from Knuth)](https://www-cs-faculty.stanford.edu/~knuth/err4b.textxt)
- [Wikipedia: Exact cover](https://en.wikipedia.org/wiki/Exact_cover)

---

Source: https://cracked.guide/guide/knuth-w120-1
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.