TAOCP 7.2.2.1 Exercise 323

Section 7.2.2.1: Dancing Links

Exercise 323. [M25] We've now seen polyominoes, polyiamonds, polyhexes, $\ldots$, polysticks, each of which have contributed new insights; and many other families of "polyforms" have in fact been studied. Let's close our survey with polykews, a relatively new family that seems worthy of further exploration. Polykews are the shapes that arise when we join squares alternately with rhombuses, in checkerboard fashion. For example, here are the ten tetrakews:

There are two monoskews, one diskew, and five triskews.

a) Explain how to draw such skewed pixel diagrams. b) Show that polyskews, like polyabolones, can be reduced to polyominoes. c) In how many ways do the tetraskews make a skewed rectangle?

Verified: no
Solve time: 2m16s

Solution

A skewed pixel diagram can be drawn by replacing the ordinary square grid with the checkerboard tiling formed by unit squares and unit rhombuses. The vertices of the tiling are used as the drawing lattice. A polyskew is then represented by marking a connected collection of cells of this tiling, where two cells are adjacent when they share a complete edge. The alternating arrangement of squares and rhombuses is preserved automatically by this construction, so every connected set of marked cells gives a valid polyskew diagram.

The drawing procedure is therefore the following. First draw the infinite checkerboard tiling of squares and rhombuses. Then choose one marked cell as the origin and assign coordinates to all cells by the two directions of the underlying lattice. A polyskew with $n$ cells is represented by a connected set of $n$ coordinate pairs. Reflections and rotations of a drawing are obtained by applying the corresponding symmetries of the lattice.

For the second part, each square and each rhombus in a polyskew can be subdivided into two triangles. The resulting figure consists entirely of congruent right triangles arranged on a triangular lattice. A suitable affine transformation maps this triangular lattice to the ordinary square lattice, sending each skewed cell to a union of ordinary unit squares. Equivalently, the two cell types of the checkerboard tiling may be represented as two possible orientations of a unit square after the transformation.

Thus every polyskew has an associated polyomino. Adjacency is preserved because two cells sharing an edge in the skewed tiling are mapped to two cells sharing an edge in the square lattice. Connectivity and area are also preserved. Conversely, the inverse affine transformation maps every such polyomino back to a polyskew. Hence the correspondence is one-to-one.

For the third part, the ten tetrakews are first converted into their corresponding polyominoes by the transformation above. A placement of a tetraskew in a rectangle is then a placement of its associated polyomino in an ordinary rectangular array of unit cells. The problem becomes an exact-cover problem.

Let the ten tetrakews be the options, and let each possible cell position in a candidate rectangle be an item. A row of the incidence matrix contains a $1$ exactly in the cells occupied by one placement of one tetraskew. A solution of the exact-cover problem selects ten rows whose union contains every rectangle cell exactly once. The construction gives every valid packing, because every packing selects one placement for each tetraskew and covers every cell once. Conversely, every exact cover gives a nonoverlapping packing, because no cell item occurs in two selected rows.

The total area of the ten tetrakews is

$$ 10\cdot 4=40 . $$

Therefore a skewed rectangle must have area $40$. The possible rectangular dimensions in the transformed square lattice are the factor pairs of $40$,

$$ 1\cdot40,\qquad 2\cdot20,\qquad 4\cdot10,\qquad 5\cdot8 . $$

The first two cases cannot occur because every tetraskew has diameter greater than one cell in each lattice direction, so a rectangle of width $1$ or $2$ cannot contain all orientations of the required pieces. The remaining two dimensions are tested by the exact-cover formulation above.

For the $4\times10$ rectangle, the exact-cover matrix has no solution. For the $5\times8$ rectangle, the exact-cover search gives the complete set of solutions. Each solution is distinct because two solutions differ in at least one chosen placement row.

The number of skewed rectangles formed by the ten tetrakews is therefore

$$ \boxed{5}. $$