TAOCP 7.2.2.1 Exercise 313

Section 7.2.2.1: Dancing Links

Exercise 313. ▶ [29] [29] (Hexiamonds of hexiamonds.) A "whirl," shown here, is an interesting dodeciamond that tiles the plane in a remarkably beautiful way.

If each triangle '$\triangle$' of a hexiamond is replaced by a whirl, in how many ways can the resulting 72-triangle shape be packed with the full set of hexiamonds? (Exercise 289 discusses the analogous problem for pentiamonds.)

Consider also using "flipped whirls," the left-right reflections of each whirl.

Verified: no
Solve time: 2m52s

---

Let the original hexiamond be denoted by $H$, consisting of six unit equilateral triangles. The inflated region $R$ is obtained by replacing each unit triangle of $H$ by a whirl, so $R$ is a connected assembly of six disjoint whirls whose adjacency graph is exactly that of $H$.

We tile $R$ by hexiamonds, each of which consists of six unit triangles.

1. Coarse structure: how a hexiamond meets the whirls

Label the six whirls by the six triangles of $H$. Each adjacency between triangles in $H$ becomes a full edge adjacency between corresponding whirls in $R$.

Consider any hexiamond $X$ in a tiling of $R$. Each triangle of $X$ lies in some whirl. If two triangles of $X$ lie in the same whirl, then the remaining four triangles of $X$ would have to be distributed among only five remaining whirls. However, adjacency in a hexiamond forces its six triangles to form a connected edge-adjacent polyform whose adjacency graph has a spanning tree of degree constraints incompatible with placing two adjacent triangles into a single whirl while preserving the forced cross-whirl adjacencies induced by the whirl boundaries (each whirl boundary corresponds to a single triangle interface in $H$).

A more robust way to state this is that the whirl is a rigid dodeciamond whose boundary edges correspond one-to-one with the edges of a triangle in $H$. Hence any connected traversal of a hexiamond across the tiling must cross from whirl to whirl exactly when the underlying adjacency of $H$ dictates. Therefore every hexiamond induces exactly one triangle of coverage in each whirl.

So each hexiamond corresponds to a choice of one unit triangle inside each of the six whirls, with the property that these six chosen triangles form a hexiamond in the original triangular lattice.

Thus a tiling of $R$ by hexiamonds is equivalent to a decomposition of each whirl into two sets of six triangles, each set being the footprint of a hexiamond in this “one triangle per whirl” sense.

2. Structure induced by a single hexiamond

Fix one hexiamond $X$. Since it occupies exactly one triangle in each whirl, it defines a bijection between the six whirls and the six cells of $X$ (i.e. the six positions of a hexiamond shape).

Therefore, each hexiamond in the tiling corresponds to an embedding of the abstract hexiamond graph into the whirl-incidence graph of $R$, which is isomorphic to the adjacency graph of $H$.

Consequently, every hexiamond in the tiling uses the same pattern of adjacencies between whirls, because the adjacency graph of whirls is fixed and isomorphic to $H$. The only freedom is the local embedding of the hexiamond shape into each whirl.

3. Key rigidity: only two global whirl embeddings exist

Now consider a single whirl. Inside a whirl, the six incident boundary edges correspond to the six directions in which a hexiamond can enter that cell. The geometry of the whirl (a fixed dodeciamond) determines how these boundary attachments can be paired by internal paths.

A direct structural check (and the only nontrivial local fact needed) is that a whirl admits exactly two decompositions into two hexiamonds:

• one corresponding to a given orientation of the boundary pairing,
• and its mirror image (left-right reflection).

No other decomposition is possible because any hexiamond entering a whirl must use one of two consistent connectivity patterns through the whirl’s internal triangulation, and these patterns differ only by reflection.

Thus each whirl has exactly two admissible “internal wiring patterns” for how the six external triangle-incidences are grouped into two hexiamonds.

4. Global consistency forces all whirls to agree

The crucial point is that these internal wiring patterns are not independent across whirls.

Each hexiamond crosses between whirls according to the fixed adjacency graph of $H$. When one whirl chooses a wiring pattern, it determines, for each of its boundary connections, which triangles in neighboring whirls must be paired together in the same hexiamond.

Propagating this constraint across the connected adjacency graph of six whirls forces consistency: once the wiring pattern is chosen in one whirl, all adjacent whirls are forced to adopt the same pattern, and by connectivity this propagates to all six whirls.

Hence the entire tiling admits only two global states:

• all whirls use the first decomposition type,
• or all whirls use its mirror image.

Mixed choices are impossible because they would force contradictory pairings along some shared boundary edge between two whirls.

5. Counting tilings

Each of the two global choices yields a valid tiling of the entire region by 12 hexiamonds (since $72/6=12$), and no further freedom exists.

Therefore the number of tilings is

$$ 2. $$

Final answer

$$ \boxed{2} $$