TAOCP Vol 4B: Combinatorial Algorithms, Part 2 · Week 139
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 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.
This week's steps
3 stepsRead §7.2.2.1 Dancing Links (part 3)
Add colors to your solver (Algorithm C): purify instead of cover when an option gives a secondary item a color.
Start with Ex 80, Ex 101, Ex 117; log what you solve below.
Write down one thing you'd explain to someone
A few sentences in your own words: the idea, why it works, an example.
Sign in to track this: tick each step off and it counts toward your week.
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
Exercise 11724▶ Recommended
Encode graph coloring as exact cover with secondary items per edge, then improve it using cliques.
Exercise 16922▶ Recommended
Find all t-element independent sets of a graph as a multiplicity problem.
Your log
Sign in to log the exercises you work: number, rating, how far you got.
Discussion
0 postsQuestions about the reading go here; each exercise has its own thread below. Hints over answers.
No posts yet. Ask a question or share a tip.
Sign in to postAnyone can read. Posting needs an account with a confirmed email.
Exercise threads
One thread per exercise. Open one to ask for a nudge or check your thinking.
Exercise 8019No posts yet
Hints over answers. Say what you tried; put an answer or a full solution inside a spoiler:
||like this||or a```spoilerblock.Sign in to postAnyone can read. Posting needs an account with a confirmed email.
Exercise 10125No posts yet
Hints over answers. Say what you tried; put an answer or a full solution inside a spoiler:
||like this||or a```spoilerblock.Sign in to postAnyone can read. Posting needs an account with a confirmed email.
Exercise 11724No posts yet
Hints over answers. Say what you tried; put an answer or a full solution inside a spoiler:
||like this||or a```spoilerblock.Sign in to postAnyone can read. Posting needs an account with a confirmed email.
Exercise 16922No posts yet
Hints over answers. Say what you tried; put an answer or a full solution inside a spoiler:
||like this||or a```spoilerblock.Sign in to postAnyone can read. Posting needs an account with a confirmed email.
Reference
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.
Common traps
- Expecting colors to be free. A colored item is hidden, not covered, so it can still need purification work on every branch.