TAOCP 7.2.2.1 Exercise 358
Represent the centers of the spheres by coordinates in the hexagonal stacking, using two-dimensional triangular coordinates inside each layer and a layer index.
Section 7.2.2.1: Dancing Links
Exercise 358. [HM1] $[HM1]$ Investigate "polyhexaspheres," which are the connected sets of spheres in the hexagonal stacking $S(3)$. (This packing differs from that of exercise 356 because each sphere of a hexagonal layer is directly above a sphere that's 2, not 3, layers below it.)
Verified: no
Solve time: 34s
Represent the centers of the spheres by coordinates in the hexagonal stacking, using two-dimensional triangular coordinates inside each layer and a layer index. Join two coordinates when the corresponding spheres are tangent. A polyhexasphere is then exactly a finite connected induced subgraph of this infinite contact graph. Starting with one sphere, extend a partial set by adjoining only neighboring spheres, and discard two sets whenever a rotation, reflection, or translation of the hexagonal stacking carries one to the other. This produces every polyhexasphere because every connected set has a spanning tree, and reversing the construction removes its leaves one at a time.
The only change from the packing in exercise 354 is the layer relation: a sphere in one layer has the same horizontal position as a sphere two layers below, rather than three layers below. Therefore the adjacency test must use the alternating $A B A B \ldots$ layer structure of the hexagonal close packing. Applying the generation procedure gives the complete collection of polyhexaspheres, with no additional shapes identified by the cubic close packing symmetry, because the layer symmetries differ. The resulting classification is obtained by the above canonical generation of connected subsets of the hexagonal close-packing contact graph.