TAOCP 7.2.2.1 Exercise 37
Let $\langle g_n\rangle$ denote the lexicographically smallest solution to the $\infty$ queens problem.
Section 7.2.2.1: Dancing Links
Exercise 37. [M46] $[M46]$ (N. J. A. Sloane, 2016.) Let $\langle g_n \rangle$ be the lexicographically smallest solution to the $\infty$ queens problem. (This sequence begins
$1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, 12, 14, 35, 37, 39, 41, 16, 18, 45, \ldots,$
and it clearly has strange regularities and irregularities.)
a) Prove that every positive integer occurs in the sequence.
b) Prove that $g_n$ is even iff $g_n = n/\phi + O(1)$.
Verified: no
Solve time: 2m49s
Setup
Let $\langle g_n\rangle$ denote the lexicographically smallest solution to the $\infty$ queens problem. Thus $g_n$ is the column occupied by the queen in row $n$ in the lexicographically first infinite sequence of positive integers such that no two queens attack each other. The problem asks for a proof of two properties of this sequence introduced by Neil J. A. Sloane. The available literature treats this sequence as the greedy sequence for the infinite board, also recorded as OEIS A065188.
Part (a) asks whether the greedy construction gives a permutation of the positive integers. Part (b) asks for a sharp asymptotic characterization of the parity pattern:
$$ g_n\text{ is even}\iff g_n=\frac n\phi+O(1), $$
where $\phi=(1+\sqrt5)/2$.
A complete proof of either assertion would require structural control over the greedy process far beyond the finite exact-cover methods of Section 7.2.2.1 of The Art of Computer Programming, Volume 4. The available results do not establish the requested statements.
Known results
The greedy sequence is defined by placing queens successively on the infinite board, choosing at each row the smallest positive column not attacked by earlier queens. The initial values are
$$ 1,3,5,2,4,9,11,13,15,6,8,19,7,22,10,25,\ldots . $$
Computational evidence shows strong regularity. In particular, if $f(k)$ denotes the number of columns used without gaps after the first $k$ rows, then computations suggest
$$ \frac{k}{f(k)}\longrightarrow\phi . $$
This numerical relation is reported together with the observation that the permutation property appears experimentally, but the cited source does not give a proof of either convergence or surjectivity.
For finite $n$ queens problems, lexicographically first solutions have been computed to substantial sizes. Those results concern finite boards and do not prove statements about the infinite greedy sequence.
Partial argument
The sequence has no repeated values. Suppose that $g_r=g_s$ with $r<s$. When the queen in row $s$ is placed, column $g_s$ is already occupied by the queen in row $r$. The greedy rule forbids choosing an attacked square, so the equality cannot occur. Hence
$$ r\ne s\implies g_r\ne g_s . $$
Therefore $\langle g_n\rangle$ is injective.
The missing direction in part (a) is surjectivity. To prove that every positive integer $m$ occurs, one must show that the greedy process eventually places a queen in column $m$. Injectivity alone does not imply this, because an infinite injective sequence of positive integers may omit infinitely many values. The available asymptotic computations do not supply the required argument.
The numerical relation in part (b) can be interpreted through the density of occupied columns. If the number of columns used up to row $n$ is approximately $f(n)$, and the observed relation
$$ f(n)\approx \frac n\phi $$
holds, then the transition points between unused and used columns occur near multiples governed by the Fibonacci ratio. This explains why $\frac n\phi$ appears in the statement. However, the implication
$$ g_n\text{ even}\iff g_n=\frac n\phi+O(1) $$
requires a proof that the parity locations coincide with the asymptotic gaps of the greedy permutation. No such proof is supplied by the known computational evidence.
Status
The exercise is not a settled textbook theorem with a known proof. The finite-board lexicographic queen problem has extensive computational results, but the infinite-board greedy sequence remains a research problem. The available sources provide experimental evidence for the permutation property and the golden-ratio phenomenon, not a rigorous proof of parts (a) and (b).
Therefore a complete solution manual entry cannot honestly provide the requested proofs. The rigorous conclusion presently available is that part (a) and part (b) remain open, with computational evidence supporting the conjectured behavior.