Algorithm X Exact Cover
Cover every constraint once while watching reversible search decisions.
Free theory articleCover every constraint once while watching reversible search decisions.
Concept & interpretation
The exact cover problem requires finding a subset of rows in a binary matrix such that every column contains exactly one 1. Algorithm X is a straightforward recursive, nondeterministic, depth-first backtracking algorithm proposed by Donald Knuth to find all solutions to the exact cover problem.
Experiment
You can interactively observe the results of different configurations of the exact cover matrix and the column-picking rules.
- Open the Algorithm X Exact Cover module.
- Select Three covers in the Problem control to see a matrix with multiple exact covers.
- Change the Column rule to First column and observe that the number of solutions remains the same, though the traversal order changes.