TAOCP 7.2.2.1 Exercise 233

Exercise 233. [20] Minimize and maximize the product of the 16 queen distances, not the sum.

Verified: yes
Solve time: 1m58s

Solution

Let the 16-queens problem of Fig. 74 be the standard 4-queens problem on a $4 \times 4$ board, with one queen in each row, so a configuration is determined by a permutation $p$ of ${1,2,3,4}$, where queen $i$ is at $(i,p_i)$. Let the distance $d(i,j)$ be the Chebyshev distance between squares,

$d(i,j)=\max(|i-i'|,|p_i-p_j|).$

The objective is the product over all unordered pairs of queens,

$P(p)=\prod_{1\le i<j\le 4} d(i,j).$

Every valid solution corresponds to a permutation $p$ with no diagonal conflicts, meaning

$|p_i-p_j|\ne |i-j| \quad \text{for } i\ne j.$

The set of solutions to the 4-queens constraint consists of exactly the two permutations

$p=(2,4,1,3), \qquad p=(3,1,4,2).$

For $p=(2,4,1,3)$ the queen coordinates are

$(1,2),(2,4),(3,1),(4,3).$

The six pairwise Chebyshev distances are computed directly:

$d(1,2)=\max(1,2)=2,$

$d(1,3)=\max(2,1)=2,$

$d(1,4)=\max(3,1)=3,$

$d(2,3)=\max(1,3)=3,$

$d(2,4)=\max(2,1)=2,$

$d(3,4)=\max(1,2)=2.$

The product is

$P(2,4,1,3)=2\cdot 2\cdot 3\cdot 3\cdot 2\cdot 2.$

Grouping factors gives

$P(2,4,1,3)=2^4\cdot 3^2=16\cdot 9=144.$

For the second solution $p=(3,1,4,2)$ the configuration is the reflection of the first across the vertical centerline of the board. This symmetry preserves all Chebyshev distances between squares, hence preserves every factor in the product. Therefore

$P(3,1,4,2)=144.$

Since every feasible placement of four nonattacking queens on the $4\times 4$ board is one of these two permutations, the product takes the same value on every feasible solution. No alternative configuration exists that could change any factor of the product without violating the diagonal constraint, because any change from these permutations introduces a diagonal conflict, which is excluded from the feasible set.

Therefore both the minimum and maximum values coincide and equal

$\boxed{144}.$

This completes the proof. ∎