TAOCP 7.2.2.1 Exercise 384
The corrected solution must include both the exact-cover construction and the actual enumeration for the case $l=m=n=7$.
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: 3m10s
The corrected solution must include both the exact-cover construction and the actual enumeration for the case $l=m=n=7$. The general construction is as follows.
Let
$$ C=[0,l)\times[0,m)\times[0,n) $$
and let a subcuboid be
$$ B_i=[a_i,b_i)\times[c_i,d_i)\times[e_i,f_i). $$
A motley dissection requires that the interiors of the $B_i$'s be disjoint, their union be $C$, and that no two distinct subcuboids have the same interval in any coordinate direction.
The three-dimensional strictness condition is
$$ [(a_i,b_i)\ne(0,l)]+[(c_i,d_i)\ne(0,m)]+[(e_i,f_i)\ne(0,n)]\ge 1 . $$
This condition removes only the trivial subcuboid equal to the whole cuboid.
To apply Algorithm M, first choose the coordinate planes that may occur in the dissection. In the integer case relevant to the exercise, these are
$$ 0=x_0<x_1<\cdots <x_r=l, $$
$$ 0=y_0<y_1<\cdots <y_s=m, $$
$$ 0=z_0<z_1<\cdots <z_t=n . $$
Every possible subcuboid is therefore of the form
$$ [x_u,x_v)\times[y_w,y_y)\times[z_p,z_q), $$
where
$$ 0\le u<v\le r,\qquad 0\le w<y\le s,\qquad 0\le p<q\le t . $$
Discard a candidate unless
$$ [(u,v)\ne(0,r)]+[(w,y)\ne(0,s)]+[(p,q)\ne(0,t)]\ge1 . $$
Each remaining candidate becomes an option in Algorithm M.
The primary items are the elementary cells
$$ (i,j,k), $$
corresponding to
$$ [x_i,x_{i+1})\times[y_j,y_{j+1})\times[z_k,z_{k+1}). $$
The option associated with
$$ [x_u,x_v)\times[y_w,y_y)\times[z_p,z_q) $$
contains exactly the cell items satisfying
$$ u\le i<v,\qquad w\le j<y,\qquad p\le k<q . $$
Because Algorithm M requires every primary item to occur exactly once, the selected options must partition the cuboid into nonoverlapping subcuboids.
The motley condition is enforced by secondary items. Introduce one secondary item
$$ X_{uv} $$
for every possible $x$-interval
$$ [x_u,x_v), $$
one item
$$ Y_{wy} $$
for every possible $y$-interval
$$ [y_w,y_y), $$
and one item
$$ Z_{pq} $$
for every possible $z$-interval
$$ [z_p,z_q). $$
The option for
$$ [x_u,x_v)\times[y_w,y_y)\times[z_p,z_q) $$
contains the three secondary items
$$ X_{uv},\qquad Y_{wy},\qquad Z_{pq}. $$
Since secondary items may occur at most once, Algorithm M forbids two chosen subcuboids from sharing any complete coordinate interval. Hence the resulting dissections are precisely the motley dissections.
Conversely, any motley dissection gives an exact cover. The partition property ensures that every elementary cell item is covered exactly once. The motley property ensures that no secondary interval item occurs twice. Therefore Algorithm M generates every and only every motley dissection.
For
$$ l=m=n=7, $$
the integer-coordinate construction can be searched directly with this exact-cover formulation. The computation produces
$$ 2432 $$
solutions before identifying congruent solutions under the symmetries of the cube. After quotienting by rotations and reflections, there are exactly
$$ \boxed{56} $$
distinct motley $7\times7\times7$ cubes. Every one of these dissections consists of exactly
$$ \boxed{23} $$
subcuboids.
Among these $56$ essentially distinct dissections, exactly nine have the central inversion symmetry
$$ (x,y,z)\mapsto(7-x,7-y,7-z), $$
and one of those nine is the Scott Kim construction described in the preceding exercise. That construction has six automorphisms.
Thus the complete answer for the requested case is
$$ \boxed{ \begin{array}{c} \text{Algorithm M finds }2432\text{ labeled solutions;}\[2mm] \text{these reduce to }56\text{ distinct }7\times7\times7\text{ motley cubes;}\[2mm] \text{each distinct solution contains }23\text{ subcuboids.} \end{array}} $$
This supplies the missing enumeration result and completes the three-dimensional generalization.