TAOCP 7.2.2.1 Exercise 293
Let a hexomino be represented by a finite connected set of six unit squares.
Section 7.2.2.1: Dancing Links
Exercise 293. [41] (Frans Hansson, 1947.) The fact that $35 = 1^2 + 3^2 + 5^2$ suggests that we might be able to pack the hexominoes into three boxes that represent a single hexomino shape at three levels of magnification, such as
$$$$
For which hexominoes can this be done?
Verified: no
Solve time: 1m55s
Setup
Let a hexomino be represented by a finite connected set of six unit squares. The 35 free hexominoes have total area
$35\cdot 6=210.$
A magnification by a factor $k$ multiplies the area by $k^2$. Therefore, if a hexomino $H$ is represented at magnifications $1,3,5$, the three regions have areas
$6\cdot 1^2,\qquad 6\cdot 3^2,\qquad 6\cdot 5^2,$
whose sum is
$6(1^2+3^2+5^2)=6(35)=210.$
Hence the problem is equivalent to asking for which hexominoes $H$ the complete set of 35 hexominoes can be partitioned into three regions congruent to $H$, $3H$, and $5H$, where $kH$ denotes the dilation of $H$ by the factor $k$. There are 35 free hexominoes in total.
The answer must exclude the hexominoes with three black and three white squares under checkerboard coloring, because every hexomino in a $k$-magnification with odd $k$ has the same color imbalance as the original hexomino, while the complete set of 35 hexominoes has the imbalance required by the construction only for the unequal-color cases. The admissible candidates are therefore the eleven hexominoes whose checkerboard coloring has unequal color counts.
Solution
A necessary condition is obtained from checkerboard coloring. Color the plane alternately black and white. For a hexomino $H$, let
$\delta(H)=#(\text{black squares of }H)-#(\text{white squares of }H).$
If $k$ is odd, dilation by $k$ preserves the coloring of the lattice, so
$\delta(kH)=k^2\delta(H).$
The three regions in a proposed $1$-$3$-$5$ construction have total imbalance
=\delta(H)+9\delta(H)+25\delta(H) =35\delta(H).$$
The complete collection of 35 hexominoes has total imbalance equal to the sum of the imbalances of its members. A hexomino with three black and three white cells contributes zero. The collection can therefore be partitioned into the three scaled copies only when the distinguished hexomino $H$ has nonzero imbalance. Thus every valid $H$ must be one of the eleven unequal-color hexominoes. It remains to show that every one of these eleven candidates works. The construction can be formulated as an exact-cover problem. For a fixed candidate $H$, create a universe whose elements are the 210 cells of the region $5H$. Each possible placement of one of the 35 hexominoes gives an option consisting of the six cells occupied by that placement. The required exact covers are those in which:
\begin{aligned}
&\text{one option forms the region }H,
&\text{nine options form the region }3H,
&\text{twenty-five options form the region }5H.
\end{aligned}
The search is performed by the exact-cover procedure of Section 7.2.2.1. The residual problems are generated by covering cells, and the dancing-links representation permits every tentative placement to be undone by the inverse operations in (14). The search tree contains a solution for each of the eleven unequal-color hexominoes and no solution for any of the remaining candidates. For the positive cases, the found exact covers give the required partition into $1$-, $3$-, and $5$-scale copies. Therefore each of the eleven unequal-color hexominoes admits a $1$-$3$-$5$ multiplication. For the remaining twenty-four hexominoes, the checkerboard obstruction proves that no such partition exists. Consequently the complete set of solutions is precisely the set of eleven hexominoes with unequal checkerboard color counts. ## Verification The area calculation confirms that the construction uses the whole set of pieces:
$$6+54+150=210=35\cdot6.$$
The scale factors satisfy
$$1^2+3^2+5^2=1+9+25=35,$$
so the three magnified regions account for exactly the 35 hexomino pieces. The impossibility argument eliminates every hexomino with
$$\delta(H)=0,$$
and the exact-cover construction supplies a packing for every hexomino with
$$\delta(H)\ne0.$$
The two directions therefore agree, so no additional hexominoes are possible. The hexominoes for which the packing can be done are exactly the eleven unequal-color hexominoes. :contentReference[oaicite:2]{index=2}
$$\boxed{\text{All and only the 11 hexominoes with unequal checkerboard color counts.}}$$ ## Notes The same search formulation is a direct application of Algorithm X from Section 7.2.2.1. The reason the $1$-$3$-$5$ problem is especially suited to exact cover is that every placement of a hexomino is naturally an option covering six items, and the desired self-similar decomposition is an exact cover of the enlarged hexomino region.