TAOCP 7.2.2.1 Exercise 324
We recompute the number of base placements using the orbit–stabilizer theorem under the action of the proper rotation group of the cube, which has order $24$.
Section 7.2.2.1: Dancing Links
Exercise 324. ▶ [30] [30] Extend exercise 206 to three dimensions. How many base placements do each of the seven Soma pieces have?
Verified: yes
Solve time: 2m34s
We recompute the number of base placements using the orbit–stabilizer theorem under the action of the proper rotation group of the cube, which has order $24$.
A base placement of a polycube $P$ is an orbit of $P$ under this group. Hence
$$ #\text{base placements}(P)=\frac{24}{|\mathrm{Stab}(P)|}. $$
We determine $|\mathrm{Stab}(P)|$ for each Soma piece.
1. Tricube $V$
The tricube $V$ consists of three unit cubes placed at
$$ (0,0,0),\ (1,0,0),\ (0,1,0),\ (0,0,1), $$
so that from the origin there are three mutually perpendicular arms of length $1$ along the positive coordinate axes.
Any proper rotation preserving $V$ must permute these three axis-aligned unit segments. Thus, it induces a permutation of the coordinate axes ${x,y,z}$.
All such permutations that arise from proper rotations correspond to the even permutations of the axes, i.e., the rotational symmetries of a cube that preserve orientation. These form a subgroup isomorphic to $A_4$, but only the subgroup fixing the set of three coordinate axes as unordered directions from the origin is relevant here.
In this configuration, the tricube is completely determined by the unordered set of the three coordinate directions, and any cyclic permutation of the axes preserves the piece.
Concretely, the rotation
$$ x \mapsto y,\quad y \mapsto z,\quad z \mapsto x $$
is a $120^\circ$ rotation about the body diagonal $(1,1,1)$, and it maps the tricube to itself. Its square gives the second nontrivial symmetry:
$$ (x,y,z)\mapsto (z,x,y). $$
Thus the stabilizer contains exactly the cyclic group of order $3$.
No rotation of order $2$ preserves the ordered incidence structure of the three arms, since any such rotation would reverse orientation on at least one axis direction, producing a different embedding of the piece.
Hence
$$ |\mathrm{Stab}(V)| = 3, \qquad #\text{placements}(V)=\frac{24}{3}=8. $$
2. Planar tetracubes $L, T, Z$
Each of these pieces lies in a coordinate plane and forms a planar tetromino embedded in $\mathbb{R}^3$.
Each has exactly one nontrivial proper rotational symmetry: a half-turn ($\pi$-rotation) about the axis perpendicular to its supporting plane through its center. This maps the piece to itself by exchanging symmetric unit cubes.
There are no additional symmetries:
- A $90^\circ$ rotation in the plane does not preserve adjacency.
- Any rotation moving the supporting plane out of itself changes the set of occupied lattice points.
Therefore,
$$ |\mathrm{Stab}(P)| = 2,\quad P \in {L,T,Z}, $$
and hence
$$ #\text{placements}(P)=\frac{24}{2}=12. $$
3. Skew tetracubes $A, B, C$
Each of these pieces is nonplanar and lacks any geometric symmetry that preserves adjacency of all four cubes.
Any nontrivial proper rotation of the cube necessarily moves at least one unit cube of the piece to a position not occupied by the original configuration, since:
- there is no axis aligning the structure with a rotational symmetry,
- and no permutation of cube positions preserves the full adjacency graph.
Thus the only symmetry is the identity:
$$ |\mathrm{Stab}(P)| = 1,\quad P \in {A,B,C}. $$
Hence
$$ #\text{placements}(P)=\frac{24}{1}=24. $$
Final result
$$ \begin{aligned} V &: 8,\ L &: 12,\ T &: 12,\ Z &: 12,\ A &: 24,\ B &: 24,\ C &: 24. \end{aligned} $$
Conclusion
The only correction required is for the tricube $V$, whose stabilizer is the cyclic group of order $3$ generated by $120^\circ$ rotations about the body diagonal. All other Soma pieces retain their previously computed stabilizers.