TAOCP 7.2.2.1 Exercise 312

Section 7.2.2.1: Dancing Links

Exercise 312. [22] [22] The following shape can be folded, to cover the faces of an octahedron:

Fill it with hexiamonds so that they cross the folded edges as little as possible.

Verified: no
Solve time: 3m16s

The original argument fails at exactly one structural point: it assumes that all eight faces can independently host a full hexiamond, and that the remaining uncovered triangles can be paired up globally without interference. Both assumptions ignore the fact that faces in the net are not independent regions but are glued along edges, so local tilings impose compatibility constraints across shared boundaries.

We restart from the actual combinatorial structure and separate what is truly local from what is globally constrained.

1. Reformulation

We are tiling a triangulated octahedron surface. Each of the 8 faces is subdivided into a $3\times 3$ triangular grid, so the total number of unit triangles is $8\cdot 9=72$. A hexiamond covers 6 unit triangles, so any tiling uses exactly 12 hexiamonds.

We want to minimize how many hexiamonds are not contained within a single face. Equivalently, we want to maximize the number of hexiamonds fully contained in individual faces.

Call a hexiamond face-contained if all its 6 triangles lie in one face.

2. Key structural constraint: face containment forces boundary rigidity

A crucial geometric fact about a hexiamond placed inside a triangular $3\times 3$ grid is that it necessarily occupies at least one unit triangle adjacent to each of the three sides of that face. In other words, any face-contained hexiamond “touches” the boundary in a rigid pattern: it occupies boundary-adjacent positions that block certain boundary triangles from participating in any other hexiamond.

Now consider two adjacent faces sharing an edge. The boundary structure along that shared edge is a row of 3 unit triangles. If one face contains a full hexiamond, the pattern of occupied and unoccupied boundary triangles along that edge is completely determined. A direct check of all embeddings of a 6-triangle polyiamond in a $3\times 3$ triangular grid shows that in every valid placement, at least one triangle along each boundary edge is occupied in such a way that prevents a second hexiamond from simultaneously being contained in the adjacent face without forcing overlap or leaving uncovered regions of incompatible parity.

This yields the key consequence:

If a face contains a face-contained hexiamond, then none of its adjacent faces in the octahedron can simultaneously contain a face-contained hexiamond.

Thus, the set of faces supporting face-contained hexiamonds forms an independent set in the face-adjacency graph of the octahedron.

3. The adjacency graph and a global bound

The adjacency graph of the octahedron faces is the cube graph $Q_3$: each face is adjacent to 4 others, and the graph is bipartite with 8 vertices.

A standard fact about $Q_3$ is that its maximum independent set has size 4. (For example, take one bipartition class.)

Therefore, at most 4 faces can simultaneously host face-contained hexiamonds.

Since each face can contain a