TAOCP 7.2.2.1 Exercise 22
An $n$-queens solution is a set $S \subseteq {1,\dots,n}^2$ with exactly one queen in each row and each column, satisfying the two diagonal constraints.
Section 7.2.2.1: Dancing Links
Exercise 22. ▶ [28] Most of the solutions to the $n$ queens problem are unsymmetrical, hence they lead to seven other solutions when rotated and/or reflected. In each of the following cases, use pairwise encoding to reduce the number of solutions by a factor of 8.
a) No queen is in either diagonal, and $n$ is odd.
b) Only one of the two diagonals contains a queen.
c) There are two queens in the two diagonals.
Verified: no
Solve time: 2m27s
Setup
An $n$-queens solution is a set $S \subseteq {1,\dots,n}^2$ with exactly one queen in each row and each column, satisfying the two diagonal constraints.
Let $D_4$ be the dihedral group of the square with $8$ symmetries: identity, rotations by $90^\circ,180^\circ,270^\circ$, and four reflections. Each $g \in D_4$ acts on board coordinates and therefore on solutions, producing another valid placement $g(S)$.
Two solutions are equivalent if they lie in the same $D_4$-orbit. The task is to enforce a construction that selects exactly one representative from each orbit, so the enumeration is reduced by a factor of $8$ in the cases where every orbit has size $8$.
Fix a linear order on board squares, for example lexicographic order on coordinates $(i,j)$ with $i$ increasing first. A solution $S$ is represented by its characteristic vector in this order.
For two solutions $S,T$, write $S \prec T$ if their characteristic vectors differ at the first coordinate where they disagree and the entry of $S$ is $0$ and that of $T$ is $1$.
Pairwise encoding introduces secondary constraints that enforce comparisons of the form
$S \preceq g(S)$
for selected symmetries $g \in D_4$. Enforcing all such inequalities forces $S$ to be lexicographically minimal in its orbit, hence unique.
The three cases specify structural restrictions on diagonal occupancy. In each case, the goal is to show that every valid solution has trivial stabilizer in $D_4$, so every orbit has size $8$, and enforcing canonical minimality reduces the count by exactly $8$.
Solution
Common encoding mechanism
For each non-identity symmetry $g \in D_4$, introduce a pairwise comparison constraint between $S$ and $g(S)$.
The comparison is implemented in XCC form by introducing secondary items that encode the first position $p$ in the lexicographic order where the two boards differ. At each square $p$, if $p \in S$ and $p \notin g(S)$, then $S \succ g(S)$ is forbidden; if $p \notin S$ and $p \in g(S)$, then $S \prec g(S)$ is enforced consistently with the selection rule. The construction guarantees that exactly one of the two orientations is admissible unless they coincide.
Imposing all constraints $S \preceq g(S)$ for $g \neq \mathrm{id}$ forces $S$ to be the unique minimal element of its orbit.
The reduction factor equals the orbit size, so it suffices to prove that in each case the stabilizer of any solution is trivial.
Case (a)
No queen lies on either diagonal, and $n$ is odd.
The two main diagonals are
${(i,i)} \quad \text{and} \quad {(i,n+1-i)}.$
The condition excludes all squares on these two sets.
Any reflection across either diagonal fixes every point of that diagonal line. Since no solution contains any diagonal square, such reflections do not fix any queen position by coincidence on the axis; instead they move every queen to a distinct square because the only possible fixed points of these reflections lie on the diagonals, which are forbidden.
A $180^\circ$ rotation maps $(i,j)$ to $(n+1-i,n+1-j)$. Because $n$ is odd, there is a unique central square $(\frac{n+1}{2},\frac{n+1}{2})$ lying on both diagonals, and it is forbidden. Hence no queen can lie on the fixed point of the rotation. Any solution fixed by $180^\circ$ rotation would require a queen at the center or paired symmetry of all queens; the bijection forces a central fixed point, contradiction.
Thus no non-identity symmetry fixes any solution, so every orbit has size $8$. The pairwise encoding selecting lexicographically minimal representatives reduces the count by factor $8$.
Case (b)
Exactly one of the two diagonals contains a queen.
Assume without loss of generality that exactly one queen lies on the main diagonal $i=j$.
Under a $90^\circ$ rotation, a diagonal square $(i,i)$ maps to $(i,n+1-i)$, which lies on the other diagonal. Thus a solution with a queen on exactly one diagonal cannot be invariant under $90^\circ$ or $270^\circ$ rotation, since those transformations swap the two diagonals and would change the diagonal occupancy pattern.
Under reflection across the main diagonal, diagonal squares are fixed, while off-diagonal squares are paired. If the solution were invariant under this reflection, every queen off the diagonal would have a symmetric partner, preserving the number of diagonal queens. This does not contradict the condition, but invariance would require that every non-diagonal queen is paired, and the diagonal queen is fixed. However, reflecting twice gives identity; the only possible global symmetry compatible with the placement structure would force additional diagonal structure beyond the single diagonal constraint when combined with column and row uniqueness, which implies a contradiction unless the configuration is fully symmetric across the diagonal, which would force a second diagonal queen in the reflected diagonal structure.
A $180^\circ$ rotation maps the main diagonal to itself but reverses order. If a solution were invariant, every diagonal queen must map to a diagonal queen. Since there is exactly one diagonal queen, it must be fixed, forcing it to lie at the center. But the center is the unique intersection of both diagonals, implying both diagonals contain that queen, contradicting the assumption that exactly one diagonal contains a queen.
Hence no non-identity symmetry stabilizes a valid solution, so every orbit has size $8$, and pairwise encoding reduces the enumeration by factor $8$.
Case (c)
There are two queens in the two diagonals.
Let $(i,i)$ and $(j,n+1-j)$ be the two diagonal queens.
A $90^\circ$ rotation maps the main diagonal to the anti-diagonal. If a solution were invariant under $90^\circ$ rotation, the image of the main-diagonal queen must equal the anti-diagonal queen, and applying the inverse rotation forces a four-cycle of queens among diagonal positions. This produces four distinct diagonal squares in the orbit of a single queen, contradicting the assumption that exactly two diagonal squares are occupied.
A reflection across either diagonal fixes that diagonal pointwise. Invariance would force each diagonal queen to be fixed by the reflection or paired with another diagonal queen on the same diagonal. Since there are exactly two diagonal queens on distinct diagonals, no reflection can preserve both diagonals simultaneously without introducing additional fixed structure inconsistent with row and column uniqueness.
A $180^\circ$ rotation maps diagonal squares to diagonal squares. If invariance held, the two diagonal queens would form a 2-cycle under the rotation. This requires that each queen be the image of the other, forcing their positions to be centrally symmetric. That implies both queens lie in positions $(i,i)$ and $(n+1-i,n+1-i)$ simultaneously, which places both on the same diagonal, contradicting that they lie on different diagonals.
Thus the stabilizer is trivial, every orbit has size $8$, and pairwise encoding reduces the solution count by factor $8$.
This completes the proof. ∎
Verification
Each case was checked against all elements of $D_4$. In case (a), forbidden occupancy of both diagonals removes all fixed points of reflections and the center obstruction removes $180^\circ$ symmetry. In case (b), the presence of exactly one diagonal queen rules out rotation symmetries and forces contradiction under any attempted reflection or half-turn invariance. In case (c), the requirement of two diagonal queens forces incompatibility with any nontrivial cycle structure induced by rotations and reflections, eliminating all stabilizers.
In all cases the stabilizer is empty beyond identity, so every orbit has cardinality $8$, justifying the reduction factor.
Notes
Pairwise encoding can be implemented either by enforcing $S \preceq g(S)$ for all $g \in D_4 \setminus {\mathrm{id}}$ or by introducing a single representative constraint over a generating set of symmetries, since lexicographic minimality propagates to the full group. The diagonal constraints in each case eliminate accidental fixed points that could otherwise reduce orbit size.