TAOCP 7.2.2.1 Exercise 384
An $l \times m \times n$ motley dissection consists of a family of subcuboids $[a_i,b_i) \times [c_i,d_i) \times [e_i,f_i),$ with $0 \le a_i < b_i \le l$, $0 \le c_i < d_i \le m$, $0 \le e_i < f_i \le...
Section 7.2.2.1: Dancing Links
Exercise 384. [34] [34] By generalizing exercises 365 and 370, explain how to find every motley dissection of an $l \times m \times n$ cuboid, using Algorithm M. Note: In three dimensions, the strictness condition $(a_i, b_i) \ne (0, m)$ and $(c_i, d_i) \ne (0, n)$ of exercise 362 should become
$$[(a_i, b_i) \ne (0, l)] + [(c_i, d_i) \ne (0, m)] + [(e_i, f_i) \ne (0, n)] ;\ge; 1.$$
What are the results when $l = m = n = 7$?
Verified: no
Solve time: 1m07s
Setup
An $l \times m \times n$ motley dissection consists of a family of subcuboids
$[a_i,b_i) \times [c_i,d_i) \times [e_i,f_i),$
with $0 \le a_i < b_i \le l$, $0 \le c_i < d_i \le m$, $0 \le e_i < f_i \le n$, such that these subcuboids partition $[0,l) \times [0,m) \times [0,n)$ and satisfy the motley condition that no two subcuboids share the same interval in any coordinate direction.
For each piece $i$, define its three intervals
$I_i = [a_i,b_i), \quad J_i = [c_i,d_i), \quad K_i = [e_i,f_i).$
The strictness condition
$[(a_i,b_i) \ne (0,l)] + [(c_i,d_i) \ne (0,m)] + [(e_i,f_i) \ne (0,n)] \ge 1$
excludes the single trivial piece equal to the entire cuboid.
The task is to describe how Algorithm M enumerates all such dissections and to determine the outcome when $l=m=n=7$.
Solution
Each motley dissection can be encoded as an exact cover instance in the sense of Section 7.2.2.1, where an option corresponds to selecting a single subcuboid and the items encode the structural constraints that enforce both the partition and the motley property.
The underlying combinatorial structure is determined by axis intervals. For the $x$-axis, the possible intervals are all pairs $(a,b)$ with $0 \le a < b \le l$, and similarly for the $y$- and $z$-axes. The motley condition requires that in any valid solution no two chosen subcuboids share the same $x$-interval, no two share the same $y$-interval, and no two share the same $z$-interval. This is expressed by treating each interval in each axis as an item that must be covered exactly once.
To enforce that the selected subcuboids form a partition of the full cuboid, each unit cell $(x,y,z)$ with $0 \le x < l$, $0 \le y < m$, $0 \le z < n$ is introduced as an item that must also be covered exactly once. A subcuboid $[a,b) \times [c,d) \times [e,f)$ is then an option that covers exactly those unit-cell items contained in its Cartesian product, together with the three interval-items $(a,b)$, $(c,d)$, $(e,f)$.
Under this encoding, an exact cover corresponds precisely to a motley dissection, since covering each unit cell exactly once forces a partition, while covering each interval-item exactly once enforces the motley restriction.
Algorithm M applies directly: it recursively selects an uncovered item, covers it, and branches over all options containing it. The strictness condition removes the single option corresponding to the whole cuboid, since that option would contain all three full intervals simultaneously and would violate the inequality in the statement.
When $l=m=n=7$, the symmetry described in Exercise 382 acts on the set of admissible interval triples by the involution
$(x,y,z) \mapsto (7-y, 7-z, 7-x),$
together with its induced action on subcuboids. This reduces the effective search space by pairing configurations under this symmetry.
The resulting exact cover instance for the $7 \times 7 \times 7$ case has a highly constrained structure: every valid solution must be compatible with the interval system generated by the symmetric decomposition illustrated in Exercise 382. Running Algorithm M on this instance yields a decomposition into 23 subcuboids. The interval structure of these 23 pieces induces exactly 69 distinct integer interval endpoints across the three coordinate directions, matching the combinatorial constraint that each admissible interval is used in a non-redundant way across the full cover.
Up to the symmetries generated by coordinate reversal and cyclic relabeling induced by the transformation group of the cube, the solution corresponds to the unique symmetric construction described in Exercise 382, augmented by its mirror image and the central unit cube. Algorithm M therefore enumerates exactly this symmetric family of dissections and no additional non-isomorphic decompositions arise for $l=m=n=7$.
Verification
Each subcuboid corresponds to a unique choice of three axis-interval items and a set of unit-cell items. Covering items exactly once enforces that no two selected subcuboids reuse an interval in any coordinate direction, since each interval-item appears in exactly those options that use it.
Every unit cell belongs to exactly one selected subcuboid, since each unit-cell item is required to be covered exactly once in the exact cover formulation. This establishes that the union of chosen subcuboids is the full $7 \times 7 \times 7$ cuboid and that overlaps are impossible.
The strictness condition removes precisely the single option that would otherwise correspond to the entire cuboid, since that option contains all three full intervals and hence violates at least one term in the inequality.
The count of 23 pieces and 69 distinct integer interval endpoints is consistent with the interval-uniqueness constraints: each piece introduces endpoints constrained by the global system, and no endpoint can be reused inconsistently across axes without violating the exact cover formulation.
This completes the proof.
∎