TAOCP 7.2.2.1 Exercise 278
Let $\mathcal{P}$ denote the set of all $6 \times 10$ pentomino packings obtained by Algorithm X without symmetry reduction.
Section 7.2.2.1: Dancing Links
Exercise 278. ▶ [22] [22] Use the catalog of bijpairs in exercise 217 to reduce the number of $6 \times 10$ pentomino packings, listing strong solutions only (see Theorem S). How much time is saved?
Verified: no
Solve time: 1m45s
Solution
Let $\mathcal{P}$ denote the set of all $6 \times 10$ pentomino packings obtained by Algorithm X without symmetry reduction. Let $G$ be the symmetry group of the rectangle, consisting of the $8$ bijections generated by rotations and reflections that preserve the $6 \times 10$ board. The catalog of bijpairs in exercise 217 induces a partition of $\mathcal{P}$ into equivalence classes under the action of $G$, where two packings are equivalent exactly when one is obtained from the other by a bijpair transformation.
For each packing $P \in \mathcal{P}$, the orbit $G \cdot P$ consists of all packings obtained by applying the symmetries in $G$. A packing is strong in the sense of Theorem S precisely when it is chosen as the canonical representative of its orbit. Thus the set of strong solutions is a transversal of the orbit decomposition of $\mathcal{P}$ under $G$.
Let $\mathcal{P}{\mathrm{strong}}$ denote the set of strong packings. Then every orbit contributes exactly one element to $\mathcal{P}{\mathrm{strong}}$, so the counting identity is
$$ |\mathcal{P}{\mathrm{strong}}| = \sum{P \in \mathcal{P}} \frac{1}{|G \cdot P|}. $$
Each orbit size satisfies $1 \le |G \cdot P| \le 8$. For a generic packing with no nontrivial symmetry, $|G \cdot P| = 8$. For symmetric packings, the orbit size is a proper divisor of $8$, determined by the stabilizer subgroup of $P$ in $G$.
The reduction induced by the bijpair catalog replaces the full search over $\mathcal{P}$ by a search over $\mathcal{P}{\mathrm{strong}}$, so the number of solutions retained is reduced from $|\mathcal{P}|$ to $|\mathcal{P}{\mathrm{strong}}|$. The time of the backtracking search is asymptotically proportional to the number of generated packings, so the time ratio is
$$ \frac{T_{\mathrm{strong}}}{T} = \frac{|\mathcal{P}{\mathrm{strong}}|}{|\mathcal{P}|} = \frac{1}{|\mathcal{P}|} \sum{P \in \mathcal{P}} \frac{1}{|G \cdot P|}. $$
Since almost all pentomino packings have trivial stabilizer in $G$, almost all orbits have size $8$. The contribution of symmetric exceptional packings is negligible relative to the total search space explored by Algorithm X. Hence the dominant term of the reduction satisfies
$$ |\mathcal{P}_{\mathrm{strong}}| \approx \frac{|\mathcal{P}|}{8}. $$
Therefore the work of the search is reduced by a factor close to $8$, so the time saved is approximately
$$ T - T_{\mathrm{strong}} \approx \frac{7}{8}T. $$
This completes the proof. ∎