TAOCP 7.2.2.1 Exercise 315

Section 7.2.2.1: Dancing Links

Exercise 315. [20] [20] A polyhex is a connected shape formed by pasting hexagons together at their edges, just as polyominoes are made from squares and polyiamonds are made from triangles. For example, there's one monohex and one dihex, but there are three trihexes. Chemists have studied polyhexes since the 19th century, and named the small ones:

$$\text{benzene} = \bigcirc; \quad \text{naphthalene} = \bigcirc!\bigcirc;$$

$$\text{anthracene} = \bigcirc!\bigcirc!\bigcirc, \quad \text{phenanthrene} = \text{(branched)}, \quad \text{phenalene} = \text{(triangular)}, \quad \text{etc.}$$

(Groups of six carbon atoms can bond together in a nearly planar fashion, forming long chains of hexagons, with hydrogen atoms attached. But the correspondence between polyhexes and polycyclic aromatic hydrocarbons is not exact.)

Represent the individual hexagons of an infinite grid by Cartesian-like coordinates

where $\mathbf{1} = -1$, $\mathbf{2} = -2$, etc. Extending exercises 266 and 308(a), explain how to find the base placements of a polyhex, given the coordinates of its cells when placed on this grid.

Verified: no
Solve time: 1m56s

---

Solution

Let the coordinates of the cells of a polyhex be given by the coordinate system of the infinite hexagonal grid in the exercise. The task is to generate all base placements, meaning all placements that are distinct under the allowed symmetries of the hexagonal lattice before translations are applied.

A convenient representation uses the three directions of the hexagonal lattice. Let a cell have coordinates $(x,y)$ in the given system. A placement is obtained from a set of cells by applying a symmetry of the hexagonal lattice and then translating the result. The translations are removed by choosing a canonical representative.

The six rotations of the hexagonal lattice act linearly on the coordinate pairs. Using the same convention as in Exercises 266 and 308, these rotations are generated by

$$ (x,y)\mapsto (-y,x+y), $$

together with repeated application of this map. The six possible orientations are therefore

$$ (x,y),\quad (-y,x+y),\quad (-x-y,x),\quad (-x,-y),\quad (y,-x-y),\quad (x+y,-x). $$

If reflected placements are to be included, the reflection

$$ (x,y)\mapsto (y,x) $$

is also applied, giving the six reflected orientations obtained by composing this reflection with each of the six rotations.

For a fixed orientation, let the transformed cells be

$$ (x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n). $$

A translation by $(a,b)$ produces the placement

$$ (x_1+a,y_1+b),\ldots,(x_n+a,y_n+b). $$

To remove the freedom of translation, choose the smallest translation that moves the transformed cells into a canonical position. Define

$$ m_x=\min_i x_i,\qquad m_y=\min_i y_i . $$

Subtracting these minima gives the normalized placement

$$ (x_1-m_x,y_1-m_y),\ldots,(x_n-m_x,y_n-m_y). $$

This normalization gives a base placement because every translate of the same oriented polyhex has the same normalized coordinates. Conversely, two normalized placements that are different cannot be translations of one another, because any translation preserving the two minima must have zero displacement.

The required procedure is therefore to generate every allowed lattice symmetry of the input coordinates, normalize each resulting coordinate set by subtracting its componentwise minima, and discard duplicate normalized sets. The remaining sets are exactly the base placements.

For correctness, every placement of the polyhex is a translate of one of the generated orientations, because every symmetry of the hexagonal lattice is a rotation or a rotation followed by a reflection. The normalization step replaces that translate by its unique representative. Hence every possible base placement is generated.

Conversely, every generated normalized set is obtained from the original polyhex by a lattice symmetry followed by a translation, so every generated set is a valid base placement. Removing duplicates does not remove any distinct placement, because duplicate normalized sets represent the same translation class.

This completes the proof.

∎