TAOCP 7.2.2.1 Exercise 24
An $n$-queens solution is a permutation $p$ of ${1,\dots,n}$ such that queens are placed at $(i,p(i))$ and no two attack each other.
Section 7.2.2.1: Dancing Links
Exercise 24. [20] With Algorithm X, find all solutions to the $n$ queens problem that are unchanged when they're rotated by (a) 180°; (b) 90°.
Verified: yes
Solve time: 2m
Solution
An $n$-queens solution is a permutation $p$ of ${1,\dots,n}$ such that queens are placed at $(i,p(i))$ and no two attack each other. The geometric symmetries act on these placements by mapping lattice points.
(a) Rotation by $180^\circ$
The $180^\circ$ rotation maps $(i,j)$ to $(n+1-i,n+1-j)$. A solution is invariant under this rotation exactly when
$$ (i,p(i)) \Longleftrightarrow (n+1-i,n+1-p(i)). $$
Hence for every $i$,
$$ p(n+1-i)=n+1-p(i). $$
This identity determines the permutation on row pairs ${i,n+1-i}$.
If $n$ is even, the rows split into $n/2$ disjoint pairs. Choosing $p(i)=j$ for $1\le i\le n/2$ forces $p(n+1-i)=n+1-j$. Thus each assignment on a representative row determines its partner uniquely, and no additional freedom remains.
If $n$ is odd, the middle index $m=(n+1)/2$ satisfies $n+1-m=m$, hence the constraint becomes $p(m)=m$. The center square must be occupied by a queen. The remaining rows still form $(n-1)/2$ independent pairs with the same coupling rule.
Non-attacking constraints (columns and diagonals) must hold simultaneously for all chosen representatives. In particular, selecting a value $p(i)=j$ removes the column pair ${j,n+1-j}$ and enforces diagonal consistency with the forced companion assignment.
Thus every $180^\circ$-invariant solution corresponds exactly to a selection of one row from each pair ${i,n+1-i}$ together with a compatible assignment of distinct column pairs, subject to the usual diagonal restrictions induced by the paired placement rule, and conversely every such selection extends uniquely to a full solution via
$$ (i,p(i)),\ (n+1-i,n+1-p(i)). $$
This completes the characterization for $180^\circ$ symmetry. ∎
(b) Rotation by $90^\circ$
The $90^\circ$ rotation maps $(i,j)$ to $(j,n+1-i)$. Invariance requires that every queen lies in a full orbit under repeated application of this map.
Starting from $(i,j)$, repeated rotation produces
$$ (i,j)\to (j,n+1-i)\to (n+1-i,n+1-j)\to (n+1-j,i)\to (i,j). $$
Hence every orbit has size $4$ unless it is fixed by a nontrivial power of the rotation.
A fixed point of the $90^\circ$ rotation satisfies
$$ (i,j)=(j,n+1-i), $$
so $i=j$ and $i=n+1-i$, giving $i=j=(n+1)/2$. This occurs only when $n$ is odd, and yields the single central square as a possible singleton orbit.
No orbit of size $2$ exists, since $(i,j)=(n+1-i,n+1-j)$ implies $180^\circ$ invariance, which contradicts the $90^\circ$ constraint unless the configuration is already fixed by the full rotation group.
Thus every noncentral queen belongs to a 4-element orbit
$$ (i,j),\ (j,n+1-i),\ (n+1-i,n+1-j),\ (n+1-j,i), $$
and a solution is determined by choosing one representative from each orbit together with enforcing that all four induced positions are valid and mutually nonattacking.
In permutation form, the condition implies
$$ p(p(i)) = n+1-i \quad\text{and hence}\quad p^{-1}(i)=n+1-p(i), $$
so $p$ is completely determined by its action on a set of orbit representatives, and each assignment propagates through a 4-cycle of row and column indices.
If $n$ is odd, the central queen at $(m,m)$ with $m=(n+1)/2$ is fixed and contributes a singleton orbit; all other rows are partitioned into pairs $(i,n+1-i)$ whose images are forced into corresponding column pairs, and the resulting assignments must satisfy the usual diagonal constraints across all four induced positions.
If $n$ is even, all orbits have size $4$, and the entire solution is obtained by selecting a set of representatives in a fundamental quarter region, for example indices satisfying $1\le i\le n/2$ and $i\le j\le n+1-i$, with each choice generating exactly four queens and consuming four rows and four columns.
In both parity cases, the $90^\circ$-invariant solutions are exactly those exact covers whose option sets are closed under the 4-cycle induced by rotation, so that Algorithm X restricted to orbit representatives generates each solution once and only once. ∎