TAOCP 7.2.2.1 Exercise 38

Exercise 38. [M25] $[M25]$ Devise an efficient way to compute the sequence $\langle g_n \rangle$ of exercise 37.

Verified: no
Solve time: 2m21s

Solution

Let $g_n$ denote the lexicographically smallest solution of the $\infty$ queens problem. Thus $g_n$ is the row occupied by the queen in column $n$, and the defining condition is

$$ g_i\ne g_j,\qquad |g_i-g_j|\ne |i-j| $$

for all distinct positive integers $i,j$.

A direct greedy computation chooses $g_k$ as the least positive integer that is not already occupied and does not attack any of the queens in columns $1,\ldots,k-1$. The inefficiency in the direct method is the repeated scanning of all small integers. The improvement is to maintain the set of legal candidates dynamically.

For every $k$, define the forbidden set

$$ F_k={g_i:i<k}\cup{g_i+k-i:i<k}\cup{g_i-k+i:i<k,\ g_i-k+i>0}. $$

The first part of $F_k$ excludes rows already occupied. The second part excludes rows attacked by a diagonal of slope $1$. The third part excludes rows attacked by a diagonal of slope $-1$. Therefore the greedy choice is exactly

$$ g_k=\min(\mathbb Z^+\setminus F_k). $$

The computation can be organized by storing the positive integers in increasing order in an ordered priority queue $Q$. Initially,

$$ Q=(1,2,3,\ldots). $$

The entries removed from $Q$ are precisely the integers that have become forbidden. After computing $g_k$, the three families of newly forbidden positions are

$$ g_k,\qquad g_k+t,\qquad g_k-t\quad(1\le t<k,\ g_k-t>0), $$

because a queen placed in column $k$ attacks those rows in the columns that have already been considered or in future columns.

The resulting algorithm is

$$ \begin{array}{ll} \mathrm{E1}.&\text{Initialize }Q\text{ with the increasing sequence }1,2,3,\ldots .\[2mm] \mathrm{E2}.&\text{For }k=1,2,\ldots,\text{ repeatedly delete from the front of }Q\text{ every value}\ &\text{already marked forbidden, and set }g_k\text{ equal to the first remaining value.}\[2mm] \mathrm{E3}.&\text{Insert the marks}\ &g_k,\ g_k+1,\ldots,g_k+k-1,\ g_k-1,\ldots,g_k-k+1\ &\text{into the forbidden structure, omitting nonpositive values.}\[2mm] \mathrm{E4}.&\text{Continue with }k+1. \end{array} $$

The forbidden structure in E3 does not need to store the whole set explicitly. Since only membership tests and insertion of integers are required, a hash table gives expected constant time per operation. The number of newly inserted values at stage $k$ is

$$ 1+(k-1)+(g_k-1\text{ values among the negative-diagonal candidates that remain positive}), $$

and only the first $k$ positive values can affect the search for $g_{k+1}$. Hence the algorithm may discard forbidden values below the current minimum candidate after they have been passed. A balanced tree or indexed bit vector gives deterministic performance.

To prove correctness, suppose that the algorithm has produced

$$ g_1,g_2,\ldots,g_{k-1} $$

correctly. The invariant is that the forbidden structure contains exactly the positive integers $r$ for which a queen in column $k$ and row $r$ would attack one of the previously placed queens.

For every $i<k$, the row $g_i$ is forbidden because two queens would share a row. The row $g_i+k-i$ is forbidden because

$$ (g_i+k-i)-g_i=k-i, $$

which equals the difference between the column numbers. The row $g_i-k+i$ is forbidden because

$$ g_i-(g_i-k+i)=k-i, $$

so the other diagonal is attacked. These are exactly the possible attacks involving the new column $k$. Therefore the least value not in the forbidden structure is precisely the least row that can be assigned to column $k$ without violating the queens condition.

The induction hypothesis gives the correctness of the first $k-1$ choices. The preceding argument proves the correctness of the $k$th choice, so the algorithm produces the lexicographically smallest valid sequence.

The data structure changes only by adding the rows and diagonals generated by each new queen. No backtracking is required, because the lexicographically first choice at every column extends to the lexicographically first infinite solution.

This completes the proof.

∎