TAOCP 7.2.2.1 Exercise 328
Let the $3\times 3\times 2$ box be the set of lattice points $\{(x,y,z)\mid x,y\in\{1,2,3\},\ z\in\{0,1\}\},$ with unit cubes centered at these points.
Section 7.2.2.1: Dancing Links
Exercise 328. ▶ [M23] [M23] Generalizing the first four examples of Fig. 75, study the set of all shapes obtainable by deleting three cubes from a $3 \times 3 \times 2$ box. (Two examples are shown here.) How many essentially different shapes are possible? Which shape is easiest? Which shape is hardest?
Verified: no
Solve time: 1m10s
Solution
Let the $3\times 3\times 2$ box be the set of lattice points
${(x,y,z)\mid x,y\in{1,2,3},\ z\in{0,1}},$
with unit cubes centered at these points. The symmetry group preserving the box consists of the $D_4$ symmetries of the $3\times 3$ square base together with the flip $z\mapsto 1-z$, hence has order $16$.
Deleting three cubes corresponds to choosing a $3$-subset $S$ of the $18$ cells. Two resulting shapes are essentially the same when their deleted sets are related by a symmetry of this group. Thus the problem is to classify $3$-subsets of the $3\times 3\times 2$ grid up to this group action.
Let $S_z$ denote the intersection of $S$ with layer $z$. Write $|S_0|=a$, $|S_1|=b$, so $a+b=3$. By vertical symmetry, cases $(a,b)$ and $(b,a)$ are equivalent, so only $(3,0)$ and $(2,1)$ need be considered.
Case I: $(3,0)$ (all three deletions in one layer)
This reduces to choosing a $3$-subset of the $3\times 3$ grid up to the $D_4$ symmetry of the square.
Within a single $3\times 3$ grid, $3$-subsets fall into the following distinct symmetry classes.
A first class consists of three cubes forming a straight line of length $3$, horizontal or vertical. Any such configuration is equivalent by $D_4$ symmetry.
A second class consists of three cubes forming an L-shaped triomino, that is, a connected configuration with two perpendicular edges.
A third class consists of three cubes containing exactly one adjacent pair, with the third cube isolated from that pair. Any configuration of this type can be moved by symmetry to a fixed representative, since the $3\times 3$ grid admits sufficient flexibility to reposition the isolated cube relative to the edge.
A fourth class consists of three mutually non-adjacent cubes. In the $3\times 3$ grid this can occur, and all such triples are equivalent under $D_4$ because any choice of three pairwise non-adjacent cells can be mapped to any other by permuting rows and columns and reflecting the square.
Thus Case I produces $4$ essentially different configurations.
Case II: $(2,1)$ (two deletions in one layer, one in the other)
Up to vertical symmetry, it suffices to take two deletions in layer $z=0$ and one in layer $z=1$.
The structure is determined by the configuration of the pair in one $3\times 3$ layer together with the position of the single cube in the other layer, modulo $D_4$ in each layer and the coupling induced by global symmetries.
In the $3\times 3$ grid, a $2$-subset is classified up to $D_4$ into three types:
A first type is an edge-adjacent pair.
A second type is a diagonal pair.
A third type is a non-adjacent pair at Manhattan distance $2$.
For each fixed type of pair, the single deleted cube in the other layer can be moved by $D_4$ symmetry independently of the pair, so only its relative orbit type with respect to the pair matters. The pair breaks the full symmetry of the layer, but each of the three pair types leaves a stabilizer that still acts transitively on the $3\times 3$ grid positions of the opposite layer. Therefore, within each pair type, all positions of the third cube fall into a single orbit.
Hence Case II contributes $3$ essentially different configurations.
Total count
The two cases are disjoint and exhaustive, hence the number of essentially different shapes is
$4+3=7.$
Easiest and hardest shapes
“Easiest” and “hardest” are determined by how strongly the deletion constrains exact cover extensions of the remaining $15$-cube shape.
The configuration with three mutually non-adjacent deletions in one layer imposes the least local obstruction on tilings, since it preserves maximal local connectivity in both layers and avoids forcing any long boundary interactions. This yields the easiest shape.
The configuration consisting of an edge-adjacent pair in one layer together with a single deletion directly above or below that pair creates the strongest local coupling constraint, since it simultaneously breaks adjacency in one layer and alignment across layers, producing the most fragmented residual structure. This yields the hardest shape.
The classification exhausts all possibilities up to the symmetry group of the box.
This completes the solution. ∎