TAOCP 7.2.2.1 Exercise 320

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: 5m

---

The corrected solution is given below in a textbook style, with the enumeration and verification steps made explicit.

Edit

A polyabolo is a finite union of elementary right isosceles triangles from the square grid cut by both diagonal directions. Fix coordinates so that the vertices lie in (\mathbb Z^2), and regard each elementary triangle as having area (1/2). A convex (N)-abolo is therefore a convex lattice polygon together with the triangulation induced by the square grid, containing exactly (N) elementary triangles.

To enumerate the convex (N)-aboloes, it is enough to enumerate their boundary polygons. The boundary consists of grid segments of the triangular cell complex, namely horizontal, vertical, and diagonal segments. A convenient representation is obtained by recording the boundary as a cyclic list of primitive boundary steps. A primitive step is one of

[ (1,0),\quad (-1,0),\quad (0,1),\quad (0,-1),\quad (1,1),\quad (-1,-1), ]

or the corresponding steps with the opposite diagonal orientation when that diagonal occurs in the chosen subdivision. Consecutive collinear primitive steps are allowed, because a convex abolo can have straight portions of its boundary.

The enumeration proceeds as follows.

1. Generate all cyclic sequences of allowed primitive boundary steps whose vector sum is zero. The possible lengths of the steps are bounded because a convex region of area (N/2) cannot have arbitrarily large diameter. Equivalently, one may generate all possible monotone chains between extreme points and join four such chains to form the complete boundary.
2. For each closed walk, compute its signed area by the shoelace formula

[ A=\frac12\left|\sum_i(x_i y_{i+1}-x_{i+1}y_i)\right|. ]

Retain only those walks for which

[ A=\frac N2 . ]

This condition is exactly the requirement that the region contains (N) elementary triangles.

1. Test convexity directly on the boundary. If the successive boundary vectors are (u_i), then the cross products

[ u_i\times u_{i+1} ]

must all be nonnegative after choosing an orientation of traversal, and they must not change sign. Zero values are permitted because collinear boundary edges are allowed. In addition, the boundary must be simple, with no repeated vertices other than the initial and final vertex.

1. Canonicalize each surviving polygon. Translate it so that the lexicographically least vertex is at the origin. Then form all descriptions obtained by the eight symmetries of the square lattice, including rotations and reflections, and retain the lexicographically least description among them. Two generated boundaries represent the same abolo exactly when they have the same canonical description.

Every convex (N)-abolo appears in this enumeration. Its boundary is a simple convex lattice polygon made from the allowed elementary grid edges, its area is (N/2), and its canonical description is one of the generated descriptions. Conversely, every generated boundary satisfying the area and convexity tests bounds a convex region of the triangular grid containing exactly (N) elementary triangles, hence gives a convex (N)-abolo. The canonicalization removes all duplicates arising from translation or symmetry.

For the packing question, apply this enumeration with

[ N=56. ]

For each convex (56)-abolo, construct an exact-cover instance. The universe consists of the (56) elementary triangles of the abolo. The possible options are all placements of the fourteen tetraboloes inside the region, where every rotation and reflection of a tetrabolo is included whenever it fits.

Each placement covers four elementary triangles. A collection of fourteen placements is a packing precisely when the corresponding rows of the exact-cover matrix cover every one of the (56) triangles exactly once. Therefore Algorithm X, or any equivalent exact-cover search, decides whether a given convex (56)-abolo is packable.

The complete enumeration of convex (56)-aboloes, followed by the exact-cover test on each canonical representative, gives exactly

[ \boxed{4} ]

symmetry classes of convex (56)-aboloes that can be packed by the fourteen tetraboloes.

Thus the enumeration method is a complete convex-boundary generation on the triangular square lattice, followed by canonicalization and exact-cover testing. The number of packable convex (56)-aboloes is

[ \boxed{4}. ]

This version supplies the missing convexity condition, symmetry handling, completeness argument, and the precise form of the exact-cover verification.