Greedy Queens and the Golden Ratio

One queen per column, as low as possible

Number the rows and columns of a quarter-infinite chessboard $0,1,2,\dots$, with the origin at the lower left. Put a queen at the origin. Then, in column $1$, column $2$, and so on, put a queen in the lowest square that no earlier queen attacks along a row, a diagonal or an antidiagonal.

This is OEIS A275895. Antti Karttunen introduced the positive-integer version, A065188, in 2001.Writing $q_n$ for the row of the queen in column $n$, the rule produces $$(q_0,q_1,q_2,\dots )=(0,2,4,1,3,8,10,12,14,5,\dots ).$$ Each earlier queen attacks at most three squares of a column, so some square is always free and every column gets a queen. Less obviously, every row eventually gets one too: Lemma 4 shows that $n\mapsto q_n$ is a permutation of $\mathbb{N}$.

Step through the rule below. In the highlighted column, a cross marks each square that an earlier queen attacks, and the gold square is the lowest one left. Hover overTap a cross, or a row number, to see the queen responsible.

A queen is upper if it lies above the diagonal $y=x$ and lower if it lies below. Let the rule run for a while and a pattern appears: The upper queens climb steeply, the lower ones more gently, and both families seem to follow straight lines.

The queens never stray far from two lines

Here $\varphi =(1+\sqrt{5})/2\approx 1.618$, and $1/\varphi =\varphi -1\approx 0.618$.Dekking, Shallit and Sloane conjectured that the upper and lower queens stay within a bounded distance of the lines $y=\varphi x$ and $y=x/\varphi$, where $\varphi$ is the golden ratio. The paper proves it.

Theorem 1

For every $n\ge 1$, $$\begin{array}{rlrl}\left|q_n-n\varphi \right|& <\frac{5}{\varphi }\approx 3.09& & \text{if }{q}_n>n,\\ |q_n-\frac{n}{\varphi }|& <4+\frac{5}{\varphi }\approx 7.09& & \text{if }{q}_n<n.\end{array}$$

From far away the queens look like two straight rays, as in the picture at the top of this page. The figure below subtracts the rays: For each column $n$ it plots how far the queen lies above or below its line. Over a thousand columns or a million, the points fill two thin horizontal strips that do not widen.

Knuth states his ranges in $1$-indexed coordinates, $s(c)=q_{c-1}+1$; the figure converts them. See the remark at the end of Section 3.Knuth's dashed ranges contain every point of the figure, but by themselves they are observations, not theorems. The gold lines come from the paper's second theorem, which sharpens the constants of the first.

Theorem 2

For every $n\ge 1$, $$\begin{array}{rlrl}\frac{19\sqrt{5}-49}{8}& <q_n-n\varphi <\sqrt{5}-1& & \text{if }{q}_n>n,\\ 15-8\sqrt{5}& <q_n-\frac{n}{\varphi }<13-4\sqrt{5}& & \text{if }{q}_n<n;\end{array}$$ numerically, rounding outward, $-0.8144<q_n-n\varphi <1.2361$ and $-2.8886<q_n-n/\varphi <4.0558$.

The gold lines lie inside Knuth's dashed ranges, so his ranges hold in every column, not only in the first $10^9$. Chapter 10 follows its proof (Section 6.6), which reuses the states of the finite check of Chapter 9. The new bounds are close to the truth: In the first $10^{11}$ columns, the highest upper queen comes within $0.004$ of its gold line, and the lowest lower queen within $0.001$ of its gold line.

The rest of this page follows the proof of Theorem 1, which has two halves. A counting argument (Chapters 3 to 5) derives the golden lines from one bound on the lower queens. A finite computation and an induction (Chapters 6 to 9) prove that bound. The map below shows how the pieces fit; each box links to its chapter. Chapter 10 then proves Theorem 2 with a second contraction.

First, the upper queens, which are much simpler than the lower ones.

Upper queens take the diagonals in order

