TAOCP 7.2.2.1 Exercise 37

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: 3m54s