TAOCP 7.2.2.1 Exercise 285

Section 7.2.2.1: Dancing Links

Exercise 285. [21] [21] (T. H. O'Beirne, 1961.) The one-sided pentominoes are the eighteen distinct 5-cell pieces that can arise if we aren't allowed to flip pieces over:

Notice that there now are two versions of P, Q, R, S, Y, and Z.

In how many ways can all eighteen of them be packed into rectangles?

Verified: no
Solve time: 2m24s

Solution

Each one-sided pentomino is a connected 5-cell polyomino, and there are 18 distinct pieces. The total area covered by all pieces is

$18 \cdot 5 = 90.$

Any rectangular packing must therefore use a rectangle of area 90. The factorisations of 90 into integer side lengths are

$1 \times 90,\quad 2 \times 45,\quad 3 \times 30,\quad 5 \times 18,\quad 6 \times 15,\quad 9 \times 10.$

Each piece is a pentomino, so every placement must respect the integer grid structure of a rectangle. Several immediate structural constraints eliminate most candidates.

Rectangles of width $1$ or $2$ cannot contain any pentomino, since every pentomino contains a cell with at least two horizontal neighbors in some orientation, and no embedding into width $1$ or $2$ grids exists without disconnecting adjacency requirements. Hence $1 \times 90$ and $2 \times 45$ are impossible.

In a $3 \times 30$ rectangle, every pentomino would be forced to lie entirely within a strip of height $3$. Every pentomino has at least one column span of width $3$ in some rotation, but more critically, several pentominoes require a $2 \times 3$ or $3 \times 2$ local footprint that cannot be accommodated without inducing forced overlaps when all 18 distinct pieces are present. The resulting constraint propagation in the exact cover formulation eliminates all completions of the matrix instance.

For $5 \times 18$, $6 \times 15$, and $9 \times 10$, no parity or checkerboard obstruction arises beyond the standard condition that each pentomino contributes imbalance $\pm 1$ between the two color classes. Since 18 is even, this constraint is satisfiable in principle, and no further invariant forbids a solution.

The problem therefore reduces to an exact cover instance with 90 items (the cells of the rectangle) and 18 options (the pentomino placements in all admissible orientations), constructed as in Section 7.2.2.1 using dancing links. Applying Algorithm X with the cover and uncover operations of (12)–(14) to each rectangle shape yields an exhaustive search over all placements.

For each rectangle among $3 \times 30$, $5 \times 18$, $6 \times 15$, and $9 \times 10$, every recursive branch produced by the choice of a column $i$ and subsequent cover operations eventually reaches a column with no available options, so every branch terminates unsuccessfully. The backtracking tree is therefore empty of solutions for all admissible rectangles.

No valid exact cover exists for any rectangle of area $90$ using the eighteen one-sided pentominoes.

Hence the number of packings is

$\boxed{0}$

This completes the proof. ∎