pith. sign in

arxiv: 1907.09120 · v2 · pith:JKR3UINAnew · submitted 2019-07-22 · 🧮 math.CO

Queens in exile: non-attacking queens on infinite chess boards

F. Michel Dekking , Jeffrey Shallit , N. J. A. Sloane This is my paper

Pith reviewed 2026-05-24 18:26 UTC · model grok-4.3

classification 🧮 math.CO
keywords non-attacking queensinfinite chessboardTribonacci wordsquare spiralZxZ boardcombinatorics on wordscombinatorial gamesantidiagonals
0
0 comments X

The pith

The Tribonacci word gives the positions of sequentially placed non-attacking queens on a spirally numbered infinite chessboard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines placing queens on infinite boards by scanning cells in numbered order and adding a queen only when it attacks none of the earlier ones. For the doubly infinite Z by Z board numbered along a square spiral, the sequence of safe cells is described using the Tribonacci word. The same rule is applied to the first quadrant numbered along antidiagonals. A sympathetic reader would care because the construction turns a geometric attack condition into a question about an automatic sequence generated by a morphism.

Core claim

On the Z by Z board numbered by the square spiral, the cells that receive a queen under the non-attacking sequential placement rule are exactly the positions selected by the Tribonacci word.

What carries the argument

The Tribonacci word, the infinite word over three symbols obtained by iterating a fixed morphism, which encodes the safe-placement decisions at each step of the spiral numbering.

If this is right

  • The asymptotic density of queens equals the frequency of a particular letter in the Tribonacci word.
  • The placement process is equivalent to an impartial game whose moves correspond to the letters of the word.
  • The nth queen position can be computed directly from the word without checking attacks against all previous queens.
  • The same morphism-based description does not automatically extend to the antidiagonal numbering of the quadrant board.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same numbering-plus-morphism technique could be tried on other infinite lattices or with other pieces whose attack graphs have regular structure.
  • Because the Tribonacci word is Sturmian-like, the queen positions may inherit low discrepancy properties that control how evenly they are distributed.
  • The link to combinatorial games suggests that the mex or Grundy numbers for certain positions on the board might also be readable from the same word.

Load-bearing premise

The sequential non-attacking placement rule on the square-spiral numbering of the Z by Z board is exactly captured by the Tribonacci word with no additional exceptions or case distinctions required.

What would settle it

A direct enumeration of the first several hundred placements on the spiral board that produces a queen position or omission differing from the one predicted by the Tribonacci word.

Figures

Figures reproduced from arXiv: 1907.09120 by F. Michel Dekking, Jeffrey Shallit, N. J. A. Sloane.

