TAOCP 7.2.2.1 Exercise 319

Section 7.2.2.1: Dancing Links

Exercise 319. [21] After polyominoes, polyiamonds, and polyhexes, the next most popular polyforms are the polyaboloes, originally proposed by S. J. Collins in 1961. These are the shapes obtainable by attaching isoceles right triangles at their edges; for example, there are three diaboloes ${\square, \angle, \square}$. Notice that any $n$-abolo corresponds to a $2n$-abolo, when it has been scaled up by $\sqrt{2}$.

The 14 tetraboloes can be named by using rough resemblances to hexiamonds:

Show that the study of polyaboloes can be reduced to the study of (slightly generalized) polyominoes, just as exercise 318 reduces polyiamonds to polyhexes.

Verified: yes
Solve time: 1m18s

Solution

Each polyabolo is a finite connected union of congruent isosceles right triangles whose sides are either legs of length $1$ or hypotenuses of length $\sqrt{2}$. Two triangles are adjacent when they share a full edge.

Fix a reference square lattice in the plane with unit squares. Each unit square is decomposed by its main diagonal into two congruent isosceles right triangles. Denote these two triangles in each square by type $0$ and type $1$, according to whether the hypotenuse has slope $+1$ or $-1$.

Define a mapping $\varphi$ from triangles to lattice data as follows. A triangle $T$ lying in a unit square $S$ is mapped to the pair $(S, \tau)$, where $\tau \in {0,1}$ encodes whether $T$ is the lower-left or upper-right half of $S$ with respect to the chosen diagonal decomposition.

This induces a mapping from a polyabolo $P$ to a set of decorated square cells $\varphi(P)$ in which each occupied unit square carries a subset of ${0,1}$ indicating which of its two triangular halves are present.

Adjacency of triangles in $P$ translates into adjacency relations between these decorated square cells in $\varphi(P)$:

If two triangles share a leg, then they lie in two edge-adjacent unit squares of the lattice, so their images correspond to orthogonally adjacent squares.

If two triangles share a hypotenuse, then they lie in the same unit square but occupy opposite halves; hence they correspond to the two decorations $(S,0)$ and $(S,1)$ inside a single square.

Thus every polyabolo is represented by a connected set of unit squares of the integer lattice together with an internal binary state in each square specifying which of its two diagonal halves are occupied.

Conversely, any such connected configuration of decorated squares determines a unique union of isosceles right triangles, obtained by subdividing each occupied square according to its decoration and taking the corresponding halves. Connectivity in the decorated-square representation ensures connectivity of the resulting triangle union, because every adjacency in the square model corresponds either to sharing a side of a square or to sharing a diagonal inside a square, both of which correspond to shared edges between triangles.

This establishes a one-to-one correspondence between polyaboloes and connected finite configurations of square-lattice cells equipped with a two-state decoration.

Now interpret this as a reduction to polyominoes. Replace each decorated square $(S,\tau)$ by a single enlarged cell $S'$ in a refined lattice in which each unit square is split into two distinguishable positions. Equivalently, form a lattice of unit squares in which each square is labeled by an element of ${0,1}$, and adjacency is defined so that two states inside the same square are adjacent, and states in neighboring squares are adjacent according to the usual square adjacency.

This produces a standard polyomino problem on a slightly generalized square grid, namely a grid whose vertices are pairs $(x,y,\tau)$ and whose adjacency relation includes both orthogonal moves between squares and intra-square transitions between the two triangle states.

Under this construction, every polyabolo corresponds bijectively to a polyomino in this generalized square lattice, since each triangle becomes a single cell and each edge adjacency of triangles becomes adjacency of cells.

Conversely, every connected set of cells in this generalized square lattice determines a unique polyabolo by collapsing each cell back into its corresponding triangle.

Therefore the study of polyaboloes is equivalent to the study of polyominoes on a square lattice with a fixed finite local decoration (a two-state per cell structure), which is a slight generalization in the same sense that polyiamonds reduce to polyhexes.

This completes the reduction. ∎