A lower bound for the n-queens problem
read the original abstract
The $n$-queens puzzle is to place $n$ mutually non-attacking queens on an $n \times n$ chessboard. We present a simple two stage randomized algorithm to construct such configurations. In the first stage, a random greedy algorithm constructs an approximate \textit{toroidal} $n$-queens configuration. In this well-known variant the diagonals wrap around the board from left to right and from top to bottom. We show that with high probability this algorithm succeeds in placing $(1-o(1))n$ queens on the board. In the second stage, the method of absorbers is used to obtain a complete solution to the non-toroidal problem. By counting the number of choices available at each step of the random greedy algorithm we conclude that there are more than $\left( \left( 1 - o(1) \right) n e^{-3} \right)^n$ solutions to the $n$-queens problem. This proves a conjecture of Rivin, Vardi, and Zimmerman in a strong form.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Statistical mechanics of the $N$-queens problem
Monte Carlo simulations of the N-queens lattice gas recover the Simkin constant γ ≈ 1.944 to 0.1% accuracy via thermodynamic integration from the exact high-temperature limit.
-
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 da...
-
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 po...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.