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: yes
Solve time: 1m14s

Solution

Represent each hexagon of the infinite grid by a triple $(x_1,x_2,x_3)\in\mathbb{Z}^3$ satisfying $x_1+x_2+x_3=0$, with adjacency defined by moving from $(x_1,x_2,x_3)$ to one of the six points obtained by increasing one coordinate by $1$ and decreasing another by $1$. This realizes the hexagonal grid as the graph induced by the plane $x_1+x_2+x_3=0$ in $\mathbb{Z}^3$, consistent with the coordinate convention in the figure.

A polyhex $P$ is a finite connected set $S\subset\mathbb{Z}^3$ under this adjacency. A placement of $P$ on the grid is an injective map $\pi:S\to\mathbb{Z}^3$ that preserves adjacency structure, and every such placement differs from $S$ by an isometry of the hexagonal lattice followed by a translation.

The isometries of the hexagonal grid form the dihedral group of order $12$, generated by the $6$ rotations permuting $(x_1,x_2,x_3)$ cyclically and the $6$ reflections swapping two coordinates. Every isometry $g$ acts on $S$ componentwise, producing a congruent copy $g(S)$.

For each fixed isometry $g$, all translations of $g(S)$ are obtained by adding a vector $(t_1,t_2,t_3)$ with $t_1+t_2+t_3=0$. A canonical representative of these translates is obtained by forcing a distinguished condition on coordinates. Choose $m(g)=\min{x_1:(x_1,x_2,x_3)\in g(S)}$, and then restrict to translates where the minimal first coordinate equals $0$. Concretely, define $t=(-m(g),0,m(g))$ in any consistent coordinate normalization, so that $g(S)+t$ contains a point with first coordinate $0$ and no point with negative first coordinate.

This choice still leaves ambiguity when several cells attain the same minimal first coordinate. To eliminate this, order points lexicographically and select the unique translation $t_g$ such that the lexicographically least element of $g(S)+t_g$ is $(0,0,0)$. This condition determines a unique representative of each orbit of translations.

A base placement of the polyhex is defined as each set

$B_g = g(S)+t_g$

obtained from an isometry $g$ followed by its canonical translation $t_g$. The collection of all base placements consists of exactly one representative from each equivalence class of placements under translations, and it has at most $12$ elements corresponding to the $12$ isometries of the hexagonal lattice.

To construct all base placements from the coordinate description of $S$, compute $g(S)$ for each of the $12$ isometries $g$, then translate each image so that its lexicographically least cell is $(0,0,0)$. The resulting normalized sets are the required base placements for use in exact cover generation.

This completes the construction of base placements for a polyhex from its cell coordinates. ∎