TAOCP 7.2.2.1 Exercise 82
Let primary items be indexed by $1,2,\dots,N_1$, and let items with index $x > N_1$ be secondary items.
Section 7.2.2.1: Dancing Links
Exercise 82. [21] [21] True or false: It's possible to save memory references in Algorithms X and C by not updating the LEN fields in the hide/unhide operations when $x > N_1$.
Verified: yes
Solve time: 1m03s
Solution
Let primary items be indexed by $1,2,\dots,N_1$, and let items with index $x > N_1$ be secondary items. In Algorithm X (and its implementation C), the field $\mathrm{LEN}(x)$ is used only to represent the current number of nodes in the vertical list of item $x$ and to support the heuristic that selects an item of minimum list length.
The operations $\mathrm{hide}(p)$ and $\mathrm{unhide}(p)$ decrement and increment $\mathrm{LEN}(x)$ for every item $x$ whose vertical list is modified by removal or restoration of nodes belonging to options containing $p$. These updates affect only the bookkeeping used to guide item selection; they do not affect the structural correctness of the covering and uncovering process, which is entirely determined by the $\mathrm{DLINK}$, $\mathrm{ULINK}$, $\mathrm{LLINK}$, and $\mathrm{RLINK}$ fields.
If $x > N_1$, then item $x$ is never chosen in step C1 or the corresponding selection step of Algorithm X, because the search is restricted to primary items when determining whether the exact cover is complete. Consequently, the value of $\mathrm{LEN}(x)$ is never used in any decision that affects the search tree, since no selection rule consults secondary items.
During execution of $\mathrm{cover}(i)$ and $\mathrm{uncover}(i)$, the modification of $\mathrm{LEN}(x)$ for $x > N_1$ affects only data that is never read for control flow or termination. The correctness of hiding and unhiding depends solely on restoring the doubly linked structure of active options and items, which is independent of the numerical values stored in $\mathrm{LEN}(x)$.
Therefore, omitting the updates
$\mathrm{LEN}(x) \leftarrow \mathrm{LEN}(x) - 1 \quad \text{and} \quad \mathrm{LEN}(x) \leftarrow \mathrm{LEN}(x) + 1$
whenever $x > N_1$ leaves all pointer manipulations in $\mathrm{hide}$ and $\mathrm{unhide}$ unchanged and preserves the invariant that the active structure represents exactly the remaining uncovered incidence relations between options and items.
Since no step of Algorithm X or C uses $\mathrm{LEN}(x)$ for $x > N_1$ in item selection or termination, the search behavior is unchanged.
This completes the proof. ∎