Number the upper queens $1,2,3,\dots$ from left to right. The upper diagonals $y-x=1,2,3,\dots$ are used in the same order.

Lemma 3

The $k$th upper queen lies on the $k$th upper diagonal: If it is in column $n$, its row is $n+k$.

The identity is implicit in Knuth's program infty-queens.The proof is an induction. Only upper queens lie on upper diagonals, and the first $k-1$ of them hold diagonals $1$ to $k-1$, so the $k$th upper diagonal is still free. When the $k$th upper queen is placed in column $n$, those $k-1$ diagonals block rows $n+1$ to $n+k-1$ of that column. Every earlier queen lies below and to the left of the square $(n,n+k)$, so none of them shares its row or its antidiagonal, and the greedy rule takes it.

Write $U(n)$ for the number of upper queens in columns $1$ to $n$. An upper queen in column $n$ is the $U(n)$th, so it sits in row $n+U(n)$: The upper queens are determined by the single count $U$. In the figure below, each curve joins an upper queen's column to its row. The $k$th curve lands $k$ places to the right of where it starts, so the curves never cross.

The rows that the curves miss are exactly the lower rows, and the figure shows why they are easy to count. Upper queens in columns before $j$ land below row $j+U(j-1)$, and the later ones land above it, so that row is the $j$th lower row. This is a case of the Lambek–Moser theorem on complementary sequences.

The lower queens themselves are another matter. Their rows are not in increasing order, and nothing as simple as Lemma 3 places them.

One bound on the lower queens

Number the lower queens $1,2,3,\dots$ from left to right. The $j$th lower queen, at $(x_j,y_j)$, lies on the lower diagonal $y-x=-d_j$, and $d_j=x_j-y_j$ is its magnitude. If lower queens used the lower diagonals in order, as upper queens do, we would have $d_j=j$. They do not, but they come close.

Lemma 6 (bounded diagonal discrepancy)

For every $j\ge 1$, $|d_j-j|\le 4$.

The paper calls this bound the heart of its result. Chapter 5 shows how it forces the golden ratio, and Chapters 7 to 9 show how it is proved. In the figure, each strand runs from the $j$th lower queen to its magnitude $d_j$. Strands cross only near neighbors, and none travels more than four places.

The values $3$ and $4$ never occur. This is no accident of the first million columns: The checked states of Chapter 9 show that $d_j-j\le 2$ always (Section 6.6). The same checked states also show that the least unused magnitude never falls more than four behind $j$, so the magnitudes $d_j$ run through every positive integer; with Lemma 3, every diagonal of the board holds exactly one queen (Corollary 19).

How one bound forces the golden ratio

Let $L(n)=n-U(n)$ count the lower queens in columns $1$ to $n$. Sorting the lower queens by row, with Lemma 5, turns the bound of Chapter 4 into an estimate for the columns of the lower queens (Lemma 7). From that estimate, Lemma 8 derives a relation between the counts $U(n)$ and $U(L(n))$: $${\eta }_n=n-2U(n)+U(L(n))\text{has}|{\eta }_n|\le 5.$$

Why does this force $\varphi$? Suppose that $U(n)$ were exactly $\theta n$ for some slope $\theta$. Then $L(n)=(1-\theta )n$, and $${\eta }_n=(1-\theta -{\theta }^2)n.$$ Drag the slope (drag the gold number sideways, or focus it and use the arrow keys): with $\theta =$ 0.600, the coefficient $1-\theta -{\theta }^2$ is 0.0400, which is positive. A bounded ${\eta }_n$ needs the coefficient to vanish, so ${\theta }^2+\theta =1$ and $\theta =1/\varphi$.

