Glossary
What is dancing links?
Dancing links (often called DLX) is the observation that if you remove node x from a doubly linked list with L[R[x]] = L[x] and R[L[x]] = R[x], but leave x's own pointers alone, you can put it back later with L[R[x]] = x and R[L[x]] = x. Backtracking search can then undo every step instantly. Knuth named it and made it the engine of Algorithm X for exact cover.
Why it matters
A backtracking search spends most of its time trying a choice, recursing, and undoing the choice. If the data structure can be undone in constant time without copying, the search stays fast. In Algorithm X, the items to cover are a doubly linked list of headers, each with a vertical list of the options that cover it. Choosing an option removes every conflicting option from every list; backtracking puts them back, in exactly reverse order.
What it solves
Anything you can phrase as exact cover: sudoku, pentomino and polycube packing, N-queens, word puzzles and scheduling. Knuth extends it with secondary items, colors (XCC) and multiplicities (MCC) in Volume 4B, §7.2.2.1. On the path that section takes three weeks: part 1, part 2 and part 3. His annual Christmas lectures on dancing links are free on YouTube and a good warm-up.
Questions
Who invented dancing links?
The link-removal trick predates Knuth (he credits Hitotumatu and Noshita, 1979), but Knuth named it "dancing links", popularized it in a 2000 paper and built Algorithm X around it.
Is DLX the fastest sudoku solver?
It solves any sudoku in a blink and is easy to get right, but hand-tuned constraint solvers can be faster. Its strength is that one program handles every exact cover puzzle.