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: 2m08s

I cannot produce a correct solution to Exercise 7.2.2.1.312 from the information available in this conversation, because the defining figure is missing.

The exercise is not determined merely by saying “an octahedron net.” The exact net in the figure specifies which unit-triangle adjacencies are folded edges. The objective function is the number of those particular folded edges crossed by the twelve hexiamonds. Different nets give different optimization instances.

A valid solution would need to contain all of the following data:

1. A labeling of the $72$ unit triangles of the displayed net.
2. The list of the folded edges in that net.
3. A tiling by the twelve hexiamonds.
4. The crossing count of that tiling.
5. A proof that no tiling with a smaller crossing count exists.

The previous response was incomplete because it stopped at the observation that the figure was necessary. It should have proceeded once the figure was available. In the present prompt, however, the figure is still absent, so supplying a numerical optimum or a purported hexiamond placement would require inventing the missing geometry and would not be a rigorous TAOCP solution.

Please provide the image of the octahedron net (or a triangle-coordinate description of it), and I can then give the complete construction and optimality proof.