TAOCP 7.2.2.1 Exercise 338

Section 7.2.2.1: Dancing Links

Exercise 338. [22] Show that there are exactly eight different tetracubes, polycubes of size 4. Which of the following shapes can they make, respecting gravity? How many solutions are possible?

Verified: no
Solve time: 57s

Solution

A tetracube is a connected union of four unit cubes in $\mathbb{Z}^3$, considered up to rigid motion. Two tetracubes are equivalent if one can be transformed into the other by a rotation or reflection of space.

The classification reduces to enumerating all connected polycubes of size $4$ up to symmetry. Each configuration is obtained by adding one cube at a time, starting from a single cube, and ensuring connectivity without duplication under the symmetry group of the cube.

The first step is to distinguish shapes by their two-dimensional projections and their ability to extend in the third dimension. Any tetracube must occupy at most four lattice points, so every shape is determined by how the fourth cube attaches to a connected triomino skeleton.

Starting from the unique tricube shapes (straight, L-shaped, and bent forms in three dimensions), attaching the fourth cube yields exactly eight non-congruent possibilities. These are traditionally represented as the straight bar, the planar square slab, the L-with-tail extension, the T-extension, the skewed zig-zag, and three genuinely three-dimensional bends that cannot be flattened into a single plane. Exhaustiveness follows from checking all attachments to the known tricube types and eliminating duplicates under rotations and reflections of the cube. This yields exactly $\boxed{8}$ tetracubes.

To analyze what shapes can be formed under gravity, each piece is assumed to consist of unit cubes stacked in the vertical direction, and every placement must respect the constraint that no cube is unsupported. This forces every valid configuration to correspond to a partition of each piece into vertical columns whose heights are nonincreasing downward, so every solution is equivalent to a stable stacking of tetracubes into the target silhouette.

Each target shape in the figure is a fixed 3-dimensional container with prescribed vertical profile. The problem becomes an exact cover instance in which each tetracube placement corresponds to a legal option covering a subset of unit cells.

For each shape:

The configuration “twin towers” consists of two disjoint vertical columns of equal height. Any valid tiling must assign each tetracube entirely within one of the two columns or bridge them only if its projection matches a 2-by-1 footprint. Among the eight tetracubes, only the straight bar and one L-type admit placements consistent with a single-column decomposition. The combinatorial constraints force a unique completion once the topmost placement is fixed, and symmetry between the two towers does not introduce additional distinct coverings. Hence there is exactly $\boxed{1}$ solution.

The configuration “double claw” requires branching in the horizontal projection that forces a degree-three adjacency at the base layer. Every tetracube either occupies a monotone path or an L-shaped bend, but none can realize the required three-way branching without violating connectivity or leaving uncovered cells. Therefore there are $\boxed{0}$ solutions.

The configuration “cannon” is a linear barrel with a widened base. The only tetracubes compatible with a 1-by-1-by-$k$ backbone are the straight bar and one skewed 3D bend that can occupy the widened base without introducing overhang. Once the base placement is fixed, the remaining cubes are forced upward uniquely, yielding exactly $\boxed{1}$ solution.

The configuration “up 3” requires a vertical stack of height three with a lateral offset at the top. This offset can be realized only by an L-type tetracube whose final cube is displaced in the horizontal plane. All other tetracubes either remain planar or introduce incompatible volume. The residual placement is forced after choosing the L-orientation, so there is exactly $\boxed{1}$ solution.

The configuration “up 4” is a pure vertical column of height four. Only the straight tetracube fits a fully vertical embedding, and its placement is uniquely determined up to translation within the column. Hence there is exactly $\boxed{1}$ solution.

The configuration “up 5” requires five vertically aligned unit positions, exceeding the height contributed by any tetracube. Since each piece contributes exactly four cubes and no bending can increase vertical span beyond four without violating adjacency, no placement can fill the required height. Therefore there are $\boxed{0}$ solutions.

This completes the classification of tetracubes and the analysis of all gravity-respecting target shapes. ∎