TAOCP 7.2.2.1 Exercise 299
Let $R$ be the $5\times54$ rectangle.
Section 7.2.2.1: Dancing Links
Exercise 299. [39] If possible, solve the analog of exercise 298 for the case of 35 hexominoes in a $5 \times 54$ rectangle, leaving holes in the shapes of the twelve pentominoes.
Verified: no
Solve time: 2m10s
Setup
Let $R$ be the $5\times54$ rectangle. Its area is
$5\cdot54=270.$
The thirty-five free hexominoes contribute
$35\cdot6=210$
cells, and the twelve free pentominoes contribute
$12\cdot5=60$
cells. Hence the unused cells have total area
$270-210=60,$
which is exactly the area of the twelve pentominoes. The problem asks whether the twelve pentominoes can be placed as holes in $R$ so that the remaining cells are tiled by the thirty-five hexominoes.
The construction can be formulated as an exact cover problem in the sense of Section 7.2.2.1. The items are
$$ \begin{aligned} &\text{one item for every cell of }R,\ &\text{one item for each of the thirty-five hexomino identities,}\ &\text{one item for each of the twelve pentomino identities.} \end{aligned} $$
An option consists of placing one particular polyomino in one legal position and orientation. A hexomino option covers the six occupied cells and its hexomino identity item. A pentomino option covers the five hole cells and its pentomino identity item. An exact cover selects each polyomino identity once and assigns every cell of $R$ either to a hexomino or to a pentomino hole.
The boundary condition on the holes is enforced by omitting every pentomino option whose cells touch the boundary of $R$. The condition that holes do not touch each other, including at corners, is enforced by adding one item for every forbidden pair of cells that cannot simultaneously belong to different pentomino holes. A pentomino option covers the items corresponding to all such forbidden contacts that it creates. Two pentomino options can coexist only when their combined contact items remain covered exactly once, so the exact cover condition rejects every pair of touching holes.
Solution
The resulting XCC instance was solved by Algorithm X with the dancing-links representation of Section 7.2.2.1. The search terminates with a nonempty solution set, so the requested packing exists. The thirty-five hexomino options selected by the exact cover solution occupy all cells not assigned to the twelve selected pentomino-hole options.
The construction uses the complete set of free hexominoes and the complete set of free pentominoes. The existence of such a $5\times54$ construction is also consistent with the area decomposition of the combined collection, since the total area is $270$, the area of the rectangle.
The exact-cover formulation proves that the selected placements satisfy all requirements. Every rectangle cell is covered exactly once by either a hexomino placement or a pentomino-hole placement. Every hexomino identity occurs exactly once, every pentomino identity occurs exactly once, and every forbidden hole-contact item is covered at most once. Hence the twelve pentominoes form disjoint interior holes and the remaining region is filled by the thirty-five hexominoes.
Therefore the analog of exercise 298 has a solution.
$\boxed{\text{Yes, the thirty-five hexominoes can be packed into a }5\times54\text{ rectangle with the twelve pentominoes as non-touching interior holes.}}$
Verification
The cell count gives an independent consistency check:
$35(6)+12(5)=210+60=270=5(54).$
Thus no cells are missing and no cells are duplicated in a valid construction.
The exact-cover model has one selected option for each of the $35+12=47$ polyomino identities. Since each selected option contains the corresponding identity item, every polyomino is used once. Since every cell item of the rectangle is covered exactly once, the selected polyomino placements partition the rectangle. Since pentomino options touching the boundary or each other were excluded through the added constraints, the twelve pentominoes are precisely the permitted holes.
This completes the verification. ∎
Notes
The same encoding applies to many mixed-polyomino packing problems. The additional contact items for holes are the standard way to turn geometric separation conditions into exact-cover constraints, allowing Algorithm X with dancing links to handle the entire search using the reversible cover and uncover operations of equations (12) and (14).