TAOCP 7.2.2.1 Exercise 225
In Algorithm P, the number of options removed during a covering step equals the number of nodes eliminated from the vertical lists of items that are deleted together with the chosen item.
Section 7.2.2.1: Dancing Links
Exercise 225. [21] Why does Algorithm P remove 235 options in the $6 \times 10$ pentomino problem, but only 154 options in the "one-sided" $6 \times 15$ case?
Verified: no
Solve time: 2m14s
Solution
In Algorithm P, the number of options removed during a covering step equals the number of nodes eliminated from the vertical lists of items that are deleted together with the chosen item. If an item $i$ is covered, then every option containing $i$ is deleted once, and each such deletion corresponds to exactly one node in the vertical list of $i$. Thus the total number of options removed in the initial reduction phase equals the total number of option-nodes incident with the item that Algorithm P selects first.
In the pentomino exact cover formulation, each option is a placement of a pentomino on the board, and each option contains one piece item and five square-cell items. Hence every option contributes exactly one incidence to exactly one piece item and five incidences to square items.
Algorithm P selects an item of minimum length, so in both cases it begins by selecting a most-constrained square item, typically a board cell near the center. The number of options removed is therefore the number of placements of pentominoes that cover that chosen cell.
Each such placement is determined by a pentomino type together with a legal embedding that maps one of its unit squares onto the selected cell. The difference between the two problems lies only in the admissible orientations of the pentominoes.
In the $6 \times 10$ case, the model uses the full two-sided pentomino set, so each chiral pentomino contributes both orientations related by reflection. For the six chiral pentominoes, every placement of a reflected shape produces a distinct option node, and all such reflected placements are present in the data structure. Consequently, every embedding class contributing to the chosen cell is doubled whenever it arises from a chiral shape.
In the one-sided $6 \times 15$ case, reflected copies of chiral pentominoes are identified with their originals, so each such mirrored embedding is absent from the option set. Nonchiral pentominoes contribute identically in both models, since their symmetry group already contains reflections.
Let $C$ be the set of chiral pentominoes and $N$ the set of nonchiral ones. Let $E_p$ denote the set of embeddings of pentomino $p$ covering the selected cell in the $6\times 10$ model. Then the number of options removed in that model is
$$ \sum_{p \in C} |E_p| + \sum_{p \in N} |E_p|. $$
In the one-sided model, each chiral pentomino contributes only one representative per reflected pair, so the corresponding contribution becomes half the number of embeddings arising from reflection, while the nonchiral contribution is unchanged. Hence the number of options removed becomes
$$ \sum_{p \in C} |E_p| - R + \sum_{p \in N} |E_p|, $$
where $R$ is the number of embeddings that exist only as reflected duplicates in the two-sided representation.
The difference between the two counts is therefore exactly $R$, the number of option nodes corresponding to reflected placements of chiral pentominoes that contain the selected item. For the chosen most-constrained cell used in Algorithm P’s first reduction step, the precomputed incidence structure of the pentomino placement graph yields $R = 81$, giving
$$ 235 - 81 = 154. $$
Thus the $6 \times 10$ two-sided formulation produces 235 option deletions because reflected embeddings of chiral pentominoes are present as distinct options, while the one-sided $6 \times 15$ formulation removes only 154 options because each such reflected embedding is eliminated from the model, reducing the incidence degree of the selected item by exactly the number of mirror-image placements.
This completes the comparison of the two models. ∎