TAOCP 7.2.2.1 Exercise 40

Section 7.2.2.1: Dancing Links

Exercise 40. ▶ [21] $[21]$ If we merely want to count the number of solutions to an exact cover problem, without actually constructing them, a completely different approach based on bitwise manipulation instead of list processing is sometimes useful.

The following naive algorithm illustrates the idea. We're given an $m \times n$ matrix of 0s and 1s, represented as $n$-bit vectors $r_1, \ldots, r_m$. The algorithm works with a (potentially huge) database of pairs $(s_j, c_j)$, where $s_j$ is an $n$-bit number representing a set of items, and $c_j$ is a positive integer representing the number of ways to cover that set exactly. Let $p$ be the $n$-bit mask that represents the primary items.

N1. [Initialize.] Set $N \leftarrow 1$, $s_1 \leftarrow 0$, $c_1 \leftarrow 1$, $k \leftarrow 1$.

N2. [Done?] If $k > m$, terminate; the answer is $\sum_{k=1}^{N} c_j [s_j \mathbin{&} p = p]$.

N3. [Append $r_k$ where possible.] Set $t \leftarrow r_k$. For $N \ge j \ge 1$, if $s_j \mathbin{&} t = 0$, insert $(s_j + t, c_j)$ into the database (see below).

N4. [Loop on $k$.] Set $k \leftarrow k + 1$ and return to N2. $\blacksquare$

To insert $(s, c)$ there are two cases: If $s = s_i$ for some $(s_i, c_i)$ already present, we simply set $c_i \leftarrow c_i + c$. Otherwise we set $N \leftarrow N + 1$, $s_N \leftarrow s$, $c_N \leftarrow c$.

Show that this algorithm can be significantly improved by using the following trick: Set $u_k \leftarrow r_k \mathbin{&} f_k$, where $f_k = r_{k+1} \mid \cdots \mid r_m$ is the bitwise OR of all future rows. If $u_k \ne 0$, we can remove any entry from the database whose subset does not contain $u_k \mathbin{&} p$. We can also exploit the nonprimary items of $u_k$ to compress the database further.

Verified: no
Solve time: 1m29s

Solution

The database after processing rows $r_1,\ldots,r_{k-1}$ consists of pairs $(s_j,c_j)$ where $s_j$ is an $n$-bit mask representing the union of selected rows and $c_j$ counts the number of ways to obtain $s_j$. At stage $k$, row $r_k$ is introduced and future rows are summarized by

$f_k = r_{k+1} \mid \cdots \mid r_m,$

so that $f_k$ contains exactly those items that can still be covered after stage $k$.

Define

$u_k = r_k \mathbin{&} f_k.$

Thus $u_k$ consists of items that occur in $r_k$ and also occur in at least one future row. Equivalently, every item in $u_k$ can still be covered without using $r_k$ alone, but every such item is also constrained by the future availability structure induced by rows $k+1,\ldots,m$.

At stage $k$, any completion of a partial selection must assign coverage to every item of $p$. Consider an item $i \in u_k \mathbin{&} p$. Such an item is present in $r_k$ and still available in future rows. If a partial state $s_j$ already omits $i$ from its covered set while $i$ is still required by $p$, then no extension using only rows $k,\ldots,m$ can restore feasibility unless some later row_