TAOCP 7.2.2.1 Exercise 42

Section 7.2.2.1: Dancing Links

Exercise 42. [M21] [M21] Explain how the method of exercise 40 could be extended to give representations of all solutions, instead of simply counting them.

Verified: no
Solve time: 1m12s

Solution

Exercise 40 stores, for each reachable item set $s$, only the number $c$ of partial selections that produce $s$. The loss of information occurs when several distinct partial selections generate the same subset, because their counts are merged into a single entry. To enumerate all solutions, the database must retain enough information to reconstruct every partial selection that contributes to each reachable subset.

A convenient extension is to replace each count $c_j$ by a linked list of predecessors. Each database entry becomes a triple

$(s_j,L_j),$

where $L_j$ is the head of a list of records. Every record in that list has the form

$(k,\ell),$

meaning that the subset $s_j$ can be obtained by adjoining row $k$ to a previously generated subset represented by database entry $\ell$. For the initial entry we use a distinguished null predecessor.

Suppose Algorithm N3 is processing row $k$, and suppose that

$$ s_i \mathbin{&} r_k=0. $$

The new subset is

$$ s=s_i+r_k. $$

If no database entry for $s$ exists, a new entry is created whose predecessor list initially contains the single record $(k,i)$. If an entry for $s$ already exists, no new database entry is created; instead the additional predecessor record $(k,i)$ is appended to its predecessor list. Thus every distinct way of reaching the same subset is preserved explicitly instead of contributing only to an accumulated count.

The pruning method introduced in exercise 40 remains valid. When an entry is deleted because it cannot contribute to any complete solution, its predecessor list is deleted simultaneously. The compression based on nonprimary items is also unchanged, because it depends only on the represented subsets, not on the predecessor information attached to them.

After all rows have been processed, every database entry satisfying

$$ s_j \mathbin{&} p=p $$

represents one or more exact covers. Each predecessor record $(k,\ell)$ determines the last selected row of such a cover. Repeatedly following predecessor links reconstructs the entire sequence of selected rows in reverse order:

$$ (k_t,\ell_t)\rightarrow(k_{t-1},\ell_{t-1})\rightarrow\cdots\rightarrow(k_1,\ell_1), $$

terminating at the distinguished initial entry. Reversing this sequence yields the corresponding exact cover.

The predecessor records therefore form a directed acyclic graph whose source is the initial subset $0$ and whose sinks are the database entries representing complete covers. Every path from the source to a sink corresponds to exactly one solution, because each edge records the addition of a single row during Algorithm N3, and every solution determines a unique sequence of such additions. Conversely, every recorded path satisfies the disjointness test at every extension step and reaches a subset containing all primary items exactly once, hence it is an exact cover.

Therefore the counting algorithm of exercise 40 is transformed into a solution-enumeration algorithm simply by replacing each integer count with the complete predecessor information needed to reconstruct every path through the state graph. The asymptotic storage increases from one integer per reachable subset to one predecessor record per successful transition between reachable subsets, while all of the pruning techniques of exercise 40 remain applicable.

$$ \boxed{\text{Represent each reachable subset by its complete list of predecessors instead of a count, then reconstruct every exact cover by tracing predecessor chains from each terminal subset back to the initial subset.}} $$