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 3 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 after Proposition 8.The gold lines come from Proposition 21, which sharpens the constants of the theorem to $$\begin{array}{rlrl}1-\frac{4}{\varphi }& <q_n-n\varphi <\frac{2}{\varphi }& & \text{if }{q}_n>n,\\ -2-\frac{4}{\varphi }& <q_n-\frac{n}{\varphi }<4+\frac{1}{\varphi }& & \text{if }{q}_n<n.\end{array}$$ Knuth's dashed ranges contain every point, but they are observations, not theorems. The gold lines are proved, and their upper ends lie at or below Knuth's, so the upper halves of Knuth's ranges hold in every column; for the lower queens the two upper ends coincide, at $4+1/\varphi$. Whether the lower halves hold in every column is still open.

The rest of this page follows the proof, 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.

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 2

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 2 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 5 (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, which the paper uses to sharpen its constants (Proposition 21). 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 2, every diagonal of the board holds exactly one queen (Corollary 18).

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 4, turns the bound of Chapter 4 into an estimate for the columns of the lower queens (Lemma 6). From that estimate, Lemma 7 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 kick 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 kicks 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 2, 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 10): 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 12 and Proposition 13 need.

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 it needs a symbol beyond the end of $Q$, which the records do not hold: for the row count that gives the new row bit, for a candidate high above $m$, for an upper queen whose antidiagonal must be checked, or for the search for the next unused row. It then makes a request to the history graph of Chapter 8, which lists the symbols that may come next. When the graph allows several, the calculation branches and follows each one. Column $53$ is an example.

Condition 15 and Lemma 16

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 11). 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 17 (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 15.

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 16 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.

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.

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 18 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 5 of the paper. The page needs no server and works offline.