TAOCP 7.2.2.1 Exercise 250
Let $Z$ be a set of characters with the property that for each $\alpha \in Z$, every option contains exactly one primary item whose name begins with $\alpha$.
Section 7.2.2.1: Dancing Links
Exercise 250. [21] [21] Users of Algorithm C* are allowed to supply hints that speed up the computation, by specifying (i) a set $Z$ of characters, such that every element of $Z$ is the first character of exactly one primary item in every option; also (ii) a number $z > 0$, meaning that every option contains exactly $z$ primary items whose names don't begin with a character in $Z$. (For example, $Z = {p, r, c, b}$ in the sudoku options (30); $z = 1$ in options (16).) In the options (16) for Langford pairs, we could change the name of each numeric item $i$ to '$i$', then let $Z = {!}$ and $z = 2$.) Explain how to use these hints to supply an early-cutoff test at the beginning of step C3*, as explained in the text.
Verified: yes
Solve time: 1m46s
Solution
Let $Z$ be a set of characters with the property that for each $\alpha \in Z$, every option contains exactly one primary item whose name begins with $\alpha$. Let $z > 0$ be such that every option contains exactly $z$ primary items whose names do not begin with a character in $Z$.
At any node of the search in Algorithm $C^*$, let the current partial solution have level $l$, and let $U$ denote the set of still-uncovered primary items.
For each $\alpha \in Z$, define $U_\alpha \subseteq U$ as the set of uncovered primary items whose names begin with $\alpha$, and write $r_\alpha = |U_\alpha|$. Let $U_0 \subseteq U$ be the set of uncovered primary items whose names begin with no character in $Z$, and write $r_0 = |U_0|$.
Each chosen option removes exactly one element from each nonempty set $U_\alpha$ in which it participates, since every option contains exactly one primary item for each $\alpha \in Z$. Therefore, if $k$ further options are selected, each set $U_\alpha$ can contribute at most $k$ covered items, hence a necessary condition for completion is $k \ge r_\alpha$ for every $\alpha \in Z$.
Thus any completion requires at least $\max_{\alpha \in Z} r_\alpha$ additional options.
Each option also removes exactly $z$ items from $U_0$, since it contains exactly $z$ primary items not beginning with characters in $Z$. Therefore $k$ further options remove at most $kz$ elements of $U_0$, which implies the necessary condition $kz \ge r_0$, hence $k \ge \left\lceil r_0 / z \right\rceil$.
Combining both constraints yields the lower bound on the number of further options required to complete the cover:
$$ k_{\min} = \max!\left(\max_{\alpha \in Z} r_\alpha,\ \left\lceil \frac{r_0}{z} \right\rceil\right). $$
In step C3$^*$, let $\theta = T - C_l$ as in the text, so any continuation must achieve total remaining cost at most $\theta$. Since each recursive step in the solution appends one option, any completion requires at least $k_{\min}$ additional levels.
Let $c_{\min}$ denote the minimum cost among all currently active options. Every extension by one option increases cost by at least $c_{\min}$, hence any completion from level $l$ has total additional cost at least $k_{\min} c_{\min}$.
The early cutoff condition at the beginning of C3$^*$ is obtained by testing whether even this optimistic bound exceeds the remaining budget:
$$ k_{\min} , c_{\min} > \theta. $$
If this inequality holds, no sequence of choices can complete the cover within the allowed cutoff, and the current branch is rejected immediately.
This completes the proof. ∎