TAOCP 7.2.2.1 Exercise 214
Let a _string solution_ be a sequence of options produced by the search procedure, where the same underlying exact cover solution may appear in different orders depending on the choices made during ba...
Section 7.2.2.1: Dancing Links
Exercise 214. [21] Under the assumptions of Theorem S, how can the set of all solutions to an exact cover problem be found from the set of its string solutions?
Verified: no
Solve time: 1m54s
Solution
Let a string solution be a sequence of options produced by the search procedure, where the same underlying exact cover solution may appear in different orders depending on the choices made during backtracking. Let a solution of the exact cover problem be a set of options whose union covers each item exactly once.
Define a mapping $\Phi$ from string solutions to sets of options by letting $\Phi(S)$ be the set obtained from a string solution $S$ after forgetting order and removing repetitions of identical options if they occur.
Each string solution consists of a sequence of options that are pairwise compatible in the sense that Algorithm X only appends an option after all conflicts with previously chosen options have been eliminated by covering operations. Therefore, every option appearing in a string solution is valid with respect to the residual exact cover constraints at the moment it is chosen. The covering operations ensure that no item appears in two distinct chosen options, so $\Phi(S)$ is an exact cover.
Conversely, let $T$ be any exact cover solution, viewed as a set of options. Under the assumptions of Theorem S, the search procedure explores all admissible choices in all possible orders consistent with the covering recursion. In particular, for each ordering of the options in $T$ that is compatible with the recursive item-selection process, the algorithm generates a corresponding string solution whose underlying set of options is exactly $T$. Hence every exact cover solution arises as $\Phi(S)$ for at least one string solution $S$.
Two string solutions $S$ and $S'$ satisfy $\Phi(S)=\Phi(S')$ precisely when they differ only by the order in which the same options are chosen during recursion. No other source of duplication exists, since the covering rules prevent the introduction of any option not belonging to the final exact cover set.
The set of all solutions of the exact cover problem is therefore obtained by applying $\Phi$ to the set of all string solutions and identifying equal images. Equivalently, it is the quotient of the set of string solutions by the equivalence relation “has the same underlying set of options”.
A canonical representative of each solution class is obtained by sorting the options within each string solution in increasing lexicographic order of their item lists, then discarding duplicates. The resulting collection is in one-to-one correspondence with the set of exact cover solutions.
This completes the proof. ∎