rows at level 3, thus the algorithm moves to the next branch at level 2… There are no more selected rows at level 2, thus the algorithm moves to the next branch at level 1… There are no more selected rows at level 1, thus the algorithm moves to the next branch at level 0… There are no branches at level 0, thus the algorithm terminates. In summary, the algorithm determines there is only one exact cover: = {B, D, F}. Implementations Knuth's main purpose in describing Algorithm X was to demonstrate the utility of dancing links. Knuth showed that Algorithm X can be implemented efficiently on a computer using dancing links in a process Knuth calls "DLX". DLX uses the matrix representation of the exact cover problem, implemented as doubly linked lists of the 1s of the matrix: each 1 element has a link to the next 1 above, below, to the left, and to the right of itself. (Technically, because the lists are circular, this forms a torus). Because exact cover problems tend to be sparse, this representation is usually much more efficient in both size and processing time required. DLX then uses dancing links to quickly select permutations of rows as possible solutions and to efficiently backtrack (undo) mistaken guesses. See also Exact cover Dancing Links References . External links Knuth's paper - PDF file (also ) Knuth's Paper describing the Dancing Links optimization - Gzip'd postscript file. Search algorithms Donald Knuth