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

Set

Set

Set

Set

Set

Is there a set of sets that covers each column exactly once? In this example, the solution is , since that yields — 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:

*Related*