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

2019/07/22 by Dekking, F. Michel, Shallit, Jeffrey, Sloane, N. J. A. · 3 citations
#91A46 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1907.09120

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.

Cited by

• On a sequence of Kimberling and its relationship to the Tribonacci word
• The Tribonacci constant and finite automata
• Thresholds of Queen covers

Related

• Improved lower bounds for Queen's Domination via an exactly-solvable relaxation
• Hyper-bishops, Hyper-rooks, and Hyper-queens: Percentage of Safe Squares on Higher Dimensional Chess Boards
• A lower bound for the n-queens problem
• Successful strategies for a queens placing game on an n x n chess board
• On the existence of reflecting n-queens configurations