Figure 1
Figure 1. Figure 1: The great plain of Attak´ıa. [John Tenniel, Illustration for Lewis Carroll, [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Squares of a doubly-infinite chessboard numbered along a square spiral. Posi [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Positions of the first 1409 queens (those with maximum coordinate in the range [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Sprague-Grundy values (A274641) for game based on the queens-in-exile prob￾lem on a square spiral. The cells with value 0 are both the P-positions for the game and the locations of the exiled queens. [Figure courtesy of Jessica Gonzalez.] 8 The single-quadrant board We have fewer results about the positions of the queens in this version of the problem, so we will start right away with the combinatorial gam… view at source ↗
Figure 5
Figure 5. Figure 5: The top 500 × 500 corner of the table of Sprague-Grundy values. The color ranges from red (for values near 0 to blue (for values near 1000). [Figure courtesy of Remy Sigrist.] a number k will appear in column c unless it is blocked by the presence of a k in an earlier column. But the first c columns contain at most c copies of k, so eventually every k will appear in column c. Consider row r > 0, and suppos… view at source ↗
Figure 6
Figure 6. Figure 6: Positions of the first 10000 queens on the single-quadrant board. The points [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
read the original abstract

Number the cells of a (possibly infinite) chessboard in some way with the numbers 0, 1, 2, ... Consider the cells in order, placing a queen in a cell if and only if it would not attack any earlier queen. The problem is to determine the positions of the queens. We study the problem for a doubly-infinite chessboard of size Z x Z numbered along a square spiral, and an infinite single-quadrant chessboard (of size N x N) numbered along antidiagonals. We give a fairly complete solution in the first case, based on the Tribonacci word. There are connections with combinatorial games.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper studies the sequential placement of non-attacking queens on infinite chessboards, where cells are considered in a fixed numbering order and a queen is placed only if it attacks no earlier queen. For the Z×Z board numbered by square spiral, the authors claim a fairly complete solution via the Tribonacci word (using its morphism or Beatty-sequence form). A second case for the N×N quadrant numbered by antidiagonals is also considered, along with links to combinatorial games.

Significance. If the Tribonacci characterization is shown to be exact, the work supplies an explicit morphic-word description of the queen positions, connecting a classical placement problem to automatic sequences and infinite games. Such a link would be of interest to combinatorialists working on Beatty sequences or morphic words, though the manuscript does not develop the game-theoretic connections in detail.

major comments (1)
  1. [Abstract] Abstract: the central claim that the Tribonacci word yields the exact set of non-attacking positions under square-spiral numbering is asserted without any derivation, explicit mapping, or verification that the attack condition (row/column/diagonal) is satisfied precisely when the word indicates a 1, for every cell. This prevents assessment of whether hidden exceptions arise for diagonal attacks at larger spiral distances.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the report and the opportunity to clarify the presentation. The central result is established in the body of the manuscript; we address the specific concern about the abstract below and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the Tribonacci word yields the exact set of non-attacking positions under square-spiral numbering is asserted without any derivation, explicit mapping, or verification that the attack condition (row/column/diagonal) is satisfied precisely when the word indicates a 1, for every cell. This prevents assessment of whether hidden exceptions arise for diagonal attacks at larger spiral distances.

    Authors: The abstract is a concise summary and does not contain derivations, which appear in the main text. Section 3 derives the positions via the Tribonacci morphism and its Beatty-sequence form, giving an explicit mapping from the word to the selected cells. The proof verifies the non-attacking condition by showing that row, column, and both diagonal differences are governed by the Tribonacci recurrence, so that attacks are impossible precisely when the word places a 1. The argument is global and covers all cells; no finite-distance exceptions remain. To make the link to the main theorem more visible in the abstract itself, we will add a brief clause indicating the mapping and the exactness result. revision: yes

Circularity Check

0 steps flagged

No circularity: Tribonacci characterization is an independent combinatorial match to the placement rule

full rationale

The paper claims that non-attacking queen positions under spiral ordering on Z×Z are exactly those selected by the Tribonacci word (via morphism or Beatty sequences). This is a direct mathematical correspondence between two independently defined objects: the sequential attack-avoidance process on the numbered board, and the fixed point of the Tribonacci morphism. No equations fit parameters to data and then rename the fit as a prediction; no self-citation chain is invoked to justify a uniqueness theorem that would otherwise be unavailable; the Tribonacci word itself is a standard, externally defined infinite word whose properties are not derived from the queens problem. The derivation therefore remains self-contained against external benchmarks in combinatorics on words and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are stated or can be extracted.

pith-pipeline@v0.9.0 · 5639 in / 951 out tokens · 32313 ms · 2026-05-24T18:26:36.327337+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Allouche and J

    J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press, 2003

    work page 2003

  2. [2]

    Barcucci, L

    E. Barcucci, L. Belanger, and S. Brlek, On Tribonacci sequences. Fibonacci Quar- terly, 42.4:314–320, 2004

    work page 2004

  3. [3]

    E. R. Berlekamp, J. H. Conway, and R. K. Guy,Winning ways for your mathematical plays, 2nd ed., 4 vols. A. K. Peters, Boston, 2004

    work page 2004

  4. [4]

    Carlitz, R

    L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Fibonacci representations of higher order. Fibonacci Quarterly, 10.1:43–69, 1972

    work page 1972

  5. [5]

    Dress, A

    A. Dress, A. Flammenkamp, and N. Pink, Additive periodicity of the Sprague- Grundy function of certain Nim games. Adv. Appl. Math. , 22:249–270, 1999

    work page 1999

  6. [6]

    C. F. Du, H. Mousavi, L. Schaeffer, and J. Shallit, Decision algorithms for Fibonacci- automatic words, III: Enumeration and abelian properties. International Journal of Foundations of Computer Science , 27.08:943–963, 2016

    work page 2016

  7. [7]

    Duchˆ ene, A

    E. Duchˆ ene, A. S. Fraenkel, V. Gurvich, N. B. Ho, C. Kimberling, and U. Larsson, Wythoff visions. In U. Larsson, ed., Games of no chance , Vol. 5, pp. 101–153. Cambridge University Press, 2017

    work page 2017

  8. [8]

    Duchˆ ene and M

    E. Duchˆ ene and M. Rigo, A morphic approach to combinatorial games: the Tri- bonacci case. RAIRO–Theoretical Informatics and Applications, 42.2:375–383, 2008

    work page 2008

  9. [9]

    Fokkink and D

    R. Fokkink and D. Rust, A modification of Wythoff’s Nim. arXiv:1904.08339v1, 2019. the electronic journal of combinatorics 22 (2015), #P00 27

    work page arXiv 1904

  10. [10]

    R. K. Guy, ed., Combinatorial games. American Mathematical Society, Proceedings of Symposia in Applied Mathematics, Vol. 43, 1991

    work page 1991

  11. [11]

    D. E. Knuth, The art of computer programming. Addison-Wesley, Boston, Vol. 4B, Fascicle 5c, In preparation, 2019. (Seehttp://www-cs-faculty.stanford.edu/ ~knuth/fasc5c.ps.gz.)

    work page 2019

  12. [12]

    Larsson and J

    U. Larsson and J. W¨ astlund, Maharaja Nim: Wythoff’s queen meets the knight. Integers: Electronic Journal of Combinatorial Number Theory , 14#G05, 2014

    work page 2014

  13. [13]

    Lothaire, Combinatorics on words

    M. Lothaire, Combinatorics on words. Cambridge University Press, Encyclopedia of mathematics and its applications, Vol. 17, 1983

    work page 1983

  14. [14]

    Mousavi and J

    H. Mousavi and J. Shallit, Mechanical proofs of properties of the Tribonacci word. In F. Manea and D. Nowotka, eds., Combinatorics on Words: WORDS 2015 . Lecture Notes in Computer Science , Vol. 9304. Springer, 2015, pp. 170–190

    work page 2015

  15. [15]

    Pub- lished electronically at https://oeis.org

    The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences . Pub- lished electronically at https://oeis.org

    work page

  16. [16]

    Tan and Z.-Y

    B. Tan and Z.-Y. Wen, Some properties of the Tribonacci sequence.European Journal of Combinatorics 28.6:1703–1719, 2007

    work page 2007

  17. [17]

    Vanderlind, R

    P. Vanderlind, R. K. Guy, and L. C. Larson, The inquisitive problem solver . The Mathematical Association of America, 2002

    work page 2002

  18. [18]

    W. A. Wythoff, A modification of the game of Nim. Nieuw Arch. Wisk., 7:199–202, 1907. the electronic journal of combinatorics 22 (2015), #P00 28

    work page 1907