The paper makes this exact. Put $\epsilon (n)=U(n)-n/\varphi$. Substituting into the definition of ${\eta }_n$, and using $2+1/\varphi ={\varphi }^2$, gives $$\epsilon (n)=\frac{\epsilon (L(n))-{\eta }_n}{{\varphi }^2}.$$ The error at $n$ is a copy of the error at $L(n)$, shrunk by the factor ${\varphi }^2\approx 2.618$, plus a new term of at most $5/{\varphi }^2$. Follow $n\to L(n)\to L(L(n))\to \cdots$ down to $0$, where the error is $0$. The new terms add up to less than $$5({\varphi }^{-2}+{\varphi }^{-4}+{\varphi }^{-6}+\cdots )=\frac{5}{\varphi }\approx \mathrm{3.09.}$$

For an upper queen, $q_n-n\varphi =U(n)-n/\varphi =\epsilon (n)$ exactly, because $q_n=n+U(n)$ and $\varphi -1=1/\varphi$. That is the upper half of Theorem 1. For a lower queen, $q_n-n/\varphi$ differs from $\epsilon (n)$ by $j-d_j$, which Chapter 4 bounds by $4$; that is the lower half.

Four symbols per index

To prove the bound of Chapter 4, the paper describes the board by a word. For each index $i\ge 1$ it records two bits: The column bit $u_i$ is $1$ when column $i$ holds an upper queen, and the row bit $b_i$ is $1$ when row $i$ does. The queen word is $\sigma ={\sigma }_1{\sigma }_2{\sigma }_3\cdots$, with symbols $${\sigma }_i=2u_i+b_i\in \{0,1,2,3\}.$$

Before column $n$, the symbols ${\sigma }_1,\dots ,{\sigma }_{n-1}$ are already fixed: Each column $i<n$ is filled, and an upper queen in row $i$ must lie in a column less than $i$. The two bits are what the proof needs to know about upper queens. By Lemma 3, the upper queens are determined by counts of column bits, and a lower candidate square can be blocked by an upper queen in its row, which is a row bit.

The step in column $n$ uses the word in two places. It reads near the least unused row $m$, where the lower candidates are, and it writes the new symbol ${\sigma }_n$. Since $m$ is about $n/\varphi$, the two places drift apart as $n$ grows. The proof stores only short pieces at each end, $H_{\mathrm{in}}$ and $Q$ near $m$ and $H_{\mathrm{out}}$ just before $n$, and has to cope without the long stretch in between.

A calculation on eight records

The greedy step in column $n$ consults every earlier queen, and the board keeps growing. To prove a bound that holds in every column, the paper replaces the board by a local state (Definition 11): eight records, measured from three references that move as the queens are placed. They are the column $n$, the least unused row $m$, and the least unused lower-diagonal magnitude $d$.

Lower candidates. Every row below $m$ is used, and so is every lower diagonal of magnitude less than $d$. A lower queen in column $n$ must therefore go in a row from $m$ to $n-d$, at an offset $r=0,1,\dots ,w$ above $m$, where $w=n-m-d$. The sets $R$, $D$ and $A$ record the rows, diagonals and antidiagonals of the earlier lower queens that could still attack these candidates, as offsets from $m$, $d$ and $n+m$. The records also give the discrepancy directly: If the new queen is the $j$th lower queen, at offset $r$, then $$d_j-j=w-r-|D|.$$ So the heart of the proof reduces to bounds on two records. If $w\le 4$ and $D\subseteq \{1,2,3,4\}$ in every column, then $|d_j-j|\le 4$.

Upper queens. Rather than store their positions, the state stores pieces of the queen word. The input history $H_{\mathrm{in}}$ and the queue $Q$ start near index $m$ and answer the candidates' row and antidiagonal tests. The output history $H_{\mathrm{out}}$ holds the last twelve symbols before $n$. One more number, $z=n-m-U(m-1)$, locates column $n$ among the upper queens, and this is all that Proposition 13 and Proposition 14 need.

The calculation. From the records alone, the calculation (Algorithm 1) finds the queen in column $n$ and the records before column $n+1$, in four stages. Choose the queen: Test the lower candidates from the lowest up, first against the lower queens recorded in $R$, $D$ and $A$, then against the upper queens, using the stored symbols of the queen word; if every candidate is attacked, the queen is upper. Write the new symbol ${\sigma }_n$, and check that the history graph allows it after $H_{\mathrm{out}}$. Move the references: If the new queen fills row $m$ or the diagonal of magnitude $d$, that reference advances to the next unused one, and the offsets shift to match. Move the words: The symbols that $m$ has passed leave $Q$ for $H_{\mathrm{in}}$, and $H_{\mathrm{out}}$ gains ${\sigma }_n$.

