Dancing Links — Brief ☧
"In whom are hid all the treasures of wisdom and knowledge."
— Colossians 2:3 (KJV)
Deep version → | Back to Streaming Intersection →
Q: Imagine you are assigning chores to a group of people. Each
person can handle certain chores but not others. You need an assignment
where every chore is covered by exactly one person, and no person is
double-booked. How would you approach this?
A: This is the exact cover problem, and it is surprisingly hard
in general — it is NP-complete. The brute-force approach tries every
possible combination, which explodes exponentially. Donald Knuth devised
an elegant algorithm called Algorithm X
for this, and his key insight was in the data structure: **Dancing Links
(DLX)**.
Here is the idea. Represent the constraint matrix (people vs. chores)
as a grid of doubly-linked list nodes.
Each node links to its neighbors in four directions: up, down, left,
right. When you tentatively assign a person to a chore, you unlink
all conflicting rows and columns — the nodes detach from their
neighbors. To backtrack, you simply relink them — the nodes "dance"
back into place because each node still remembers its old neighbors.
Q: Why is this better than just deleting and re-creating rows?
A: Because unlinking and relinking are both O(1) operations —
constant time. You never copy or
reallocate memory. The "dancing" metaphor is perfect: the nodes step
out of line and step right back in, and the rest of the list does not
even notice. This makes backtracking extremely cheap, which matters
because exact cover problems involve a lot of backtracking.
Q: Can this be parallelized?
A: Yes, and this is where Edward Kmett's contribution comes in.
Using SIMD (Single Instruction, Multiple Data) — processor instructions
that operate on multiple values simultaneously — you can check column
coverage for many columns at once using bitmask
operations. Our FPGA takes this further: it checks all columns in
parallel across hardware lanes, turning the sequential coverage check
into a single-cycle operation.
Key Concepts
| Concept | Meaning | Our Project |
|---|---|---|
| Exact cover | Every column covered exactly once | Constraint satisfaction |
| DLX | Doubly-linked matrix with cover/uncover | Backtracking search with O(1) undo |
| Column selection | Choose column with fewest 1s | Fail-first heuristic |
| SIMD version | Parallel coverage with bit ops | FPGA lane-parallel search |
Each row in this table maps a classical Algorithm X concept to its counterpart in our FPGA system, and the parallels are remarkably tight. The exact cover problem asks "can I select a subset of rows such that every column has exactly one 1?" Our constraint satisfaction problem asks "can I select one value for each variable such that every constraint is satisfied?" Both involve systematic search with backtracking, and both benefit enormously from choosing the right starting point. Knuth's insight -- that the column with the fewest 1s should be covered first -- is exactly our fail-first heuristic: the variable with the smallest domain should be propagated first, because it has the fewest remaining options and will produce the smallest search tree.
Connection to our system: Our FPGA-based constraint solver is spiritually
a Dancing Links engine running on custom hardware. The "cover" operation -- removing rows and columns from the constraint matrix -- corresponds to domain intersection (AND two
bitmasks) which eliminates impossible values. The "uncover" operation -- restoring the removed rows and columns on backtrack -- corresponds to restoring the previous domain state, which in our FPGA implementation is done by maintaining a stack of domain snapshots. The SIMD parallelism that Edward Kmett applied to DLX (checking multiple columns simultaneously using bitmask operations) is exactly what our FPGA implements at the hardware level: all 64 bits of a domain word are checked in a single clock cycle, and the 8-lane M6B configuration checks 8 variables simultaneously. This is Dancing Links at silicon speed.
Soli Deo Gloria