Queens in exile

Non-attacking queens on infinite chess boards

Journal article (2020)

Authors

F.M. Dekking Applied Probability - EEMCS
Jeffrey Shallit University of Waterloo
N.J.A. Sloane The OEIS Foundation Inc.
Research Group
Applied Probability (EEMCS) (TU Delft)
Copyright: © 2020 F.M. Dekking, Jeffrey Shallit, N.J.A. Sloane
DOI
help_outline
https://doi.org/10.37236/8905
Combinatorial games Greedy Queens Sprague-Grundy function Tribonacci representation Tribonacci word Wythoff Nim
More Info
expand_more

Published Date

2020

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Applied Probability

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.