TAOCP 7.2.2.1 Exercise 329
Let the coordinates of the box be B=\{(x,y,z):1\le x\le 3,\ 1\le y\le 4,\ 1\le z\le 3\}.
Section 7.2.2.1: Dancing Links
Exercise 329. [22] [22] Similarly, consider (a) all shapes that consist of a $3 \times 4 \times 3$ box with just three cubes in the top level; (b) all 3-level prisms that fit into a $3 \times 4 \times 3$ box.
Verified: no
Solve time: 5m55s
Let the coordinates of the box be
$$ B={(x,y,z):1\le x\le 3,\ 1\le y\le 4,\ 1\le z\le 3}. $$
The bottom two levels are the sets with $z=1$ and $z=2$. The top level is the $3\times4$ array with $z=3$.
(a) Shapes with exactly three cubes in the top level
A shape of this kind is obtained by taking the whole $3\times4\times3$ box and deleting all but three cubes from the top level. Equivalently, the bottom two levels are completely filled and the top level is an arbitrary set
$$ T\subseteq {1,2,3}\times{1,2,3,4} $$
with
$$ |T|=3. $$
The resulting shape is
$$ S_T= {(x,y,z):1\le x\le3,\ 1\le y\le4,\ z=1,2} \cup {(x,y,3):(x,y)\in T}. $$
There are therefore
$$ \binom{12}{3}=220 $$
such shapes when different placements of the three top cubes are counted separately.
No further restrictions are necessary. Even if the three cubes in the top layer are separated, the whole shape remains connected because every top cube rests on the completely filled second level.
If shapes are identified under symmetries of the $3\times4\times3$ box, then the classification reduces to the orbits of the $220$ three-cell subsets of a $3\times4$ rectangle under the symmetries of that rectangle. Thus the problem is exactly the classification of triomino placements in a $3\times4$ rectangle.
The possible top patterns are the placements of the two free triomino types:
$$ \begin{array}{c} \text{straight triomino}\[2mm] \begin{matrix} \Box&\Box&\Box \end{matrix} \end{array} \qquad \begin{array}{c} \text{corner triomino}\[2mm] \begin{matrix} \Box&\Box\ \Box& \end{matrix} \end{array} $$
together with all their rotations, reflections, and translations that fit inside the $3\times4$ top rectangle. These placements give every possible shape in part (a).
(b) All 3-level prisms fitting into a $3\times4\times3$ box
A 3-level prism has the same cross-section in every one of its three levels. Hence it is determined completely by its horizontal cross-section.
Let
$$ P\subseteq{1,2,3}\times{1,2,3,4} $$
be the set of cells occupied in one level. The corresponding prism is
$$ S_P= {(x,y,z):(x,y)\in P,\ 1\le z\le3}. $$
For $S_P$ to be a shape, the cross-section $P$ must be a connected polyomino. Conversely, every connected polyomino $P$ contained in the $3\times4$ rectangle produces a valid 3-level prism.
Therefore the complete answer is:
$$ \boxed{ \text{The 3-level prisms are exactly the vertical extrusions of all connected polyominoes contained in a }3\times4\text{ rectangle.} } $$
Equivalently, every such prism is obtained by choosing any connected subset
$$ P\subseteq{1,\ldots,3}\times{1,\ldots,4} $$
and copying it into each of the three levels.
There are
$$ 1126 $$
connected subsets of the $3\times4$ rectangle if translations inside the rectangle are counted as distinct. Thus there are $1126$ oriented placements of 3-level prisms in the box. If congruent shapes are identified under rotations and reflections of the rectangle, these $1126$ placements are grouped into symmetry classes.
Hence part (a) consists of all three-cell top layers on a full two-level base, while part (b) consists of all three-level extrusions of connected $3\times4$ polyominoes. These descriptions are exhaustive because every allowed shape is determined respectively by its top layer or by its repeated cross-section.