The calculation never uses $n$, $m$ or $d$. It reads only the records, so it can be run on any state, whether or not the state comes from a real board. Sometimes a test needs a symbol beyond the end of $Q$, which the records do not hold. The calculation then makes a request to the history graph of Chapter 8, which lists the symbols that may come next, and when the graph allows several it branches and follows each one. Column $53$ is an example.

Condition 16 and Lemma 17

Suppose the records before column $n$ satisfy $$w\le 4,-4\le z\le 5,R,D\subseteq \{1,2,3,4\},$$ that $U(m-1)\ge 12$ and $m+|Q|\le n$, and that ${\sigma }_1\cdots {\sigma }_{n-1}$ follows the history graph. Then the branch that answers every request with the actual symbol never stops, places the actual queen in column $n$, and produces the actual records before column $n+1$.

The figure above follows this actual branch. The bounds do two jobs. They keep every requested symbol within six places of $m$, and together with $U(m-1)\ge 12$ they put $n$ at least eight places beyond $m$, so every requested symbol is already determined. They also ensure that no unstored upper queen can affect a test. The condition $U(m-1)\ge 12$ holds from column $30$ on, since $m$ never decreases. What remains is to show that the bounds hold in every column. Since the calculation cannot tell which branch is the actual one, the paper checks them for every branch.

What may come next

The records keep the queen word only near index $m$ and just before $n$, and the two ends drift apart: $n-m$ is $16$ before column $41$ and $381$ before column $1000$. So when the calculation needs a symbol past the end of $Q$, the records do not have it. The paper's answer is a finite history graph (Definition 12). Its vertices are words of twelve symbols, and an edge $W\stackrel{s}{\to }{W}^{\prime }$ says that the symbol $s$ may follow the twelve symbols of $W$; the destination $W^{\prime }$ drops the oldest symbol and appends $s$. A request is answered by the edges leaving the twelve symbols just read. At the other end, the output check confirms that the new symbol ${\sigma }_n$ labels an edge leaving $H_{\mathrm{out}}$.

The figure places each vertex by its bits. Its column bits, newest first, give the horizontal coordinate as a binary fraction, and its row bits give the vertical one. The four quadrants hold the windows ending in $0$, $1$, $2$ and $3$. Each quadrant splits in the same way by the symbol before, and so on. An edge appends a symbol, which halves both coordinates and moves the point toward the corner of the new symbol: It is one jump of the "chaos game".

The paper finds the graph by running the calculation itself (Algorithm 2). It starts from the eighteen windows of ${\sigma }_1\cdots {\sigma }_{29}$. Whenever a branch computes a symbol with no edge, it adds the edge instead of failing, and it repeats over all the states found so far until nothing new is added. Thirteen explorations add edges, and the fourteenth adds none. The construction only finds the graph. The proof holds the finished graph fixed and checks it.

The graph allows more than the queen word does. It has windows that never occur in $\sigma$ and edges that $\sigma$ never uses, because the state omits most of the board, so its records and the symbols it reads can combine in ways the board never produces. That is the price of a finite description, and the check in the next chapter has to cover all of these combinations.

A finite check, and an induction

Start from the state before column $30$, computed directly from the first thirty queens. Run the calculation on it, following every branch; run it on every successor; and continue until no new state appears (Algorithm 3). The check has no depth limit, and it never drops a branch.

Proposition 18 (finite verification)

With the history graph fixed, the calculation from the state before column $30$ reaches $7014$ states and $8327$ state-graph edges. Every branch passes the output check, and every successor satisfies Condition 16.

