Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQueens in exile: non-attacking queens on infinite chess boards
85
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
The famous $n$-queens problem asks how many ways there are to place $n$ queens on an $n times n$ chessboard so that no two queens can attack one another. The toroidal $n$-queens problem asks the same question where the board is considered on the surface of the torus and was asked by P{o}lya in 1918. Let $Q(n)$ denote the number of $n$-queens configurations on the classical board and $T(n)$ the number of toroidal $n$-queens configurations. P{o}lya showed that $T(n)>0$ if and only if $n equiv 1,5 mod 6$ and much more recently, in 2017, Luria showed that $T(n)leq ((1+o(1))ne^{-3})^n$ and conjectured equality when $n equiv 1,5 mod 6$. Our main result is a proof of this conjecture, thus answering P{o}lyas question asymptotically. Furthermore, we also show that $Q(n)geq((1+o(1))ne^{-3})^n$ for all $n$ sufficiently large, which was independently proved by Luria and Simkin. Combined with our main result and an upper bound of Luria, this completely settles a conjecture of Rivin, Vardi and Zimmmerman from 1994 regarding both $Q(n)$ and $T(n)$. Our proof combines a random greedy algorithm to count almost configurations with a complex absorbing strategy that uses ideas from the recently developed methods of randomised algebraic construction and iterative absorption.
By now, the Maker-Breaker connectivity game on a complete graph $K_n$ or on a random graph $Gsim G_{n,p}$ is well studied. Recently, London and Pluhar suggested a variant in which Maker always needs to choose her edges in such a way that her graph stays connected. By their results it follows that for this connected version of the game, the threshold bias on $K_n$ and the threshold probability on $Gsim G_{n,p}$ for winning the game drastically differ from the corresponding values for the usual Maker-Breaker version, assuming Makers bias to be $1$. However, they observed that the threshold biases of bo
We investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values---the omega one of chess---with two senses depending on whether one considers only finite positions or also positions with infinitely many pieces. For lower bounds, we present specific infinite positions with transfinite game values of omega, omega^2, omega^2 times k, and omega^3. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true omega one.
We present a position in infinite chess exhibiting an ordinal game value of $omega^4$, thereby improving on the previously largest-known values of $omega^3$ and $omega^3cdot 4$.
The study of the structure of infinite words having bounded abelian complexity was initiated by G. Richomme, K. Saari, and L. Q. Zamboni. In this note we define bounded additive complexity for infinite words over a finite subset of Z^m. We provide an alternative proof of one of the results of Richomme, Saari, and Zamboni.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
