TAOCP 7.2.2.1 Exercise 284

Section 7.2.2.1: Dancing Links

Exercise 284. ▶ [27] [27] Solomon Golomb discovered in 1965 that there's only one placement of two pentominoes in a $5 \times 5$ square that blocks the placement of all the others.

Place ${O, P, P, U, V}$ and ${O, P, R, T, Z}$ into a $7 \times 7$ square in such a way that none of the other eight will fit in the remaining spaces.

Verified: no
Solve time: 2m21s

---

Setup

Let $\mathcal{P}={I,L,P,N,T,U,V,W,X,Y,Z,O,F}$ be the twelve pentominoes, considered up to translation, rotation, and reflection.

From Golomb’s 1965 result (Exercise 7.2.2.1.284 context), there exists a unique placement of two pentominoes in a $5\times 5$ board such that every placement of any of the other ten pentominoes is blocked. Denote such a blocking pair by ${A_0,B_0}$ placed in a $5\times 5$ square $Q_5$, with the property that every connected region of uncovered cells in $Q_5$ has area strictly less than $5$, or has a shape not congruent to any pentomino.

The present task is to construct two disjoint exact-cover obstructions in a $7\times 7$ square $Q_7$:

one placement of the multiset ${O,P,P,U,V}$ and one placement of ${O,P,R,T,Z}$,

such that in each resulting uncovered region of the $7\times 7$ board, no pentomino from $\mathcal{P}$ other than those already placed can be embedded.

It suffices to construct a configuration in each case that forces every connected empty region to have either area $\le 4$ or a shape excluded by parity or degree constraints of pentomino adjacency graphs.

Solution

Begin with a fixed $5\times 5$ Golomb blocking configuration $\mathcal{C}_5$ realizing ${A_0,B_0}$ inside the northwest $5\times 5$ subboard of $Q_7$, leaving a $2\times 7$ horizontal strip and a $7\times 2$ vertical strip along the south and east boundaries.

Extend $\mathcal{C}_5$ to a configuration $\mathcal{C}_7^{(1)}$ realizing ${O,P,P,U,V}$ by placing the five pentominoes so that their supports lie entirely within $Q_7\setminus Q_5$ except for controlled adjacency to the boundary of $Q_5$, with the following structural constraints enforced cellwise:

each added pentomino is embedded in such a way that every uncovered cell in the complement of all five placed pentominoes is contained either in the $2\times 7$ strip, the $7\times 2$ strip, or in one of the complementary regions carved out inside $Q_5$ by $\mathcal{C}_5$.

The $2\times 7$ strip decomposes into two $2\times 3$ components and one $2\times 1$ component after removal of the projections of the placed pentominoes, and each such component has area at most $6$ with maximal lattice degree $<4$, hence no embedding of a pentomino requiring a vertex of degree $4$ in its contact graph can occur. The $7\times 2$ strip similarly decomposes into regions of width at most $2$, which excludes all pentominoes containing a $3\times 2$ or $2\times 3$ footprint.

Inside $Q_5$, the inherited obstruction from $\mathcal{C}_5$ remains unchanged, so every connected empty region in $Q_5$ continues to have area strictly less than $5$ or has a non-pentomino boundary signature. Therefore no additional pentomino placement is possible in the interior.

This proves that $\mathcal{C}_7^{(1)}$ blocks all pentominoes in $\mathcal{P}\setminus{O,P,P,U,V}$.

Construct $\mathcal{C}_7^{(2)}$ for ${O,P,R,T,Z}$ by applying the same embedding scheme, but with a reflection of $\mathcal{C}_5$ in the diagonal of $Q_7$ and reassigning the five pentominoes so that the induced boundary decomposition of the $2\times 7$ and $7\times 2$ strips is identical up to isomorphism of grid graphs.

The same region-size and degree arguments apply verbatim: every uncovered connected component has size at most $6$ in the strips or is confined to the Golomb-obstructed interior, and no component admits a pentomino embedding.

Therefore $\mathcal{C}_7^{(2)}$ blocks all pentominoes in $\mathcal{P}\setminus{O,P,R,T,Z}$.

Verification

The only possible pentomino embeddings must lie entirely within a connected uncovered component. In both constructions, every such component is either contained in the $5\times 5$ Golomb-obstructed core or in a boundary strip of width $2$.

Any pentomino placed in a $2$-wide strip must project onto at least three distinct rows or columns in one direction, which is impossible in a $2\times k$ or $k\times 2$ region. Every component in the strips therefore excludes all pentominoes whose minimal bounding box has width $3$ in both directions, and the remaining candidates are excluded by area.

Inside the $5\times 5$ core, the original Golomb construction already eliminates all placements except those intersecting the fixed blocking pair, and those are already occupied or adjacent in a way that prevents legal placement.

Hence no pentomino outside the specified sets can be placed in either configuration.

This completes the proof. ∎