You can run the check yourself. The code behind it is a TypeScript port of the companion repository's verifier, and it reproduces the counts of Section 6.

An induction (Section 6.4) now follows the actual queens forever. Suppose that, before column $n$, the actual records are one of the checked states and ${\sigma }_1\cdots {\sigma }_{n-1}$ follows the history graph. Since $U(m-1)\ge 12$ from column $30$ on, Lemma 17 applies, and the actual branch carries out the actual step. By the check, its new symbol passes the output check, and its successor is again a checked state. Both assumptions therefore hold before column $n+1$. At each lower queen from column $30$ on, the records give $d_j-j=w-r-|D|$ with $0\le w-r\le 4$ and $|D|\le 4$; the lower queens before column $30$ are checked directly. This proves the bound of Chapter 4.

Why twelve symbols?

Shorter windows give a smaller graph, but it allows too much. The calculation can then read combinations of symbols that the board never produces, and some of them push the records out of bounds. Choose a length to rerun the construction in your browser.

A second contraction

The contraction of Chapter 5 charges every hop $n\to L(n)$ its worst case, a new term as large as $5/{\varphi }^2$. Those worst cases never line up, and the queens use only a third of the band they allow: For the upper queens of Chapter 2, $q_n-n\varphi$ stays between $-0.82$ and $1.24$, inside a band of $\pm 3.09$. To prove Theorem 2, the paper uses a second contraction. It hops from column $n$ to the least unused row $m\approx n/\varphi$, and it keeps track of which worst cases can occur together. The error is the same as in Chapter 5: $\epsilon (n)=U(n)-n/\varphi$, where $U(n)$ counts the upper queens in columns $1$ to $n$.

Lemma 21 (one-step error identity)

Before column $n\ge 1$, with least unused row $m$ and records $w$, $z$ and $D$, $$\epsilon (n-1)=Y-\frac{\epsilon (m-1)}{\varphi },$$ where $Y=w-|D|+1-z/\varphi$.

The records count the queens. The lower queens in columns $1$ to $n-1$ use every lower diagonal of magnitude less than $d$, and the $|D|$ magnitudes recorded in $D$, so there are $d-1+|D|$ of them. With $w=n-m-d$, this gives $U(n-1)=m+w-|D|$. The record $z=n-m-U(m-1)$ ties column $n$ to the count at $m$. Writing both counts through $\epsilon$ and using $1/\varphi +1/{\varphi }^2=1$ leaves the identity.

Compare it with Chapter 5. This hop goes only to $m\approx n/\varphi$, not to $L(n)\approx n/{\varphi }^2$, so it shrinks the earlier error only by $\varphi$. It also flips the sign: A high error at $m$ pushes the error at $n$ down. The new term $Y$ depends only on the state before column $n$, and over the $7014$ checked states of Chapter 9 it takes just $19$ values, from $(\sqrt{5}-5)/2\approx -1.38$ to $1$. Bounding $Y$ and $\epsilon (m-1)$ separately would give only $|\epsilon |\le 1.38{\varphi }^2\approx 3.62$, which is worse than Theorem 1.

The two terms are not independent. The twelve symbols before index $m$ are the input history of the state $S_n$ before column $n$, and they are also the output history of the state $S_m$ before column $m$: $$H_{\mathrm{in}}(S_n)=H_{\mathrm{out}}(S_m).$$ So one window of the queen word constrains both the state at $n$, and with it $Y$, and the error at $m-1$. The paper therefore gives every vertex $W$ of the history graph, a possible window of twelve symbols, an interval $[\mathrm{lo}(W),\mathrm{hi}(W)]$. It is meant to contain $\epsilon (n-1)$ whenever the twelve symbols before column $n$ are $W$.

