The number of $n$-queens configurations

Abstract: The $n$-queens problem is to determine $\mathcal{Q}(n)$, the number of ways to place $n$ mutually non-threatening queens on an $n \times n$ board. We show that there exists a constant $\alpha = 1.942 \pm 3 \times 10^{-3}$ such that $\mathcal{Q}(n) = ((1 \pm o(1))ne^{-\alpha})^n$. The constant $\alpha$ is characterized as the solution to a convex optimization problem in $\mathcal{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 \textit{queenons}. These are a convex set in $\mathcal{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

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456