TAOCP 7.2.2.1 Exercise 234

Let the board be $n \times n$, and let the center be $\left(\frac{n+1}{2}, \frac{n+1}{2}\right).$ For a queen placed at $(i,j)$, the cost is $8d(i,j)^2,$ and in the standard geometric interpretation u...

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.1: Dancing Links

Exercise 234. [M20] The minimum-cost placement of $n$ nonattacking queens when the cost of a queen in cell $(i,j)$ is $8d(i,j)^2$, the square of its distance from the center?

Verified: no
Solve time: 2m27s

Solution

Let the board be $n \times n$, and let the center be

$\left(\frac{n+1}{2}, \frac{n+1}{2}\right).$

For a queen placed at $(i,j)$, the cost is

$8d(i,j)^2,$

and in the standard geometric interpretation used in this section, $d(i,j)^2$ is the squared Euclidean distance to the center, hence

$d(i,j)^2 = \left(i-\frac{n+1}{2}\right)^2 + \left(j-\frac{n+1}{2}\right)^2.$

Thus the total cost of a placement $Q$ of $n$ nonattacking queens is

$$ C(Q) = 8 \sum_{(i,j)\in Q} \left[\left(i-\frac{n+1}{2}\right)^2 + \left(j-\frac{n+1}{2}\right)^2\right]. $$

In any nonattacking placement of $n$ queens on an $n \times n$ board, each row contains exactly one queen and each column contains exactly one queen. Therefore, as $(i,j)$ ranges over all queen positions, the multiset of row indices is ${1,2,\dots,n}$ and the multiset of column indices is also ${1,2,\dots,n}$. Hence the sum splits into two independent parts,

$$ C(Q) = 8 \left(\sum_{i=1}^n \left(i-\frac{n+1}{2}\right)^2 + \sum_{j=1}^n \left(j-\frac{n+1}{2}\right)^2 \right), $$

so

$$ C(Q) = 16 \sum_{i=1}^n \left(i-\frac{n+1}{2}\right)^2. $$

The expression on the right depends only on $n$, not on the choice of the permutation underlying the placement or on the diagonal constraints.

To evaluate the sum, write $c = \frac{n+1}{2}$. Then

$$ \sum_{i=1}^n (i-c)^2 = \sum_{i=1}^n i^2 - 2c \sum_{i=1}^n i + n c^2. $$

Using the identities

$$ \sum_{i=1}^n i = \frac{n(n+1)}{2}, \qquad \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}, $$

and substituting $c = \frac{n+1}{2}$ gives

$$ \sum_{i=1}^n (i-c)^2 = \frac{n(n+1)(2n+1)}{6}

  • (n+1)\frac{n(n+1)}{2}
  • n\frac{(n+1)^2}{4}. $$

Factoring $n(n+1)$ yields

$$ \sum_{i=1}^n (i-c)^2 = n(n+1)\left(\frac{2n+1}{6} - \frac{n+1}{2} + \frac{n+1}{4}\right). $$

With common denominator $12$, the bracket becomes

$$ \frac{4(2n+1) - 6(n+1) + 3(n+1)}{12} = \frac{8n+4 - 6n - 6 + 3n + 3}{12} = \frac{5n+1}{12}. $$

Thus

$$ \sum_{i=1}^n (i-c)^2 = \frac{n(n+1)(5n+1)}{12}. $$

Substituting into the cost expression,

$$ C(Q) = 16 \cdot \frac{n(n+1)(5n+1)}{12} = \frac{4}{3} n(n+1)(5n+1). $$

Since this value is independent of the particular nonattacking placement, every feasible solution attains the same cost, and no placement can yield a smaller value.

$\boxed{\frac{4}{3} n(n+1)(5n+1)}$

This completes the proof. ∎