Algorithm X Exact Cover

Worked Example

Consider an exact cover problem with a universe of 3 elements (columns 0, 1, 2) and three available subsets (rows):

• A = {0, 1}
• B = {1, 2}
• C = {0}

We want to find subsets that exactly cover the universe {0, 1, 2} without overlap. Let's trace Algorithm X:

1. Start with an empty cover. The universe is not yet covered.
2. Choose column 2 (if using the 'Fewest rows' rule, since only row B contains it).
3. The only candidate row covering column 2 is B. Include B = {1, 2} in the cover.
4. The remaining uncovered column is 0.
5. Choose column 0. We cannot use row A = {0, 1} because it overlaps with row B at column 1. The only valid candidate is row C = {0}.
6. Include C in the cover.
7. All columns {0, 1, 2} are now covered by B, C. The solution is found.

Experiment

You can interactively observe the results of different configurations of the exact cover matrix and the column-picking rules.

1. Open the Algorithm X Exact Cover module.
2. Select Three covers in the Problem control to see a matrix with multiple exact covers.
3. Change the Column rule to First column and observe that the number of solutions remains the same, though the traversal order changes.

Limitations

Algorithm X solves the exact cover problem, which is NP-complete. In the worst case, the backtracking search tree explores an exponential number of row combinations. While Knuth's Dancing Links (DLX) optimization heavily improves the constant factor by using a circular doubly linked list for fast cover/uncover operations, the fundamental time complexity remains exponential. The visualization in this module uses a simple set-based backtracking approach and is suitable for small bounded matrices, not large-scale solver tasks.

References

The algorithm is famously described in Donald Knuth's paper on Dancing Links, which formalized Algorithm X.

• Donald E. Knuth, "Dancing links" (2000)- Describes the exact cover problem, Algorithm X, and its efficient implementation using doubly linked lists.