TAOCP 7.2.2.1 Exercise 251

Exercise 251. [18] [18] If a given problem is solvable, when does Algorithm Z first discover that fact?

Verified: yes
Solve time: 1m30s

Solution

Algorithm Z operates by recursive search over partial exact covers, maintaining the invariant that the current data structure represents the residual exact cover instance induced by the choices already made. At each recursive level it selects an item $i$, covers it, and branches over all options containing $i$, continuing until either failure is detected (no option covers $i$) or success is reached (no items remain).

The condition for success is precisely that the horizontal list of active items becomes empty. In the notation of Section 7.2.2.1, this occurs when the header node $0$ satisfies $\mathrm{RLINK}(0)=0$, since the circular doubly linked list of items contains only the header.

Let a computation path correspond to a sequence of cover operations applied to selected options $O_1, O_2, \dots, O_t$. After applying $\mathrm{cover}(i)$ for all items in each chosen option, the residual instance contains exactly the items not yet covered and the options not yet deleted by the hiding process in $\mathrm{hide}(p)$.

At the first moment when a complete exact cover exists along the chosen path, there is a smallest index $t$ such that the union of items in $O_1 \cup \cdots \cup O_t$ equals the full item set and these options are pairwise disjoint. At that point every item has been removed from the horizontal list by prior calls to $\mathrm{cover}(\cdot)$, so the algorithm reaches a recursive call in which no item $i$ can be selected in step C1 because the list is empty.

In that configuration step C1 immediately triggers termination with success, since the rule states that if no active items remain the algorithm halts successfully before any further branching or option selection. No earlier state can satisfy this condition, because as long as at least one item remains in the horizontal list, step C1 necessarily selects some item and continues the search.

Therefore, the first discovery of solvability occurs exactly at the first recursive activation in which all items have been covered, equivalently when the cover operations induced by a sequence of options first empty the horizontal item list, causing step C1 to find no selectable item and terminate successfully.

This completes the proof. ∎