For k≥3 and sufficiently large n, the maximum number of points in an n×n grid with no k+1 collinear is exactly kn.
The n-queens problem
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
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}lya's 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.
representative citing papers
Mapping N-queens to a lattice gas model shows that specific heat converges to a universal curve without phase transition, enabling thermodynamic integration to compute the Simkin constant γ ≈ 1.944 from Monte Carlo data alone.
Introduces the extensible no-(k(n)+1)-in-line problem on infinite grids, constructs optimal sets for linear k(n) and positive-density sets for power k(n), proves any high-density configuration requires k(n) growing polynomially, and reduces the constant-k case to regular functions.
QUBO formulations are derived for generalized LinkedIn Queens, Takuzu/Tango, Tents & Trees, and two new chess-piece problems to enable solution on quantum hardware.
citing papers explorer
-
No-$(k+1)$-in-line problem for $k \geqslant 3$
For k≥3 and sufficiently large n, the maximum number of points in an n×n grid with no k+1 collinear is exactly kn.
-
Statistical mechanics of the $N$-queens problem
Mapping N-queens to a lattice gas model shows that specific heat converges to a universal curve without phase transition, enabling thermodynamic integration to compute the Simkin constant γ ≈ 1.944 from Monte Carlo data alone.
-
The extensible no-$(k(n)+1)$-in-line problem
Introduces the extensible no-(k(n)+1)-in-line problem on infinite grids, constructs optimal sets for linear k(n) and positive-density sets for power k(n), proves any high-density configuration requires k(n) growing polynomially, and reduces the constant-k case to regular functions.
-
A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game
QUBO formulations are derived for generalized LinkedIn Queens, Takuzu/Tango, Tents & Trees, and two new chess-piece problems to enable solution on quantum hardware.