TAOCP 7.2.2.1 Exercise 62
Each nonstraight pentomino covers exactly $5$ unit squares.
Section 7.2.2.1: Dancing Links
Exercise 62. ▶ [24] [24] For $n \le 7$, generate all of the ways in which an $n \times n$ square can be packed with $n$ nonstraight pentominoes. (These are the possible arrangements of boxes in a square jigsaw sudoku.) How many of them are symmetric? Hint: See exercise 7.2.2–76.
Verified: no
Solve time: 1m15s
Solution
Each nonstraight pentomino covers exactly $5$ unit squares. A packing of an $n \times n$ square with $n$ such pentominoes therefore covers exactly $5n$ unit squares. Since the board contains $n^2$ unit squares, any valid packing must satisfy
$5n = n^2,$
hence
$n(n-5)=0,$
so $n=5$ is the only admissible value with $n \le 7$.
For $n \in {1,2,3,4,6,7}$ the area constraint fails, so no packings exist.
It remains to treat $n=5$.
For $n=5$, the problem is to tile a $5 \times 5$ board with $5$ pentominoes chosen from the $11$ nonstraight pentomino types (all pentominoes except the straight $I$-piece), using each selected pentomino exactly once, with rotations and reflections allowed as in the standard pentomino convention. This is an exact cover problem in the sense of Section 7.2.2.1, where:
Each item corresponds to a unit square of the $5 \times 5$ grid together with the constraint that each of the chosen pentomino types is used exactly once. Each option corresponds to placing a particular pentomino in a specific position and orientation, covering five grid squares and selecting that pentomino type.
A valid packing is therefore exactly a solution produced by Algorithm X applied to this exact cover instance.
To determine the number of packings, observe that every solution induces a partition of the $25$ board cells into five connected $5$-cell polyominoes, each congruent to a distinct nonstraight pentomino. Since the board is simply connected and has no holes, every pentomino placement is determined uniquely by the embedding of its cells, and distinct solutions correspond to distinct choices of five placements satisfying disjointness and full coverage.
The structure of the $5 \times 5$ board imposes strong boundary constraints. Every pentomino placed in a $5 \times 5$ square must have at least one unit square on the boundary of the board, since an interior $3 \times 3$ subboard contains only $9$ cells and cannot contain a full pentomino disjointly from the boundary. Consequently, every solution must contain at least one pentomino occupying a corner-adjacent configuration. Repeating this restriction forces a recursive boundary decomposition in which each placement reduces the remaining uncovered region to a smaller connected polyomino of area divisible by $5$.
Exhaustive generation via the dancing-links formulation of (10) therefore reduces the problem to a finite exact cover search over the incidence matrix of all placements of the $11$ nonstraight pentominoes on a $5 \times 5$ board. This search produces a finite set of solutions, each corresponding to a distinct tiling by five pentomino placements.
A symmetry of a packing is a transformation of the square by the dihedral group $D_4$ that maps the set of pentomino placements onto itself. A packing is symmetric if it is fixed by a nontrivial element of $D_4$. Equivalently, if $\mathcal{T}$ is a tiling and $g \in D_4 \setminus {1}$, then symmetry occurs when $g(\mathcal{T}) = \mathcal{T}$.
Because each pentomino placement is determined by its set of five occupied cells, any nontrivial symmetry must map each pentomino onto another congruent placement of the same shape type. Since the set of allowed types excludes only the straight pentomino, and every other pentomino has at most the symmetries of the square, any global symmetry of a tiling must permute the five tiles consistently with the board symmetry. In particular, fixed tilings under a reflection or rotation correspond exactly to those exact covers whose solution sets are invariant under the induced permutation of the option set.
Thus the enumeration of symmetric packings is obtained by restricting the exact cover instance to solutions invariant under each nonidentity element of $D_4$, and counting the resulting fixed points. This reduces symmetry counting to standard orbit enumeration under the group action of $D_4$ on the set of all valid Algorithm X solutions.
For $n=5$, the complete set of packings and the number of symmetric ones are obtained by th