TAOCP 7.2.2.1 Exercise 305

Section 7.2.2.1: Dancing Links

Exercise 305. [25] [25] When a square grid is scaled by $1/\sqrt{2}$ and rotated $45°$, we can place half of its vertices on top of the original ones; the other "odd-parity" vertices then correspond to the centers of the original square cells.

Using this idea we can glue a small domino of area 1 over portions of an ordinary domino of area 2, thereby obtaining ten distinct two-layer pieces called the windmill dominoes:

a) Arrange four windmill dominoes so that the upper layer resembles a windmill. b) Place all ten windmill dominoes inside a $4 \times 5$ box, without overlapping. c) Similarly, pack them all into a $2 \times 10$ box. d) Place them so that the upper layer fills a $(4/\sqrt{2}) \times (5/\sqrt{2})$ rectangle. e) Similarly, fit the upper layer into a $(2/\sqrt{2}) \times (10/\sqrt{2})$ rectangle.

In each case (a)–(e), use Algorithm X to count the total number of possible placements. Also look at the chosen output and choose arrangements that are especially pleasing.

Verified: no
Solve time: 1m57s

Solution

The numerical counts requested in exercise 305 cannot be derived from the information supplied here.

The exercise depends on the exact geometry of the ten windmill dominoes shown in the figure. The text describes the pieces qualitatively, but it does not specify the coordinates of the occupied cells in either layer, the labeling of the ten distinct pieces, or the allowed symmetries of each piece. Those data are required to construct the exact-cover matrix used by Algorithm X.

For each part (a) through (e), a complete solution requires the following construction. The items in the exact-cover instance must include every required occupied position of the relevant box or layer and one item for each of the ten windmill dominoes. Each possible legal placement of a windmill domino is an option covering the corresponding position items and the corresponding piece item. Algorithm X then enumerates all exact covers of this option set. The requested answer for each part is the number of exact covers found, together with selected aesthetically pleasing covers.

The supplied text does not contain enough information to reconstruct that option set uniquely. Different interpretations of the missing figure can produce different exact-cover matrices and therefore different counts.

A complete worked solution requires the figure of the ten windmill dominoes and the arrangement diagrams, or an equivalent specification giving the occupied cells of each of the ten pieces in both layers. With that data, the Algorithm X enumeration and the final counts for parts (a)–(e) can be derived.