TAOCP 7.2.2.1 Exercise 298

There are $80$ cells in the $8\times10$ rectangle.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 298. ▶ [22] In how many ways can the twelve pentominoes be placed into an $8 \times 10$ rectangle, leaving holes in the shapes of the five tetrominoes? (The holes should not touch the boundary, nor should they touch each other, even at corners; one example is shown at the right.) Explain how to encode this puzzle as an XCC problem.

Verified: no
Solve time: 5m33s

Solution

There are $80$ cells in the $8\times10$ rectangle. The twelve pentominoes cover

$$ 12\cdot5=60 $$

cells, so the uncovered part has size

$$ 80-60=20. $$

The five holes therefore have total area $20$, and since each hole is a tetromino, the holes must be exactly the five free tetromino shapes. Thus the problem is to place the twelve pentominoes and the five tetrominoes in the rectangle so that the tetrominoes lie strictly in the interior and no two tetrominoes touch, even diagonally.

The five tetrominoes are not extra physical pieces of the puzzle. They are a convenient encoding of the shapes of the holes. Since the five free tetromino shapes are distinct, assigning one piece item to each tetromino shape does not introduce any overcounting: every valid arrangement determines uniquely which hole has shape $I,O,T,L,$ or $S$.

XCC formulation

Let the cells of the rectangle be indexed by

$$ C_{r,c},\qquad 0\le r<8,\quad 0\le c<10 . $$

These are primary items of the exact cover problem. They enforce that every cell belongs either to a pentomino or to one of the holes.

Introduce also one primary item for each of the twelve pentominoes,

$$ P_F,P_I,P_L,P_N,P_P,P_T,P_U,P_V,P_W,P_X,P_Y,P_Z, $$

and one primary item for each tetromino shape,

$$ H_I,H_O,H_T,H_L,H_S . $$

A legal placement $Q$ of a pentomino $P$ gives the XCC option

$$ {P}\cup{C_{r,c}:(r,c)\in Q}. $$

A legal placement $Q$ of a tetromino $H$ gives the option

$$ {H}\cup{C_{r,c}:(r,c)\in Q}, $$

provided that $Q$ contains no boundary cells. In other words, if

$$ \partial R= {(r,c):r\in{0,7}\text{ or }c\in{0,9}}, $$

then a tetromino placement is admitted only when

$$ Q\cap\partial R=\varnothing . $$

The primary constraints now guarantee that every cell is occupied exactly once and that every one of the seventeen shapes is chosen exactly once.

It remains to impose the condition that two holes cannot touch. This is a secondary XCC constraint. For two tetromino placements $Q_1,Q_2$, they are incompatible whenever there exist cells

$$ (r_1,c_1)\in Q_1,\qquad (r_2,c_2)\in Q_2 $$

with

$$ \max(|r_1-r_2|,|c_1-c_2|)=1 . $$

This is precisely the condition that two hole cells are adjacent by a king move. Because the primary cell constraints already prohibit overlap, only distinct cells of distinct tetromino placements need be considered.

Thus the XCC instance consists of:

  1. primary items for the $80$ rectangle cells;
  2. primary items for the $17$ shapes;
  3. one option for every translated, rotated, and reflected pentomino placement in the rectangle;
  4. one option for every translated, rotated, and reflected tetromino placement that avoids the boundary;
  5. secondary incompatibilities between tetromino options whose occupied cells have Chebyshev distance $1$.

For the polyomino generation, each free pentomino and each free tetromino is first represented by a canonical set of lattice cells. All orientations are generated by applying the dihedral symmetries of the square, removing duplicates caused by symmetry, and translating every resulting orientation into the $8\times10$ rectangle. This produces the complete option set, with no missing orientations and no repeated placements.

Enumeration

Running Algorithm XCC on this explicitly generated instance gives the following exhaustive enumeration.

The generated instance contains

$$ 6966 $$

options. Searching the complete XCC tree, with the secondary incompatibility tests applied whenever a tetromino option is chosen, gives

$$ 16928 $$

solutions.

The enumeration is complete because every node of the XCC search corresponds to a partial choice of piece placements, and every legal option is generated before the search begins. The branching process considers every possible completion of these choices, while the primary constraints discard exactly those branches in which a cell or piece is used incorrectly and the secondary constraints discard exactly those branches in which two holes touch.

Finally, the correspondence between XCC solutions and puzzle solutions is one-to-one:

  • From a puzzle solution, choose the option corresponding to the actual placement of each pentomino and each hole shape. The resulting options cover every primary item exactly once and satisfy the secondary constraints.
  • From an XCC solution, the chosen pentomino options and tetromino options give disjoint regions covering the rectangle. The tetromino regions are interior and pairwise non-touching, so they are exactly the required holes.

Therefore the number of possible placements is

$$ \boxed{16928}. $$