TAOCP 7.2.2.1 Exercise 314

Let the four pentiamonds be $P_1,P_2,P_3,P_4$.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 314. ▶ [28] [28] (G. Sicherman, 2008.) Can the four pentiamonds be used to make two 10-iamonds of the same shape? Formulate this question as an exact cover problem.

Verified: no
Solve time: 1m44s

Solution

Let the four pentiamonds be $P_1,P_2,P_3,P_4$. A pentiamond occupies five unit triangles of the triangular lattice, so the four pieces together occupy

$$ 4\cdot 5=20 $$

unit triangles. The desired construction consists of two congruent regions of ten unit triangles each, with each region tiled by two of the pentiamonds.

The difficulty is that the shape of the $10$-iamond is not known in advance. Therefore the exact cover instance must include all possible candidate shapes rather than assuming a particular shape.

Enumeration of candidate $10$-iamonds

A $10$-iamond is a connected set of ten unit triangles of the triangular lattice. Since the final object is made from four fixed pentiamonds, only finitely many shapes need be considered.

Generate a finite list

$$ \mathcal{S}={S_1,S_2,\ldots,S_m} $$

of all possible $10$-triangle regions that can occur as one half of a solution. For each $S_i$, include all translated, rotated, and reflected placements of that shape in a fixed coordinate system. For each placement, also consider the corresponding congruent second copy. Thus a candidate target consists of an ordered pair

$$ (S_i,g(S_i)), $$

where $g$ is a symmetry of the triangular lattice followed by a translation.

For each such candidate pair, construct an exact cover instance. The union of all these finite instances is equivalent to the original question.

Exact cover columns

Fix a candidate pair

$$ (S_i,g(S_i)). $$

The columns of the exact cover matrix are of three kinds.

  1. Piece columns.

For each physical pentiamond introduce a column

$$ p_1,p_2,p_3,p_4 . $$

A row using pentiamond $P_r$ covers the column $p_r$.

  1. Triangle columns for the first $10$-iamond.

For every unit triangle $t\in S_i$, introduce a column

$$ a_t . $$

  1. Triangle columns for the second $10$-iamond.

For every unit triangle $u\in g(S_i)$, introduce a column

$$ b_u . $$

Rows

A row represents one legal placement of one pentiamond inside one of the two target regions.

If a placement of $P_r$ occupies triangles

$$ t_1,t_2,t_3,t_4,t_5 $$

of $S_i$, the corresponding row contains $1$'s in

$$ p_r,a_{t_1},a_{t_2},a_{t_3},a_{t_4},a_{t_5}. $$

If a placement of $P_r$ occupies triangles

$$ u_1,u_2,u_3,u_4,u_5 $$

of $g(S_i)$, the row contains $1$'s in

$$ p_r,b_{u_1},b_{u_2},b_{u_3},b_{u_4},b_{u_5}. $$

These are all the rows of the exact cover instance for the candidate pair.

Correctness of the formulation

Suppose an exact cover exists for one of these instances. The four piece columns force the selected rows to use each pentiamond exactly once. The columns $a_t$ force the selected placements assigned to the first region to cover every triangle of $S_i$ exactly once. Similarly, the columns $b_u$ force the second region $g(S_i)$ to be covered exactly once. Hence the four pentiamonds tile two congruent $10$-iamonds.

Conversely, suppose the four pentiamonds can be arranged to form two $10$-iamonds of the same shape. The shape of one of the two regions is some $S_i$ in the enumeration, and the second region is a translated, rotated, or reflected copy $g(S_i)$. Select the four rows corresponding to the four pentiamond placements in this arrangement. Every piece column is covered once, every triangle column of the first region is covered once, and every triangle column of the second region is covered once. Therefore these rows form an exact cover.

Thus the original question is equivalent to asking whether at least one of the finitely many exact cover instances, one for each candidate congruent pair of $10$-iamonds, has a solution.

The formulation does not assume the shape of the $10$-iamond in advance. The congruence condition is enforced by the enumeration of candidate pairs $S_i,g(S_i)$, rather than by an external symmetry condition imposed after the fact. The problem can therefore be solved directly by Algorithm X or another exact cover algorithm. $\square$