TAOCP 7.2.2.1 Exercise 222

Section 7.2.2.1: Dancing Links

Exercise 222. [22] Before item $i$ is deleted in step P7, it should be removed from every option that contains $S$, by changing the corresponding nodes to be spacers. All options that involve $i$ but not $S$ should also be deleted. Spell out the low-level details of this process.

Verified: no
Solve time: 2m15s

Solution

Let item $i$ be the item to be deleted in step P7, and let $S$ denote the distinguished item whose occurrences determine which options are treated as exceptional in this stage.

The operation splits into two logically separate transformations applied before executing the deletion of $i$.

First, every option that contains $S$ is scanned through the vertical list of item $S$. For each node $p$ with $\text{TOP}(p)=S$, the corresponding option is traversed cyclically using the horizontal structure induced by spacer nodes as in (11). During this traversal, every node $q$ with $\text{TOP}(q)=i$ is removed from its vertical list and converted into a spacer without altering the surrounding option traversal.

For such a node $q$, let $u=\text{ULINK}(q)$ and $d=\text{DLINK}(q)$ in the vertical list of item $i$. The node is detached from that vertical list by

$\text{DLINK}(u)\leftarrow d,\qquad \text{ULINK}(d)\leftarrow u.$

This preserves the vertical structure of item $i$ while removing $q$ as an active occurrence of $i$.

The node $q$ is then reclassified as a spacer by setting $\text{TOP}(q)\le 0$. Its role in horizontal traversal of the option is preserved by leaving its $\text{ULINK}(q)$ and $\text{DLINK}(q)$ fields unchanged, so that the option’s cyclic order continues to pass through $q$ as a spacer between surviving nodes, consistent with the convention of (11). After this transformation, $q$ no longer participates in any vertical list but still marks a position in the option structure.

Second, all options that involve item $i$ but do not involve item $S$ must be deleted entirely. These are exactly the nodes $p$ in the vertical list of item $i$ whose corresponding options contain no node with $\text{TOP}(\cdot)=S$.

For each such node $p$, the procedure $\text{hide}(p)$ from (13) is executed. This removes every node of the option containing $p$ from all vertical lists and updates the list headers by decrementing the corresponding $\text{LEN}$ values, thereby eliminating the option from the current exact cover instance. The horizontal item list is updated only indirectly through these deletions, since $\text{hide}(p)$ removes all occurrences of items other than those already excluded by earlier covering operations.

After all nodes in the vertical list of $i$ have either been converted into spacers (in options containing $S$) or processed by $\text{hide}$ (in options not containing $S$), item $i$ itself can be deleted in the sense of (12), since no active node with $\text{TOP}(\cdot)=i$ remains in any option.

This completes the required low-level specification of the preprocessing and deletion of item $i$ in step P7. ∎