TAOCP 7.2.2.1 Exercise 254
Let Algorithm Z operate on an exact cover instance with primary items and secondary items with colors, in the sense of Section 7.
Section 7.2.2.1: Dancing Links
Exercise 254. ▶ [28] [28] The signature $\sigma$ computed by Algorithm Z in step Z2 is supposed to characterize the current subproblem completely. It contains one bit for each primary item, indicating whether or not that item still needs to be covered.
a) Explain why one bit isn't sufficient for secondary items with colors.
b) Suggest a good way to implement the computation of $\sigma$.
c) Algorithm C uses the operations hide$'$ and unhide$'$ in (39)–(37), in order to avoid unnecessary accesses to memory in nodes for secondary items. Explain why Algorithm Z does not want to use those optimizations. Hint: Algorithm Z needs to know whether the option list for a secondary item is empty.
d) When the list for item $i$ is purified, its options of the wrong color are removed from other lists. But they remain on list $i$, in order to be unpurified later. How then can Algorithm Z know when list $i$ is no longer relevant to the current subproblem?
Verified: no
Solve time: 2m25s
Setup
Let Algorithm Z operate on an exact cover instance with primary items and secondary items with colors, in the sense of Section 7.2.2.1. The signature $\sigma$ is computed in step Z2 and is intended to encode the current subproblem completely from the viewpoint of Algorithm Z. The signature contains one bit per primary item, indicating whether that item still needs to be covered.
The state of the search at any moment is determined by the currently active items and the currently active options after successive applications of $\text{cover}(i)$, $\text{hide}(p)$, and their inverses. Primary items are required to be covered exactly once. Secondary items may be optionally used, but when colors are present, compatibility constraints restrict which options remain valid.
The problem is to explain limitations of the signature representation, propose an efficient computation method, and analyze why Algorithm Z cannot adopt the optimizations of hide$'$ and unhide$'$, and how relevance of secondary lists is detected despite persistence of removed options.
Solution
(a) Why one bit is not sufficient for secondary items with colors
A secondary item with colors is not a binary condition of “present or absent in the residual problem”. Its effective state depends on which colored options remain compatible after prior cover operations.
A single bit would distinguish only whether the item is still considered, but it cannot distinguish between multiple distinct residual configurations that differ in color availability. After purifications, different subsets of options remain on other item lists, while the original list for the secondary item still physically contains all options, including those that are no longer valid. Two subproblems may agree on whether the secondary item exists but differ in which colors are still realizable through compatible options. Since Algorithm Z distinguishes subproblems by the structure of remaining choices, a single bit cannot distinguish states that lead to different future branching behavior.
Therefore, secondary items require more than a boolean presence indicator because their effective contribution is determined by the filtered option structure across other items, not by a single inclusion flag.
(b) A good way to implement the computation of $\sigma$
The signature $\sigma$ is defined only over primary items, so its computation can be restricted to the horizontal list of active primary headers.
A direct implementation maintains the list of active primary items using the $\text{RLINK}$ chain of the header node. The signature is then computed by traversing this list and setting one bit per encountered primary item header. Concretely, if $i$ is a primary item, the bit $\sigma_i$ is set to $1$ if and only if $i$ is still in the active header list; otherwise it is $0$.
Efficient maintenance follows directly from the effect of $\text{cover}(i)$ in (12), where removal of an item from the header list is performed by updating $\text{LLINK}(r)$ and $\text{RLINK}(l)$. Each such update corresponds to flipping a single bit in $\sigma$. Thus $\sigma$ can be updated incrementally: each execution of $\text{cover}(i)$ or $\text{uncover}(i)$ toggles exactly the bit corresponding to $i$, and no traversal is required if a direct pointer from item headers to bit positions is stored.
This produces $\sigma$ in time proportional to the number of primary items covered or uncovered along the current search path, without scanning inactive structures.
(c) Why Algorithm Z does not use hide$'$ and unhide$'$ optimizations
The operations hide$'$ and unhide$'$ eliminate accesses to nodes belonging to secondary items by skipping them entirely. This optimization is valid when such nodes are irrelevant to correctness and bookkeeping.
Algorithm Z, however, depends on detecting whether the option list for a secondary item becomes empty after successive $\text{hide}(p)$ operations. This information is essential for correctness because it determines whether a partial assignment remains feasible.
In particular, after applying $\text{cover}(i)$, secondary items may lose all compatible options due to color filtering, and detecting this failure requires examining whether any node remains in their vertical structure. The optimization hide$'$ suppresses exactly the accesses needed to detect this emptiness condition. If those nodes are never visited, Algorithm Z loses the ability to determine whether a secondary item has become isolated with no available options, and thus cannot correctly prune infeasible branches.
Therefore Algorithm Z cannot adopt hide$'$ and unhide$'$ because it must preserve the ability to observe structural emptiness in secondary item lists during search.
(d) How Algorithm Z knows when a secondary item list is no longer relevant
A secondary item list remains physically present even when all of its compatible options have been removed from other lists during purification. Relevance in Algorithm Z is not determined by membership in the structure but by whether the item still participates in any active option.
Let $i$ be a secondary item. After successive applications of $\text{hide}(p)$ and color filtering, the list of active options involving $i$ is empty exactly when every node originally connected to $i$ has been removed from all other item lists. In the representation of Section 7.2.2.1, this corresponds to the situation where traversal of the vertical structure of $i$ encounters only spacer behavior or no remaining active nodes.
Algorithm Z detects this condition indirectly through the fact that each removal of an option decreases the effective degree of involved items, and the absence of any remaining node $p$ with $\text{TOP}(p)=i$ in active structures implies that no recursive step in (9) can be generated from $i$. At that point, although the physical list for $i$ persists, it is no longer reachable through any active $\text{DLINK}$ traversal initiated from active options.
Thus $i$ is no longer relevant precisely when no active option node references it in the current state of the DLX structure, which is detectable by the absence of any reachable node in its incidence structure from the active option pool.
Verification
The argument for (a) distinguishes structural identity of subproblems from a binary presence flag, since colored secondary items encode compatibility classes not representable by a single bit. This follows from the fact that option filtering changes the set of valid continuations without removing the item header.
The construction in (b) matches the invariant that $\sigma$ encodes exactly the set of active primary headers, and each application of (12) modifies exactly one header link pair, so bit updates are one-to-one with cover and uncover operations.
In (c), hide$'$ eliminates traversal of nodes whose absence is required to detect whether secondary item lists become empty, which is a necessary failure condition in Algorithm Z. Removing these accesses breaks correctness detection for infeasible subproblems.
In (d), relevance is characterized by reachability of active option nodes through the DLX incidence structure, consistent with the semantics of (13), since only nodes participating in active options remain linked through ULINK and DLINK after successive hide operations.
This completes the proof. ∎