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

F. Michel Dekking, Jeffrey Shallit, N.J.A. Sloane

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)
60 Downloads (Pure)

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 ℤ × ℤ numbered along a square spiral, and an infinite single-quadrant chessboard (of size N × 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.

Original languageEnglish
Article numberP1.52
Pages (from-to)1-27
Number of pages27
JournalElectronic Journal of Combinatorics
Volume27
Issue number1
DOIs
Publication statusPublished - 2020

Keywords

  • Combinatorial games
  • Greedy Queens
  • Sprague-Grundy function
  • Tribonacci representation
  • Tribonacci word
  • Wythoff Nim

Fingerprint

Dive into the research topics of 'Queens in exile: Non-attacking queens on infinite chess boards'. Together they form a unique fingerprint.

Cite this