TAOCP 7.2.2.1 Exercise 366
Let $\mathcal{S}$ denote the set of all solutions produced by the construction in Exercise 365.
Section 7.2.2.1: Dancing Links
Exercise 366. ▶ [25] [25] Improve the construction of the previous exercise by taking advantage of symmetry to cut the number of solutions in half. (When $m = 4$ there will now be $4 + 4$ solutions; when $m = 4$ and $n = 5$: $2 + 2 + 2 + 1 + 1$ solutions. Hint: A motley dissection is never identical to its left-right reflection, so we needn't visit both.)
Verified: yes
Solve time: 1m17s
Solution
Let $\mathcal{S}$ denote the set of all solutions produced by the construction in Exercise 365. Each solution $S \in \mathcal{S}$ is a motley dissection, hence a collection of options, or equivalently a set of geometric pieces whose union forms the target rectangle.
Let $R$ denote the horizontal reflection of the rectangle. This induces a map on solutions by applying $R$ to every constituent piece of a solution $S$, producing a new solution $R(S)$. Since reflection is an involution on the rectangle, $R(R(S)) = S$ holds for every $S$.
The hypothesis states that a motley dissection is never identical to its left-right reflection, so $R(S) \ne S$ for every $S \in \mathcal{S}$. Therefore each orbit of the action generated by $R$ on $\mathcal{S}$ has size exactly $2$, consisting of ${S, R(S)}$.
Fix a total order on all solutions induced lexicographically by a canonical encoding of each dissection as a sequence of choices in the construction from Exercise 365. This encoding is well-defined because each solution corresponds to a unique sequence of options selected by the backtracking procedure. Extend this order to compare any pair $S$ and $R(S)$.
Define the restricted solution set
$$ \mathcal{S}^\star = { S \in \mathcal{S} \mid S \le R(S) }. $$
For every $S \in \mathcal{S}$, exactly one of $S \le R(S)$ or $R(S) < S$ holds because the total order is antisymmetric and total. Hence at least one element of each pair ${S, R(S)}$ belongs to $\mathcal{S}^\star$.
If both $S \le R(S)$ and $R(S) \le R(R(S)) = S$ held, antisymmetry of the order would imply $S = R(S)$, contradicting the hypothesis. Therefore exactly one element of each orbit lies in $\mathcal{S}^\star$.
It follows that $\mathcal{S}^\star$ contains exactly half the elements of $\mathcal{S}$.
To implement this restriction within the construction of Exercise 365, modify the backtracking search so that when a complete solution $S$ is produced, it is output only if the canonical encoding of $S$ is not larger than the encoding of its reflection $R(S)$. Since this condition depends only on the completed solution, it does not alter feasibility during partial construction and therefore preserves correctness of the search while eliminating exactly one representative from each reflected pair.
This completes the proof. ∎