Suppose the interval holds before column $m$, at the window $V=H_{\mathrm{in}}(S_n)$. The identity sends it to an interval for $\epsilon (n-1)$: The map $x\mapsto Y-x/\varphi$ flips it, shrinks it by $\varphi$ and shifts it by $Y$. The bounds are consistent (Definition 22) if, at every state $S$ of the state graph, this image lands inside the interval at $W=H_{\mathrm{out}}(S)$: $$\begin{array}{rl}\mathrm{lo}(W)& \le Y(S)-\frac{\mathrm{hi}(V)}{\varphi },\\ \mathrm{hi}(W)& \ge Y(S)-\frac{\mathrm{lo}(V)}{\varphi },\end{array}$$ with $V=H_{\mathrm{in}}(S)$. That is one finite condition per state. Consistent bounds that hold before columns $30$ to $48$ then hold before every column, by strong induction (Lemma 23): From column $49$ on, the least unused row $m$ is at least $30$, so the interval at $V$ already holds before column $m$, and consistency carries it to column $n$.

Where do the intervals come from? Applying the identity again at $m$, then at the least unused row before $m$, and so on, writes the error as an alternating sum along the chain, $$\epsilon (n-1)=Y(S_{n_0})-\frac{Y(S_{n_1})}{\varphi }+\frac{Y(S_{n_2})}{{\varphi }^2}-\cdots ,$$ in which each state has as input history the output history of the next. The paper takes $\mathrm{lo}(W)$ and $\mathrm{hi}(W)$ to be the least and greatest such sums over every chain of states that the state graph allows from $W$. It computes them in rounds, adding one state to the chains at a time: $$\begin{array}{rl}{\mathrm{lo}}_{t+1}(W)& =\underset{S}{\min }(Y(S)-\frac{{\mathrm{hi}}_t(H_{\mathrm{in}}(S))}{\varphi }),\\ {\mathrm{hi}}_{t+1}(W)& =\underset{S}{\max }(Y(S)-\frac{{\mathrm{lo}}_t(H_{\mathrm{in}}(S))}{\varphi }),\end{array}$$ over the states $S$ with output history $W$, starting from ${\mathrm{lo}}_0={\mathrm{hi}}_0=0$. The rest of the chain enters with a minus sign, so the least sum takes the greatest rest, and the greatest sum the least. The rounds converge geometrically, and their limits are consistent, since each state is one of the terms in the minimum and the maximum. Each limit is attained by one state, and following those states runs around a cycle; solving around the cycle gives the exact values, all in $\mathbb{Q}(\sqrt{5})$.

The last step reads off Theorem 2. For an upper queen in column $n$, $q_n-n\varphi =\epsilon (n)$ (Chapter 5), and this lies in the interval of the window ${\sigma }_{n-11}\cdots {\sigma }_n$, which ends with the symbol of an upper column. For a lower queen at offset $r$ above $m$, the definition of $z$ gives $$q_n-\frac{n}{\varphi }=r+\frac{1}{{\varphi }^2}-\frac{z+\epsilon (m-1)}{\varphi },$$ with $\epsilon (m-1)$ in the interval of $V=H_{\mathrm{in}}(S_n)$. So the bounds of Theorem 2 follow from a check of every window that ends in an upper column, and of every lower choice of every state.

Proposition 24 (finite verification of the window bounds)

There are consistent window bounds, with values in $\mathbb{Q}(\sqrt{5})$, that hold before columns $30$ to $48$, such that (i) every window whose last symbol has column bit $1$ has $\frac{19\sqrt{5}-49}{8}\le \mathrm{lo}(W)$ and $\mathrm{hi}(W)\le \sqrt{5}-1$, and (ii) at every lower choice of every state $S$, at offset $r$, with $V=H_{\mathrm{in}}(S)$, $$\begin{array}{c}15-8\sqrt{5}\le r+\frac{1}{{\varphi }^2}-\frac{z+\mathrm{hi}(V)}{\varphi },\\ r+\frac{1}{{\varphi }^2}-\frac{z+\mathrm{lo}(V)}{\varphi }\le 13-4\sqrt{5}.\end{array}$$

You can run this check too. It explores the state graph as in Chapter 9, computes the window bounds exactly, and checks every condition in exact arithmetic, as the companion repository's knuth_ranges.py does.

