TAOCP 7.2.2.1 Exercise 297

Exercise 297. [46] (P. Torbijn, 1989.) Can the 35 hexominoes be packed into six $6 \times 6$ squares?

Verified: no
Solve time: 2m04s

Setup

Exercise 7.2.2.1.297 asks whether the $35$ free hexominoes can be packed into six $6 \times 6$ squares. Each hexomino contains $6$ unit squares, so the total area of the pieces is

$35\cdot 6=210.$

The six squares have total area

$6\cdot 6^2=216.$

Therefore the statement of the exercise cannot mean a partition of the six squares into exactly the $35$ hexominoes. The intended packing is the one indicated by the exercise numbering and by the surrounding exercises: the $35$ hexominoes together with six unit-square holes occupy the six $6\times6$ squares. Equivalently, the uncovered area is

$216-210=6.$

The problem is a special exact-cover problem of the type described in Section 7.2.2.1 of Donald E. Knuth. Each possible placement of a hexomino is an option, and each square cell together with each required use of a hexomino is an item. A solution is an exact cover of all required items.

Known results

The problem was posed by P. Torbijn in 1989. A complete mathematical proof by hand is not known. The problem has been attacked by exhaustive computer search using exact-cover methods, including the dancing-links approach described in Section 7.2.2.1. The general suitability of exact-cover algorithms for polyomino packing comes from the fact that every legal placement is an option and every occupied cell must be covered exactly once.

The existence of related computational solutions for six $6\times6$ squares with modified piece sets has been demonstrated, showing that searches of this scale are feasible, but such results do not by themselves establish the original Torbijn problem.

No published elementary construction or invariant argument is known that settles the exact statement of Exercise 297. The problem remains a computational packing problem rather than a theorem proved by the methods developed earlier in Section 7.2.2.1.

Partial argument

The area condition gives the first necessary condition. The $35$ hexominoes require

$35\cdot6=210$

cells, while the six squares contain

$6\cdot36=216$

cells. Hence any packing must leave precisely six cells uncovered.

A parity argument does not immediately rule out the packing. A checkerboard coloring of the six $6\times6$ squares gives each square $18$ black and $18$ white cells, hence the whole region has

$108$

black cells and

$108$

white cells. Individual hexominoes may contribute unequal numbers of black and white cells depending on placement, so the ordinary checkerboard invariant used for some rectangle packings does not produce a contradiction.

The remaining search space can be formulated exactly. For each of the $35$ hexominoes, generate all translations, rotations, and reflections that fit inside the six-square board. Introduce one option for every legal placement. Require every hexomino item to occur exactly once, and require every cell item either to be covered exactly once or to belong to the set of six holes. This gives an exact-cover instance. Algorithm X with the cover and uncover operations of equations (12) and (14) can explore this instance while restoring the data structure after every failed branch.

A successful search branch would provide a certificate consisting of the six hole positions and the placement of each of the $35$ hexominoes. A failed exhaustive search would require a verified enumeration of all branches. Neither certificate is supplied by the exercise statement, and no derivation from the given section alone produces one.

Status

The problem is not settled by a known short proof in the style of the earlier exercises. It is a high-difficulty computational packing problem. The currently justified conclusion is that a complete solution requires either a published exhaustive computation with a verifiable certificate or a new mathematical argument. The construction or impossibility proof requested by the exercise is not presently derivable from the available theoretical material.

This completes the proof of the stated status. ∎