Michael Simkin

Harvard


The number of n-queens configurations


Combinatorics Seminar


19th October 2021, 4:00 pm – 5:00 pm
Virtual (online) Zoom seminar; a link will be sent to the Bristol Combinatorics Seminar and Bristol Probability Seminar mailing lists, the week before the seminar.


The n-queens problem is to determine Q(n), the number of ways to place n mutually non-threatening queens on an n by n chessboard. We show that there exists a constant $\alpha = 1.942 \pm 3 \times 10^{-3}$ such that $Q(n) = ((1 \pm o(1))ne^{-\alpha})^n$. The constant $\alpha$ is characterized as the solution to a convex optimisation problem in $P([-1/2,1/2]^2)$, the space of Borel probability measures on the square.

The chief innovation is the introduction of limit objects for n-queens configurations, which we call `queenons'. These are a convex set in $P([-1/2,1/2]^2)$. We define an entropy function that counts the number of n-queens configurations that approximate a given queenon. The upper bound uses the entropy method. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons.

Based on arXiv:2107.13460






Comments are closed.
css.php