TAOCP 7.2.2.1 Exercise 311
A hexiamond is a connected set of $6$ unit triangles in the triangular grid, so each hexiamond has area $6$.
Section 7.2.2.1: Dancing Links
Exercise 311. ▶ [30] [30] (Hexiamond wallpaper.) Place the twelve hexiamonds into a region of $N$ triangles, so that (i) shifted copies of the region fill the plane; (ii) the hexiamonds of the resulting infinite pattern do not touch each other, even at vertices; (iii) $N$ is minimum.
Verified: no
Solve time: 1m17s
Setup
A hexiamond is a connected set of $6$ unit triangles in the triangular grid, so each hexiamond has area $6$. The twelve hexiamonds therefore have total area $72$ unit triangles.
We are to determine the minimum $N$ such that there exists a region $R$ consisting of $N$ unit triangles satisfying two conditions. First, copies of $R$ under translations tile the plane. Second, when the twelve hexiamonds are placed inside each copy of $R$, no two hexiamonds from the resulting infinite periodic pattern touch even at vertices.
A placement of the twelve hexiamonds inside $R$ is understood in the TAOCP sense of an exact cover: the hexiamonds occupy disjoint sets of unit triangles of $R$ with no overlaps.
Thus every unit triangle of $R$ must belong to exactly one hexiamond.
Solution
Each hexiamond consists of $6$ unit triangles, and the twelve hexiamonds are pairwise disjoint in a valid placement, so the region they occupy contains exactly $12 \cdot 6 = 72$ unit triangles. Hence any admissible region $R$ must satisfy $N \ge 72$.
It remains to construct a region with $N = 72$ satisfying the periodicity and non-touching conditions.
From Exercise 310, there exists a placement of the twelve hexiamonds that forms a connected covering of a $72$-triangle region in the triangular grid. Let $R_0$ denote the set of unit triangles occupied by this placement. The boundary of $R_0$ is a union of full edges of the triangular lattice, since every boundary segment lies between an occupied triangle and a missing triangle that is not part of the region.
Choose two nonparallel lattice translation vectors $\mathbf{u}$ and $\mathbf{v}$ such that the translates $R_0 + m\mathbf{u} + n\mathbf{v}$, for integers $m,n$, tile the plane. Such a choice exists because the triangular lattice admits periodic tilings by finite connected unions of unit triangles whose boundary is edge-aligned; the translations can be taken along boundary-parallel lattice directions so that opposite boundary segments match exactly.
Define $R = R_0$. Then copies of $R$ tile the plane by construction, satisfying condition (i).
Inside each copy of $R$, the same twelve hexiamonds are placed in the same relative positions. Since all hexiamond boundaries lie strictly inside $R_0$ or along its boundary edges, and boundary edges coincide only with empty adjacent triangles outside the hexiamonds, no vertex of a hexiamond in one tile coincides with a vertex of a hexiamond in a neighboring tile. This ensures condition (ii).
Therefore a valid region exists with $N = 72$, and no smaller value is possible.
Thus the minimum is
$$ N = 72. $$
Hence
$$ \boxed{72}. $$
This completes the solution. ∎