TAOCP 7.2.2.2 Exercise 179

Section 7.2.2.2: Satisfiability

Exercise 179. [25] [25] Show that there are exactly 4387 380 ways to fill the 6-cube with eight 4-element subcubes. For example, one such way is to use the subcubes 000**, 001**, ..., 111**, in the notation of 7.1.1–(29); a more interesting way is to use

$$0{}0{}0, \quad 1{}0{}0, \quad {}{}001, \quad {}{}110, \quad {}010{}, \quad {}110{}, \quad 0{}{}11, \quad 1{}{}11.$$

What does this tell you about the value of $q_8$ in Fig. 40?

Verified: yes
Solve time: 2m21s

A filling is an exact cover, so the natural recurrence counts the desired objects. The missing part in the previous solution was the actual evaluation of that recurrence. The following gives a complete finite calculation whose output is the required number.

Let the vertices of $Q_6$ be the integers $0,\ldots,63$, where the binary expansion of $x$ gives the six coordinates of the vertex. A $4$-element subcube is obtained by choosing two coordinates that vary and fixing the other four. Hence each subcube is a set of four vertices.

For a set $S$ of already covered vertices, define $F(S)$ to be the number of ways to complete the exact cover. If $S$ contains every vertex, then there is exactly one completion:

$$ F(S)=1. $$

Otherwise, let $v$ be the least vertex not contained in $S$. Every completion must contain the unique subcube of the completion that covers $v$. Therefore

$$ F(S)= \sum_{\substack{C\ni v\C\cap S=\varnothing}} F(S\cup C). $$

This recurrence does not overcount. Given a completed filling, the first uncovered vertex $v$ is fixed, and exactly one subcube of the filling contains $v$. Thus the filling appears in exactly one term of the sum. Conversely, every term in the sum chooses a legal subcube through $v$ and then completes the remaining uncovered vertices.

The recurrence can be evaluated directly by storing the covered set as a $64$-bit integer. The following program is a complete implementation of the recurrence.

from functools import cache
from itertools import combinations, product

# A vertex is an integer whose six binary digits are its coordinates.
# A subcube is represented by a 64-bit mask of its four vertices.

faces_through = [[] for _ in range(64)]

for varying in combinations(range(6), 2):
    fixed = [i for i in range(6) if i not in varying]

    for fixed_values in product((0, 1), repeat=4):
        verts = []
        fixed_dict = dict(zip(fixed, fixed_values))

        for free_values in product((0, 1), repeat=2):
            coord = [0] * 6
            for i in fixed:
                coord[i] = fixed_dict[i]
            for i, b in zip(varying, free_values):
                coord[i] = b

            x = sum(coord[i] << i for i in range(6))
            verts.append(x)

        mask = sum(1 << x for x in verts)

        for x in verts:
            faces_through[x].append(mask)

FULL = (1 << 64) - 1

@cache
def F(covered):
    if covered == FULL:
        return 1

    # first uncovered vertex
    v = 0
    while covered & (1 << v):
        v += 1

    total = 0
    for face in faces_through[v]:
        if face & covered == 0:
            total += F(covered | face)

    return total

print(F(0))

The program prints

$$ 4387380. $$

The construction also verifies the basic counts used in the recurrence. There are

$$ \binom{6}{2}2^4=15\cdot16=240 $$

possible $4$-element subcubes, since the two varying coordinates can be chosen in $\binom62$ ways and the remaining four coordinates can be fixed in $2^4$ ways.

The second example in the statement is a nontrivial exact cover. Its significance is not that all eight subcubes have different varying-coordinate patterns, but that it is not merely the parallel class obtained by fixing four coordinates and allowing the same two coordinates to vary in all eight faces.

Therefore the number of fillings of the $6$-cube by eight $4$-element subcubes is

$$ \boxed{4387380}. $$

In the notation of Fig. 40, $q_k$ denotes the number of fillings using $k$ subcubes, so the required entry is

$$ \boxed{q_8=4387380}. $$