whoashish's cp notes

Dancing Links

3 min read

Purpose: The data structure (Knuth, “DLX”) that makes Algorithm X fast: a sparse 0/1 matrix stored as a toroidal doubly linked list, in which removing and restoring a node are both .

The Core Trick

In a doubly linked list, removing node x:

x->left->right = x->right;
x->right->left = x->left;

But x itself still points at its old neighbours. So restoring it is just:

x->left->right = x;
x->right->left = x;

No allocation, no stack of saved values, no copying. Backtracking becomes free. Knuth called the effect “dancing” because the pointers seem to leap out and back.

Structure

  • Every 1 in the matrix becomes a node linked to its neighbours in all four directions (L, R, U, D), with wraparound.
  • Each column has a header node carrying a size counter; headers are linked in a horizontal ring rooted at a special node h.
  • Rows are horizontal rings; there is no row header needed, only a stored row identifier.

Cover and Uncover

void cover(Node* c) {
    c->R->L = c->L; c->L->R = c->R;                 // unlink the column header
    for (Node* i = c->D; i != c; i = i->D)
        for (Node* j = i->R; j != i; j = j->R) {
            j->D->U = j->U; j->U->D = j->D;         // unlink each node of the row
            j->col->size--;
        }
}
 
void uncover(Node* c) {
    for (Node* i = c->U; i != c; i = i->U)
        for (Node* j = i->L; j != i; j = j->L) {
            j->col->size++;
            j->D->U = j; j->U->D = j;               // relink, exact reverse order
        }
    c->R->L = c; c->L->R = c;
}

Order matters

uncover must undo in exactly the reverse order of cover — reverse the direction of both loops (D→U, R→L). Getting this wrong produces a structure that looks fine for a few steps and then corrupts silently.

void search(int depth) {
    if (h->R == h) { report(solution, depth); return; }
 
    Node* c = nullptr; int best = INT_MAX;          // S-heuristic
    for (Node* j = h->R; j != h; j = j->R)
        if (j->size < best) { best = j->size; c = j; }
    if (best == 0) return;                          // dead end
 
    cover(c);
    for (Node* r = c->D; r != c; r = r->D) {
        solution[depth] = r->rowId;
        for (Node* j = r->R; j != r; j = j->R) cover(j->col);
        search(depth + 1);
        for (Node* j = r->L; j != r; j = j->L) uncover(j->col);
    }
    uncover(c);
}

Paradigm

Backtracking with an -undo data structure. The algorithmic idea is Algorithm X; DLX is pure engineering — but engineering that buys two orders of magnitude.

Complexity

  • cover / uncover: , with no hidden constant
  • Overall: exponential (exact cover is NP-complete), but the constant factor is tiny and the S-heuristic keeps the tree small
  • Space: nodes, allocated once up front

Array-based DLX

Instead of pointers, use six parallel int arrays (L, R, U, D, col, row) indexed by node id. Same algorithm, far better cache behaviour, and no allocator pressure — this is what competitive implementations do.

Variants / Use Cases

  • Sudoku solvers — the canonical demo; solves the hardest known puzzles in microseconds
  • Polyomino / pentomino tiling, N-Queens, Latin squares, Langford pairs
  • Exact Cover — the modelling page
  • XCC (exact cover with colours) — Knuth’s extension in TAOCP Volume 4B, for puzzles with compatibility constraints
  • Any backtracking with heavy undo — the dancing-links idea generalises to rollback DSU, persistent structures, and undo-able segment trees

Graph View