TAOCP 7.2.2.1 Exercise 355

Section 7.2.2.1: Dancing Links

Exercise 355. [25] [25] The theory in exercise 354 allows us to represent polysphere cells with three integer coordinates $xyz$, because $x$, $y$, and $z$ are nonnegative in base placements. The other variable, $w$, is redundant (but worth keeping in mind); it always equals $-x - y - z$.

a) What's a good way to find all the base placements of a given polysphere ${x_1 y_1 z_1,$ $x_2 y_2 z_2, \ldots, x_n y_n z_n}$? Hint: Use exercise 354 to tweak the method of exercise 324.

b) Any three points of three-dimensional space lie in a plane. So exercise 354(b) tells us that there are just four trispherics: a tromino, two trihexes, and one that's both:

$$\text{bent trisphere} \qquad \text{straight trisphere} \qquad \text{phenalene} \qquad \text{phenanthrenene}$$ $$\text{(anthracene)}$$

What are their base placements?

c) According to exercise 354(c), every base placement of a tetrasphere occurs in the SGB graph $\mathit{sample}(3,3,3,3,0,0)$. Use exercise 7.2.2–75 to find all of the four-element connected subsets of that graph, and hence find all of the distinct tetraspheres. How many times does each isomer occur in the graph?

Verified: no
Solve time: 8m48s