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.