The intervals reach the constants, but the queens do not, so the inequalities of Theorem 2 are strict. The upper constants have a positive coefficient of $\sqrt{5}$, and $q_n-n\varphi =(q_n-\frac{n}{2})-\frac{n}{2}\sqrt{5}$ has a negative one. The lower constants could equal $q_n-n/\varphi$ only at $n=16$ or $n=8$, and the columns before $49$ are checked directly. The queens do come close: In the first $10^{11}$ columns, the highest upper queen comes within $0.004$ of $\sqrt{5}-1$, and the lowest lower queen within $0.001$ of $15-8\sqrt{5}$. Since the gold lines lie inside Knuth's dashed ranges, his observation holds in every column.

The queens as a game

The greedy queens also solve a game. A single queen stands on the board. Two players take turns moving it any number of squares to the left, down, diagonally down and to the left, or diagonally up and to the left, and the player who cannot move loses. Every move decreases $2x+y$, so the game always ends.

The losing positions, from which the player to move loses against best play, are exactly the greedy queens $(x,q_x)$. No move joins two of them, because the queens do not attack one another. From any other square $(x,y)$ there is a move to one. If $y>q_x$, move down to $(x,q_x)$. If $y<q_x$, the greedy rule passed over $(x,y)$ because an earlier queen attacks it, and that queen is one move away.

In the language of combinatorial game theory, the queens are the P-positions, where the previous player, the one who just moved, wins. Every other square is an N-position, where the next player wins.These two facts give the winning strategy: Move to a greedy queen every time. Your opponent then always stands on a queen, and every move from it lands on a square that is not a queen; from there you move back onto a queen. The game cannot last forever, so in the end your opponent stands on a queen with no move at all, the origin $(0,0)$, and loses. The strategy is also the only way to win against an opponent who plays perfectly. Move once to a square that is not a queen, and your opponent moves to a queen and plays the same strategy against you.

Combinatorial game theory gives every square a Sprague–Grundy value $G(x,y)$: the least nonnegative integer that is not the value of a square one move away. The losing squares are those with $G=0$, the greedy queens, and Theorem 1 locates this zero set. The positive values are harder to describe. Every value occurs exactly once in each row and each column; Dekking, Shallit and Sloane conjectured that it also occurs exactly once on each diagonal, and Corollary 19 proves this for the value $0$.

A million queens from a few dozen records

The local description also gives a fast way to compute the queens. The calculation for column $n$ reads the queen word only up to about index $m+6$, and $m\approx n/\varphi$. So the symbols it needs can be regenerated by a second copy of the same calculation, running behind the first. That copy needs symbols near $n/{\varphi }^2$, supplied by a third copy, and so on. Each copy receives the actual symbols and follows the actual branch, so nothing is guessed and the history graph is not needed.

When the first copy reaches column $N$, the second is near $N/\varphi$, the third near $N/{\varphi }^2$, and so on until a copy is still within its first eighteen columns, so the chain has about ${\log }_{\varphi }(N/48)$ copies: $22$ for a million queens. Their combined work is about $$N(1+\frac{1}{\varphi }+\frac{1}{{\varphi }^2}+\cdots )={\varphi }^{2}N\approx 2.618N$$ queen placements, and no copy keeps more than a handful of small records.

The paper goes further. Whenever a copy pauses for input, its records take one of only $300$ values, so the calculation can be compiled into a table that places several queens per lookup (Section 7.3), and the copies pass symbols four at a time through buffers (Section 7.4). The C implementation in the companion repository generates ten billion queens in about $25$ seconds using $1.76$ MiB of memory. A bit-packed adaptation of Knuth's program takes about $49$ seconds and $6.1$ GiB.

Read further

Everything on this page is computed in your browser from the definitions. The queens come from the greedy rule. The explorer, the history graph and the check use a TypeScript port of the companion repository's verifier, which reproduces the counts of Section 6 and the positions of the copies in Figure 9 of the paper. The page needs no server and works offline.