Exact Cover Problem and Knuth’s Algorithm X

I‘ve put together an implementation of Knuth’s Algorithm X (Wikipedia), which solves the Exact Cover problem (Wikipedia).

The example from Algorithm X’s Wikipedia page is as follows:

Set A = delim{lbrace}{1, 4, 7}{rbrace}
Set B = delim{lbrace}{1, 4}{rbrace}
Set C = delim{lbrace}{4, 5, 7}{rbrace}
Set D = delim{lbrace}{3, 5, 6}{rbrace}
Set E = delim{lbrace}{2, 3, 6, 7}{rbrace}
Set F = delim{lbrace}{2, 7}{rbrace}

Is there a set of sets that covers each column exactly once? In this example, the solution is delim{lbrace}{B,D,F}{rbrace}, since that yields delim{lbrace}{1, 4}{rbrace}union delim{lbrace}{3, 5, 6}{rbrace}union delim{lbrace}{2, 7}{rbrace} — none left out and none duplicated.

Algorithm X is a recursive back-tracking search; it simply tries one set, prunes down the search space, rolls back if it hits a dead end, tries another set. The secret sauce, however, is the data structure and the concept called Dancing Links (my little write-up here).

Implementation reference: Dancing Links, Knuth. If you want to understand my implementation, this reference is a must-read.

My implementation is in git and below:

Leave a Reply