Dancing Links

Knuth credits Hiroshi Hitotsumatsu and Kōhei Noshita with having invented the idea in 1979,[2] but it is his paper which has popularized it.

Knuth observed that a naive implementation of his Algorithm X would spend an inordinate amount of time searching for 1's.

To improve this search time from complexity O(n) to O(1), Knuth implemented a sparse matrix where only 1's are stored.

Each row and column in the matrix will consist of a circular doubly-linked list of nodes.

Selecting a column with a low node count is a heuristic which improves performance in some cases, but is not essential to the algorithm.

If a selected column doesn't have any rows, the current matrix is unsolvable and must be backtracked.

Knuth's paper gives a clear picture of these relationships and how the node removal and reinsertion works, and provides a slight relaxation of this limitation.