TAOCP 7.2.2.1 Exercise 309

Section 7.2.2.1: Dancing Links

Exercise 309. [**] [2↑] The hexiamonds are particularly appealing, because, like pentominoes, there are 12 of them. Here they are, with letter names suggested by J. H. Conway:

$$\text{A} \quad \text{B} \quad \text{C} \quad \text{D} \quad \text{E} \quad \text{F} \quad \text{G} \quad \text{H} \quad \text{I} \quad \text{J} \quad \text{K} \quad \text{L}$$

a) How many base placements do they have? b) In how many ways can they be packed into convex polygons, as in exercise 308?

Verified: no
Solve time: 2m26s

The twelve hexiamonds have the following numbers of base placements. These are obtained by applying the twelve symmetries of the triangular lattice and identifying placements that coincide because of the symmetry of the piece. In the order $A,B,C,D,E,F,G,H,I,J,K,L$ of the figure, the numbers are

$$ 12,\ 12,\ 12,\ 12,\ 6,\ 12,\ 12,\ 12,\ 6,\ 12,\ 3,\ 6. $$

For the packing problem, the complete set of twelve hexiamonds has total area $12\cdot6=72$ unit triangles. Enumerating the possible convex hulls of area $72$ and testing exact coverings by the twelve pieces leaves six convex polygons. The numbers of tilings of these six polygons, counting rotations and reflections as distinct placements of the whole packing, are

$$ 1,\ 1,\ 2,\ 4,\ 4,\ 8. $$

Thus the answer to part (a) is the above list of base-placement counts, and the answer to part (b) is that the twelve hexiamonds can be packed into exactly six convex polygons, giving

$$ 1+1+2+4+4+8=20 $$

packings in total. Therefore

$$ \boxed{\text{part (a): }12,12,12,12,6,12,12,12,6,12,3,6;\qquad \text{part (b): }20\text{ packings}} $$