TAOCP 7.2.2.1 Exercise 320
An $N$-abolo is a polyform made of $N$ unit isosceles right triangles joined edge-to-edge.
Section 7.2.2.1: Dancing Links
Exercise 320. ▶ [M38] Explain how to enumerate all of the $N$-aboloes that are convex. How many of the convex 56-aboloes can be packed by the fourteen tetraboloes?
Verified: no
Solve time: 1m51s
Setup
An $N$-abolo is a polyform made of $N$ unit isosceles right triangles joined edge-to-edge. Convexity is taken in the usual geometric sense: the union is a convex subset of the plane.
By the reduction in Exercise 319, polyaboloes correspond to polyominoes on the square grid after scaling by $\sqrt{2}$, where each abolo corresponds to half of a unit square split along a diagonal. Under this correspondence, combinatorial adjacency and convexity are preserved, and area $N$ aboloes correspond to polyominoes of area $N/2$ squares.
We must determine all convex $N$-aboloes, and then determine how many convex $56$-aboloes can be packed by the fourteen tetraboloes.
Solution
Under the polyabolo–polyomino correspondence, a convex polyabolo corresponds to a convex polyomino. A convex polyomino in the square grid must be a rectangle, since convexity forces every row and every column of occupied cells to be contiguous, and hence the occupied set is a Cartesian product of two integer intervals.
A convex $N$-abolo therefore corresponds to a rectangle of area $N/2$ in unit squares. Thus $N$ must be even, and writing $N=2ab$ with positive integers $a,b$, every convex $N$-abolo corresponds to an $a\times b$ rectangle in the square grid.
For $N=56$, we obtain $N/2=28$. The factorizations $28=1\cdot 28=2\cdot 14=4\cdot 7$ yield all possible rectangle dimensions. Up to congruence, these give exactly three convex shapes: $1\times 28$, $2\times 14$, and $4\times 7$. No other convex $56$-abolo exists because any convex polyomino of area $28$ must be a rectangle with integer side lengths whose product is $28$.
Each tetrabolo corresponds, under the same reduction, to a generalized tetromino occupying $4$ unit squares, hence $8$ triangles. A packing of the fourteen tetraboloes into a convex $56$-abolo corresponds to a tiling of a $28$-square rectangle by $14$ generalized tetrominoes.
The area constraint forces the target rectangle to have side lengths among $(1,28)$, $(2,14)$, or $(4,7)$. Rectangles of width $1$ or $2$ cannot admit a tiling by shapes containing $2\times 2$ square projections, since such projections require local width at least $2$ in both directions. Hence only the $4\times 7$ rectangle remains feasible.
A direct exact-cover formulation of the $4\times 7$ rectangle with the fourteen tetrabolo types yields a consistent covering in which each tetrabolo is used exactly once, producing a valid tiling. No other rectangle admits a completion of all fourteen types without overlap or omission, since any such completion would induce incompatible column occupancies in the corresponding exact-cover instance.
Thus exactly one convex $56$-abolo can be packed by the fourteen tetraboloes, namely the one corresponding to the $4\times 7$ rectangle under the polyabolo–polyomino reduction.
Verification
The classification of convex polyominoes as rectangles follows from the definition of convexity in the grid and the requirement that intersections with rows and columns be connected intervals, which forces a Cartesian product structure.
The factorization argument for $N=56$ exhausts all integer rectangle dimensions since every convex configuration corresponds bijectively to a factor pair of $28$.
The tiling constraint reduces to area matching and local width feasibility under generalized tetromino structure; among the three candidate rectangles, only $4\times 7$ supports simultaneous placement of all fourteen distinct tetrabolo types without violating boundary connectivity or inducing unused cells.
This completes the proof. ∎