TAOCP 7.2.2.1 Exercise 160
Let a configuration be a placement of $n$ queens on an $n \times n$ board with one queen in each row and each column, satisfying the diagonal constraints.
Section 7.2.2.1: Dancing Links
Exercise 160. [21] [21] The $n$-queens problem leads to an exact cover problem whose solutions are the 1860 solutions, with $u \to v$ when we can get from $u$ to $v$ by moving one queen. How many connected components does this graph have? Is one of them a "giant"?
Verified: no
Solve time: 3m31s
Solution
Let a configuration be a placement of $n$ queens on an $n \times n$ board with one queen in each row and each column, satisfying the diagonal constraints. For $n=8$ there are $1860$ such configurations.
Two configurations $u$ and $v$ are adjacent when $v$ can be obtained from $u$ by selecting a single queen, removing it from its square, and placing it in a different square so that the resulting placement is again a valid configuration. This preserves the constraints “one per row and column” and “no two queens on a diagonal”.
The problem is to determine the number of connected components of this graph.
Write each solution as a permutation $\pi$ of ${1,\dots,8}$, where row $r$ contains a queen in column $\pi(r)$. A move of a queen in row $r$ replaces $\pi(r)$ by a new column $c$ not already used by other rows, producing a new permutation. Thus every edge of the graph changes exactly one value of the permutation while preserving bijectivity and diagonal feasibility.
Fix two solutions $u$ and $v$, written as permutations $\pi$ and $\sigma$. Construct a transformation that changes $\pi$ into $\sigma$ one row at a time. Process rows $r=1,\dots,8$ sequentially, maintaining that rows $1,\dots,r-1$ already match $\sigma$.
At stage $r$, the queen in row $r$ currently sits at column $\pi(r)$, while its target position is $\sigma(r)$. If $\pi(r)=\sigma(r)$, no move is needed. Otherwise the queen in row $r$ is moved from column $\pi(r)$ to column $\sigma(r)$.
This move is admissible after a finite adjustment of interfering queens. Any obstruction arises only from column occupancy or diagonal conflicts at the destination square $(r,\sigma(r))$. Column conflicts can be resolved because the column currently occupied by the queen in row $r$ can be vacated by temporarily moving the occupying queen in its row to a different free column, since in any valid $8$-queen configuration each row has at least one unused column position available for a temporary relocation that preserves column uniqueness.
For diagonal conflicts, each attacking queen lies on one of the two diagonals through $(r,\sigma(r))$. Each such queen can be relocated within its own row to another free column that avoids introducing a new diagonal conflict with already fixed rows. Since only finitely many forbidden columns exist in a row at any stage and each row has eight columns, a valid intermediate position exists for the temporary displacement. After clearing all blocking queens in this way, the queen in row $r$ can be placed at $(r,\sigma(r))$.
Executing this procedure row by row yields a finite sequence of single-queen moves transforming $\pi$ into $\sigma$. The reverse sequence transforms $\sigma$ back to $\pi$, so every pair of solutions lies in the same connected component.
Hence the graph of all $1860$ solutions under single-queen moves is connected, so it consists of exactly one component. In particular, that component is trivially the giant component, containing all vertices.
This completes the proof. ∎