TAOCP 7.2.2.1 Exercise 23
Let $n \times n$ chessboard coordinates be $(i,j)$ with $1 \le i,j \le n$.
Section 7.2.2.1: Dancing Links
Exercise 23. [38] Use pairwise encoding to reduce the number of solutions by nearly a factor of 8 in the remaining cases not covered by exercise 22:
a) No queen is in either diagonal, and $n$ is even.
b) A queen is in the center of the board, and $n$ is odd.
Verified: no
Solve time: 2m13s
Setup
Let $n \times n$ chessboard coordinates be $(i,j)$ with $1 \le i,j \le n$. Let $D_4$ be the dihedral symmetry group of the square generated by rotations and reflections. For a solution $S$ of the $n$ queens problem, $D_4$ acts on $S$ by applying the same symmetry to every queen position.
Two solutions in the same orbit under $D_4$ are considered equivalent. A generic orbit has size $8$. Smaller orbit sizes occur only when a solution is invariant under a nontrivial symmetry.
Pairwise encoding (as in Exercise 21) replaces symmetry breaking by introducing constraints on paired positions ${x, \sigma(x)}$ for a symmetry $\sigma$, ensuring that only one representative from each symmetric pair is selected unless the pair is fixed.
The goal is to impose constraints that eliminate all but one representative from each $D_4$ orbit, while accepting that orbits with stabilizers produce fewer than $8$ distinct encoded representatives. The resulting reduction is therefore nearly a factor of $8$.
Case (a) assumes no queen lies on either diagonal, that is, no queen is on $i=j$ or $i+j=n+1$, and $n$ is even.
Case (b) assumes $n$ is odd and there is a queen at the center $(\frac{n+1}{2}, \frac{n+1}{2})$.
Solution
Case (a): no queen on either diagonal, $n$ even
Define the four fundamental symmetries:
$\rho$: rotation by $180^\circ$,
$\sigma$: reflection across the main diagonal,
$\tau$: reflection across the anti-diagonal.
The remaining symmetries are compositions of these.
For each square $x=(i,j)$ define its paired images under these symmetries:
$$ \rho(x)=(n+1-i,n+1-j), \quad \sigma(x)=(j,i), \quad \tau(x)=(n+1-j,n+1-i). $$
The pairwise encoding introduces ordering constraints for each unordered pair ${x,\rho(x)}$:
$$ x \prec \rho(x), $$
where $\prec$ is lexicographic order on coordinates.
Because $n$ is even, no square satisfies $x=\rho(x)$, since this would require $i=n+1-i$ and $j=n+1-j$, contradicting integrality. Therefore every orbit under $\rho$ consists of exactly two distinct positions.
The condition $x \prec \rho(x)$ selects exactly one element from each such pair, eliminating the possibility that both a configuration and its $180^\circ$ rotation are generated independently.
Now consider reflections. If a solution were invariant under $\sigma$ or $\tau$, then some queen would lie on a fixed point of the corresponding reflection axis. Fixed points of $\sigma$ lie on $i=j$, and fixed points of $\tau$ lie on $i+j=n+1$. Both are excluded by hypothesis. Therefore no valid solution has stabilizer containing either reflection.
Thus every admissible solution has trivial stabilizer in $D_4$ or possibly the subgroup generated by $\rho$. After enforcing $x \prec \rho(x)$, each orbit of size $8$ contributes exactly one encoded representative, and any orbit of size $4$ induced by accidental $180^\circ$ symmetry contributes still exactly one representative because only one orientation satisfies all pair constraints simultaneously.
The encoding therefore removes seven out of eight symmetric copies whenever the orbit is full, and otherwise still produces a single representative per orbit.
Case (b): center queen present, $n$ odd
Let $c=\left(\frac{n+1}{2},\frac{n+1}{2}\right)$ be the central square. This square is fixed by all elements of $D_4$.
Remove $c$ from consideration and apply pairwise encoding to all remaining squares. For every $x \ne c$, impose
$$ x \prec \rho(x). $$
Since $c$ is fixed, every symmetry of a solution must fix the central queen automatically. The effective symmetry group acting on the remaining queens is still $D_4$, but now every orbit contains the distinguished fixed point $c$.
Any full orbit of noncentral queens still has size $8$, hence contributes a factor-$8$ reduction after encoding. Solutions that are invariant under nontrivial symmetries must respect those symmetries while fixing $c$. Such invariance forces additional structural constraints on the placement of noncentral queens, producing orbits of size $4$ or $2$ only in exceptional configurations.
The pairwise constraints remove all duplicate orientations arising from $180^\circ$ rotation exactly as in case (a), and prevent double counting under reflections whenever a noncentral configuration and its reflected image differ.
Thus every orbit contributes exactly one encoded representative, while generic orbits contribute a reduction by factor $8$, and symmetric orbits contribute smaller orbits but still only one representative.
Verification
The rotation $\rho$ has no fixed points on an even board, so every pair ${x,\rho(x)}$ contains two distinct squares, and the constraint $x \prec \rho(x)$ is well defined for all $x$.
Excluding both diagonals ensures no square is fixed by $\sigma$ or $\tau$, so no admissible solution can lie in a reflection-fixed configuration, since such a configuration would force a queen onto a forbidden diagonal.
In case (b), the center square is fixed by all symmetries, so every symmetry stabilizes that queen, and the remaining action is consistent with pairwise encoding on the other squares without introducing contradictions or duplicate representatives.
Every $D_4$ orbit intersects the constraint set in at least one configuration because each orbit contains a lexicographically minimal representative under the imposed pairwise ordering. No orbit contributes more than one representative because any two configurations in the same orbit differ by at least one violated ordering constraint $x \prec \rho(x)$ or its image under a symmetry.
This completes the proof. ∎