TAOCP 7.2.2.1 Exercise 366
Edit Let the construction of Exercise 363 be regarded as a rooted search tree.
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: no
Solve time: 2m06s
Edit
Solution
Let the construction of Exercise 363 be regarded as a rooted search tree. Each leaf of this tree is a faultfree motley dissection. The left-right reflection operation gives an involution
[ D\longmapsto \rho(D) ]
on the leaves of this tree. The hint states that no motley dissection is fixed by this involution, so
[ D\neq \rho(D) ]
for every leaf (D). Consequently the leaves occur in disjoint pairs
[ {D,\rho(D)}. ]
The improvement is to choose one member of each such pair during the construction.
Assign to every dissection (D) a canonical code (c(D)). The code is obtained from the recursive construction itself: list the successive choices made in the construction in the order in which they are made, using the same ordering of choices as in Exercise 363. The reflected dissection has its own code (c(\rho(D))). Since the construction code uniquely determines the dissection, and since (D\neq \rho(D)), the two codes are different.
Modify the construction of Exercise 363 as follows. Whenever a completed faultfree dissection (D) is obtained, retain it only when
[ c(D)<c(\rho(D)) ]
in lexicographic order. Otherwise discard it.
This is a symmetry reduction because the test is made only after the dissection has been completely determined. Therefore it cannot discard a dissection merely because of a comparison between incomplete partial constructions. No assumption about how reflection acts on partial recursive choices is needed.
We now prove that this modified construction gives exactly one representative from every reflection class.
First, at least one representative is retained. Given any faultfree motley dissection (D), the two codes
[ c(D),\qquad c(\rho(D)) ]
are distinct, so exactly one of the two inequalities
[ c(D)<c(\rho(D)) ]
and
[ c(\rho(D))<c(D) ]
holds. Hence exactly one of (D) and (\rho(D)) passes the test.
Second, no two different retained dissections can be reflections of each other. If both (D) and (\rho(D)) were retained, we would have simultaneously
[ c(D)<c(\rho(D)) ]
and
[ c(\rho(D))<c(D), ]
which is impossible. Thus every reflection pair contributes exactly one output.
Therefore the modified construction enumerates the faultfree motley dissections up to left-right reflection, with no duplicate representatives. The number of solutions is exactly half the number produced by the construction of Exercise 363, because the hint guarantees that there are no exceptional dissections fixed by reflection.
Hence the former collections of solutions are replaced by their reflection classes. In particular, the four solutions of each orientation for (m=4) become
[ 4+4, ]
and for (m=4,\ n=5) the reflection classes occur as
[ 2+2+2+1+1. ]
The construction has therefore been improved by using left-right symmetry to remove one member of every reflection pair.