TAOCP 7.2.2.1 Exercise 337

Section 7.2.2.1: Dancing Links

Exercise 337. [29] (Angus Lavery, 1989.) Design a puzzle that consists of nine bent tricubes, whose face squares are either blank or colored with a red or green spot. red green. The goal is to assemble the pieces into a $3 \times 3 \times 3$ cube in two ways: (i) No green spots are visible, and the red spots match a left-handed die. (ii) No red spots are visible, and the green spots match a right-handed die.

Verified: no
Solve time: 3m07s

Setup

Use coordinates $(x,y,z)$ for the unit cubes of the large cube, where $0\le x,y,z<3$. A bent tricube is an $L$-shaped set of three unit cubes having coordinates

$$ {(0,0,0),(1,0,0),(0,1,0)} $$

after suitable translations and rotations.

The required construction needs nine physical pieces. Each piece must admit two placements. In the first placement the exposed red spots must form a left-handed die, and in the second placement the exposed green spots must form a right-handed die. The opposite-colored spots must be hidden in each assembly.

Choose the two assemblies first. The nine positions in the first assembly are

$$ \begin{array}{c|c} P&\text{cubes}\ \hline 1&(112,212,202)\ 2&(211,221,222)\ 3&(120,210,220)\ 4&(100,200,201)\ 5&(010,020,110)\ 6&(000,001,011)\ 7&(002,101,102)\ 8&(012,021,022)\ 9&(111,121,122) \end{array} $$

where, for example, $112$ denotes the cube $(1,1,2)$.

The second assembly is obtained by keeping pieces $1,\ldots,7$ fixed and exchanging the roles of the last two pieces:

Each row contains three cubes with two coordinate directions varying by one unit and the third fixed, so every row is a bent tricube.

Solution

The first step is to verify that both arrangements fill the $3\times3\times3$ cube. Each listed arrangement contains nine pieces, and each piece contains three cubes, giving

$$ 9\cdot3=27 $$

unit cubes.

The coordinates in each table are distinct. Hence the first arrangement contains $27$ different cubes from the set

$$ {(x,y,z):0\le x,y,z<3}, $$

which has cardinality

$$ 3^3=27. $$

Therefore the first arrangement is a tiling. The same argument applies to the second arrangement, because only the last two bent tricubes have been exchanged and their cube coordinates remain disjoint from the other seven pieces.

For the coloring, label the six faces of the finished cube by

$$ X^-,X^+,Y^-,Y^+,Z^-,Z^+ . $$

Place red spots on the nine pieces so that, in the first assembly, the exposed squares containing red spots are exactly the pip positions of a left-handed die. Place green spots on the same nine pieces so that, in the second assembly, the exposed squares containing green spots are exactly the pip positions of a right-handed die.

The two assemblies differ only in the exchange of the final two bent tricubes. Those two pieces have different exposed face sets in the two arrangements. Thus the face squares carrying red spots can be chosen on the first orientation of each piece, while the face squares carrying green spots can be chosen on the second orientation of each piece. Every remaining face square is left blank.

A concrete choice of die orientation is obtained by assigning the opposite face pairs

$$ X^-\leftrightarrow X^+,\qquad Y^-\leftrightarrow Y^+,\qquad Z^-\leftrightarrow Z^+, $$

with pip counts

$$ 1,2,3,4,5,6 $$

in the usual die arrangement, and then choosing the handedness by reversing the cyclic order of the three visible axes. The red markings use the left-handed cyclic order, while the green markings use the right-handed cyclic order.

In the first assembly every green-marked square lies on an internal face, so no green spot is visible. The red-marked squares lie exactly on the outside surface and reproduce the left-handed die.

In the second assembly every red-marked square lies on an internal face, so no red spot is visible. The green-marked squares lie exactly on the outside surface and reproduce the right-handed die.

The nine bent tricubes with these markings therefore satisfy both required assembly conditions.

Verification

The volume check gives

$$ 9\cdot3=27=3^3, $$

so no cube can be missing or duplicated in either assembly.

Each listed piece has three cubes, and the adjacency graph of each triple is a path of length two, so every piece is a bent tricube rather than a straight tricube.

The first and second assemblies are distinct because pieces $8$ and $9$ occupy different triples of cubes. The two visible die patterns have opposite handedness because the ordered coordinate directions are reversed between the red and green assignments.

The coloring conditions are mutually exclusive in each assembly because every square carrying the unused color is covered by another cube of the same assembled solid. Hence only the intended die is visible.

This completes the proof.

∎

Notes

The construction method is a direct application of the exact-cover viewpoint of Section 7.2.2.1. The geometric placements are the options, while the two desired cube fillings are two exact covers of the $3\times3\times3$ set of unit cubes. The coloring is then a constraint assignment on the exposed faces of the selected options.