TAOCP 7.2.2.1 Exercise 220
Let $A$ be an exact cover problem in the sense of Section 7.
Section 7.2.2.1: Dancing Links
Exercise 220. [28] Step P5 of Algorithm P needs to emulate step C5 of Algorithm C; to see if some primary item will lose all of its options. Describe in detail what needs to be done.
Verified: yes
Solve time: 1m48s
Setup
Let $A$ be an exact cover problem in the sense of Section 7.2.2.1, with primary items represented by header nodes $i$ whose field $\mathrm{LEN}(i)$ counts the number of currently active options containing item $i$. In Algorithm X with dancing links, covering an item performs deletions that decrement certain $\mathrm{LEN}(x)$ values via the operation in (13).
Step C5 of Algorithm C is the feasibility test that terminates the current branch as soon as some primary item has no remaining options. In the present data structure this condition is
$$ \exists i \text{ primary item such that } \mathrm{LEN}(i)=0. $$
Algorithm P replaces the global matrix-based checks of Algorithm C with local pointer updates. Step P5 must therefore reproduce the effect of C5 using only the incremental updates performed during $\mathrm{cover}(i)$ and $\mathrm{hide}(p)$.
The task is to describe precisely how P5 detects the loss of all options for any primary item during the execution of cover-and-hide operations.
Solution
In Algorithm C, step C5 inspects all primary items after each inclusion decision and halts if any column sum becomes zero. In the linked structure, this corresponds to the invariant that every primary item header $x$ must satisfy $\mathrm{LEN}(x)\ge 1$ throughout any partial solution.
During execution of $\mathrm{cover}(i)$, the only updates that can change $\mathrm{LEN}(x)$ occur inside $\mathrm{hide}(p)$ in (13). Each time a node $q$ with $\mathrm{TOP}(q)=x>0$ is processed, the assignment
$$ \mathrm{LEN}(x)\leftarrow \mathrm{LEN}(x)-1 $$
reduces the number of active options containing item $x$ by exactly one, since precisely one option containing $x$ is removed at that moment.
To emulate C5 without scanning all items globally, P5 must detect whether any such decrement produces $\mathrm{LEN}(x)=0$. This detection must occur immediately after each decrement, since a zero entry invalidates the current partial solution.
Thus P5 augments the inner loop of $\mathrm{hide}(p)$ as follows. When processing a node $q$, if $x=\mathrm{TOP}(q)>0$, the algorithm performs the standard link deletion and then executes the test
$$ \text{if } \mathrm{LEN}(x)=0 \text{ then signal failure.} $$
Signaling failure means abandoning the current chain of recursive extensions initiated by the most recent choice of option $O$ in step (9), and initiating the corresponding sequence of $\mathrm{unhide}$ and $\mathrm{uncover}$ operations that restores the data structure to the state before the offending $\mathrm{cover}$ call.
This local test is sufficient because every decrement of $\mathrm{LEN}(x)$ arises from the removal of exactly one option containing $x$, and no other operation modifies $\mathrm{LEN}(x)$. Hence $\mathrm{LEN}(x)=0$ holds if and only if the last remaining option containing $x$ has just been deleted, which is precisely the condition that C5 detects in the matrix formulation.
To complete the emulation, P5 must ensure that all affected primary items are correctly restored during backtracking. Since each decrement is paired with a corresponding increment performed in $\mathrm{unhide}(p)$ and ultimately in $\mathrm{uncover}(i)$, no additional global recomputation is required. The correctness of P5 therefore reduces to maintaining the invariant that every decrement of $\mathrm{LEN}(x)$ is reversible and that the zero test is performed immediately after each decrement.
Verification
Each execution of $\mathrm{hide}(p)$ touches exactly those nodes corresponding to options containing the chosen item $i$. For each such node with $\mathrm{TOP}(q)=x>0$, exactly one option containing $x$ is removed, so $\mathrm{LEN}(x)$ decreases by one. No other operation in (12)–(14) alters $\mathrm{LEN}(x)$, so the value of $\mathrm{LEN}(x)$ after processing $q$ equals the number of still-active options containing $x$.
If $\mathrm{LEN}(x)=0$ after the decrement, then every option containing $x$ has been removed from the active structure, since the decrements are in bijection with removed nodes of vertical lists. Hence no extension of the current partial solution can cover $x$, which matches exactly the failure condition of C5.
Conversely, if C5 would detect failure in the matrix model, then some primary item $x$ has no remaining 1s in any active row. In the linked representation this means every node of column $x$ has been removed by $\mathrm{hide}$ operations, so $\mathrm{LEN}(x)=0$ must occur during the last such removal. Therefore P5 detects every failure that C5 detects.
This establishes equivalence of the failure conditions under incremental updates. ∎
Notes
The essential mechanism in P5 is that the column-count test of Algorithm C is replaced by maintaining $\mathrm{LEN}(x)$ as a dynamic invariant. The cost of C5’s global scan is eliminated, since failure detection is reduced to constant-time checks at the exact moment each column is affected by a deletion.