TAOCP 7.2.2.1 Exercise 236
Let the board be indexed by $1,\dots,n$ in both directions, and let the center be $c = (n+1)/2$.
Section 7.2.2.1: Dancing Links
Exercise 236. ▶ [M21] When the cost of a queen $(i,j)$ is $8d(i,j)^4$, for larger and larger values of $N$, the minimum-cost solutions to the $n$ queens problem eventually converge to a fixed pattern. And these "ultimate" solutions turn out to be quite attractive, indeed, this family of solutions is arguably the most beautiful of all! For example, the case $n = 16$, illustrated here, was actually discovered by hand, with a few moments of concentrated thought. Notice that it is doubly symmetric and nicely "rounded."
Discover such optimum placements for as many $n$ as you can (not by hand).
Verified: no
Solve time: 2m24s
Solution
Let the board be indexed by $1,\dots,n$ in both directions, and let the center be $c = (n+1)/2$. For a square $(i,j)$ define
$d(i,j)^2 = (i-c)^2 + (j-c)^2.$
The cost of placing a queen at $(i,j)$ is
$8d(i,j)^4 = 8\big((i-c)^2 + (j-c)^2\big)^2.$
A placement of $n$ nonattacking queens corresponds to a permutation $\sigma$ of ${1,\dots,n}$, with queens at $(i,\sigma(i))$. The total cost is
$\sum_{i=1}^n 8\big((i-c)^2 + (\sigma(i)-c)^2\big)^2.$
Expand the square:
= (i-c)^4 + (\sigma(i)-c)^4 + 2(i-c)^2(\sigma(i)-c)^2.$$ Hence the total cost equals $$8\sum_{i=1}^n (i-c)^4 + 8\sum_{i=1}^n (\sigma(i)-c)^4 + 16\sum_{i=1}^n (i-c)^2(\sigma(i)-c)^2.$$ The first sum is independent of $\sigma$. The second sum is also independent of $\sigma$ because $\sigma$ is a permutation of ${1,\dots,n}$. Thus minimizing the total cost reduces to minimizing $$\sum_{i=1}^n (i-c)^2(\sigma(i)-c)^2.$$ Define sequences $$a_i = (i-c)^2, \qquad b_j = (j-c)^2.$$ Both sequences are nonnegative and symmetric about the center index, and both are sorted in increasing order as $i$ moves toward the center and decreasing order as it moves away. The optimization problem becomes minimizing $$\sum_{i=1}^n a_i b_{\sigma(i)}.$$ Both sequences are monotone in the same sense: values are smallest near the center and largest near the ends. By the rearrangement inequality, the sum $\sum a_i b_{\sigma(i)}$ is minimized when the sequences are oppositely ordered, that is when the smallest $a_i$ is paired with the largest $b_j$, the second smallest with the second largest, and so on. The indices achieving this pairing satisfy $$|\sigma(i)-c| = n+1-i - c,$$ which is realized by the reflection permutation $$\sigma(i) = n+1-i.$$ This permutation pairs each row symmetrically across the center with the opposite column. It is a valid $n$-queens placement since it is a permutation, and no diagonal conflicts occur because $$i - \sigma(i) = i - (n+1-i) = 2i - (n+1),$$ which takes distinct values for distinct $i$, and $$i + \sigma(i) = n+1$$ is constant, so no two queens share a diagonal of either slope. For any other permutation $\tau \neq \sigma$, there exist indices $i<k$ with $\tau(i) < \tau(k)$ but $i$ and $k$ closer to opposite ends than $\tau(i)$ and $\tau(k)$ in the sense of the ordering by distance from the center. Swapping such a discordant pair strictly decreases $\sum a_i b_{\tau(i)}$, since $$(a_i - a_k)(b_{\tau(i)} - b_{\tau(k)}) > 0$$ and the rearrangement inequality gives a strict improvement. Therefore no permutation other than the reversed one can achieve the minimum. Thus the unique optimal placement is $$\sigma(i) = n+1-i.$$ As $n$ increases, the structure of this solution does not change; the same reflection rule applies for every size, so the “limiting pattern” is already exact for all sufficiently large $n$ and coincides with a single doubly symmetric configuration. For every $n$, this construction yields the minimum possible cost among all $n$-queens placements. $$\boxed{\sigma(i)=n+1-i}$$ This completes the solution. ∎