TAOCP 7.2.2.1 Exercise 221
Let $S$ be the stack formed in step P7 after all options that begin with items already on the search stack have been examined.
Section 7.2.2.1: Dancing Links
Exercise 221. [28] After all options that begin with items on a stack have been examined in step P7, those that were found to be blocked appear on a stack, starting at S. Explain how to delete them. Caution: The problem might become unsolvable when an option goes away.
Verified: no
Solve time: 2m04s
Setup
Let $S$ be the stack formed in step P7 after all options that begin with items already on the search stack have been examined. Each element of $S$ is a blocked option $O$, represented in memory by a cyclic sequence of nodes in the exact-cover data structure described in Section 7.2.2.1, separated by spacer nodes as in (11). Each such option $O$ contains nodes $p$ with item indices $x=\mathrm{TOP}(p)>0$.
The task is to delete every option stored in $S$ from the current exact cover instance. Deleting an option means removing all of its nodes from the vertical lists of their respective items and updating all affected link fields so that the option is no longer available for future selection. The operation must preserve the ability to detect whether any item has lost all remaining options, since this forces immediate failure.
Solution
The stack $S$ is processed by repeatedly removing its top element until it becomes empty. Let $O$ be the option at the top of $S$, and let $p$ be the first node of $O$ in memory order.
The deletion of $O$ proceeds by traversing its nodes cyclically in the same way as in the inner loop of $\mathrm{hide}(p)$ in (13), but applied to every node belonging to the option, not only those reached during covering a single item.
Starting at a node $q$ in $O$, one sets $x \leftarrow \mathrm{TOP}(q)$, $u \leftarrow \mathrm{ULINK}(q)$, and $d \leftarrow \mathrm{DLINK}(q)$. If $x>0$, meaning $q$ is not a spacer, then the node $q$ is currently active in the vertical list of item $x$. In this case the links are updated by
$$ \mathrm{DLINK}(u) \leftarrow d, \qquad \mathrm{ULINK}(d) \leftarrow u, $$
and the item counter is decreased by
$$ \mathrm{LEN}(x) \leftarrow \mathrm{LEN}(x)-1. $$
After this update, traversal continues to the next node of the option in memory order. If $x \le 0$, then $q$ is a spacer node and only traversal advances without modifying any list structure.
When the traversal returns to the starting node $p$, the entire option $O$ has been removed from all vertical lists in which it participates. The option record is then discarded from $S$, and the next blocked option becomes the new top of $S$.
During this process, after every decrement of a value $\mathrm{LEN}(x)$, the algorithm must test whether $\mathrm{LEN}(x)=0$ for any item $x$ that is still present in the horizontal item list. If such an item exists, then no active option remains that covers $x$. Since exact cover requires every item to be covered exactly once, the residual instance has no solution and the deletion process terminates immediately with failure.
After $S$ becomes empty, all blocked options have been removed, and the data structure reflects the instance obtained after permanent elimination of those options.
Verification
Each node $q$ with $\mathrm{TOP}(q)>0$ appears in exactly one item list and contributes exactly one decrement to the corresponding $\mathrm{LEN}(x)$ when removed, since each option node is incident to a unique item. The update
$$ \mathrm{DLINK}(u) \leftarrow d, \qquad \mathrm{ULINK}(d) \leftarrow u $$
is identical to the unlinking operation in (13), so each removal preserves consistency of the doubly linked vertical lists.
Spacer nodes satisfy $\mathrm{TOP}(q)\le 0$ and therefore induce no updates, so they do not affect any $\mathrm{LEN}(x)$ or list structure.
If some item $x$ reaches $\mathrm{LEN}(x)=0$, then no node with $\mathrm{TOP}(\cdot)=x$ remains in any vertical list. By construction of the exact cover representation, this implies no remaining option covers $x$, so any purported solution would fail to include $x$ exactly once. Hence termination with failure is correct.
Each option in $S$ is processed exactly once when it is popped from the stack, so no option is deleted twice and no active option is skipped.