TAOCP 7.2.2.1 Exercise 235

Exercise 235. ▶ [21] Solve the problem of Fig. 74 using the (integer) costs $$4d(i,j)^4$.

Verified: yes
Solve time: 2m07s

Solution

Let the board be $16 \times 16$ with rows and columns indexed by $i,j \in {1,\dots,16}$. Let the center coordinate be $c=\frac{17}{2}$. Knuth’s distance is

$d(i,j)^2=(i-c)^2+(j-c)^2,$

so the cost function is

$$4d(i,j)^4 = 4\big((i-c)^2+(j-c)^2\big)^2.$

A placement of 16 nonattacking queens corresponds to a permutation $\pi$ of ${1,\dots,16}$, with one queen in each $(i,\pi(i))$. The total cost is

$C(\pi)=\sum_{i=1}^{16} 4\big((i-c)^2+(\pi(i)-c)^2\big)^2.$

Expand the square:

$C(\pi)=4\sum_{i=1}^{16}\Big((i-c)^4+(\pi(i)-c)^4+2(i-c)^2(\pi(i)-c)^2\Big).$

Since $\pi$ is a permutation,

$\sum_{i=1}^{16}(\pi(i)-c)^4=\sum_{j=1}^{16}(j-c)^4,$

so both quartic sums are constant over all permutations. The only term depending on $\pi$ is

$S(\pi)=\sum_{i=1}^{16}(i-c)^2(\pi(i)-c)^2.$

Define $a_i=(i-c)^2$. Then $a_i$ depends only on $|i-c|$, hence

$a_1<a_2<\cdots<a_8=a_9<\cdots<a_{16},$

with symmetry $a_i=a_{17-i}$.

The problem reduces to minimizing

$S(\pi)=\sum_{i=1}^{16} a_i a_{\pi(i)}.$

By the rearrangement inequality for nonnegative sequences, the sum $\sum a_i a_{\pi(i)}$ is minimized when the largest entries of one sequence are paired with the smallest entries of the other. Since both sequences are identical and sorted in increasing order of $a_i$, the minimum occurs when the order is reversed:

$\pi(i)=17-i.$

This pairing matches outer rows with outer columns in opposite order and pairs values symmetrically about the center.

For this permutation,

$S_{\min}=\sum_{i=1}^{16} a_i a_{17-i}.$

Any deviation from the reversal produces at least one inversion pair $(i<j)$ with $a_i<a_j$ but $a_{\pi(i)}<a_{\pi(j)}$, and swapping their images strictly decreases $S(\pi)$, which forces the reversed permutation as the unique minimizer up to ties caused by $a_i=a_{17-i}$.

The corresponding placement is the anti-diagonal configuration

$(i,;17-i), \quad i=1,\dots,16.$

This configuration satisfies the nonattacking constraint and achieves the minimum cost.

The maximum of $S(\pi)$ occurs when the sequences are similarly ordered, giving

$\pi(i)=i,$

which corresponds to the main diagonal placement

$(i,i), \quad i=1,\dots,16.$

Since all other terms in $C(\pi)$ are permutation-independent, these two permutations also determine the global minimum and maximum of the total cost.

Therefore the minimum-cost solution of Fig. 74 under cost $$4d(i,j)^4$ is the anti-diagonal placement.

$\boxed{\text{Place queens at }(i,17-i)\text{ for }i=1,\dots,16}$

This completes the solution. ∎