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: 2m55s

Edit

Solution

Let the database after rows (1,\ldots,k-1) have been processed contain entries

[ (s_j,c_j). ]

The invariant of Algorithm N is that (s_j) is the union of a collection of pairwise disjoint rows chosen from

[ r_1,\ldots,r_{k-1}, ]

and (c_j) is the number of such choices producing exactly that union. Initially the only choice is the empty set of rows, represented by

[ s_1=0,\qquad c_1=1. ]

When row (r_k) is considered, every old state either remains unchanged, or is extended by (r_k) when

[ s_j\mathbin{&}r_k=0 . ]

The insertion rule combines states with identical unions by adding their multiplicities, so the invariant is preserved.

Now define

[ f_k=r_{k+1}\mid r_{k+2}\mid\cdots\mid r_m ]

and

[ u_k=r_k\mathbin{&}f_k . ]

Thus (u_k) is the set of items that occur both in the current row and in at least one later row.

Consider a database entry ((s_j,c_j)) immediately before row (r_k) is processed. Suppose that there is a primary item (x) such that

[ x\in u_k\mathbin{&}p ]

but

[ x\notin s_j . ]

Then (x) occurs in (r_k), and it also occurs in some later row. If row (r_k) is selected, no later row containing (x) can be selected, because an exact cover cannot use an item twice. Since (x) was not already covered by (s_j), the resulting partial cover can never be completed to an exact cover of the primary items. Therefore this entry cannot contribute to the final answer.

Consequently every entry failing

[ u_k\mathbin{&}p\subseteq s_j ]

may be deleted before processing row (r_k). This is the first improvement.

Notice that this condition is only a necessary condition for an entry to survive. It does not assert that every surviving entry has a completion. Other rows may still make completion impossible.

The nonprimary bits of (u_k) allow a different kind of reduction. Let

[ v_k=u_k\mathbin{&}\overline p . ]

These are the nonprimary items that occur in both row (k) and in some future row. If a state (s_j) satisfies

[ s_j\mathbin{&}v_k\ne0, ]

then that state cannot be extended by row (r_k), because it already contains a nonprimary item that row (r_k) would use. Hence, when generating the new states obtained by appending (r_k), all entries with

[ s_j\mathbin{&}v_k\ne0 ]

can be skipped immediately. Only states satisfying

[ s_j\mathbin{&}u_k=0 ]

can generate an appended state

[ s_j\mid r_k . ]

The same observation gives a compression of the database representation. The full masks are needed only for those nonprimary items that can still affect compatibility with future rows. A nonprimary item of (u_k) is special because, once row (r_k) has been chosen, every future row containing that item is forbidden. Therefore states created by appending (r_k) need not store these particular nonprimary bits separately: their incompatibility with future rows is already known from the fact that row (r_k) was chosen.

Equivalently, after creating the new states obtained from row (r_k), one may store them using masks with the nonprimary part of (u_k) suppressed, provided the implementation also suppresses the corresponding tests against future rows for these states. The suppressed bits are not removed from arbitrary old states, because those states may represent solutions that do not use row (r_k). They are removed only from states whose history already contains the information that those conflicts have been settled.

When two compressed states become identical, their counts may again be combined by the insertion rule. The multiplicities are preserved because the suppressed bits no longer distinguish possible continuations: all continuations incompatible with those bits have already been excluded.

Thus the bitwise algorithm can be improved in two ways:

Before processing row (r_k), delete every state ((s_j,c_j)) for which

[ u_k\mathbin{&}p\not\subseteq s_j . ]

Use the nonprimary part

[ v_k=u_k\mathbin{&}\overline p ]

to avoid generating impossible extensions and to suppress nonprimary conflict information that has become implicit after a row choice has been made.

The first rule removes states that cannot possibly lead to exact covers, and the second rule reduces the amount of information stored in surviving states without changing the final count. (\boxed{})