Combinatorics Seminar - Spring '21

When: Sunday, March 21, 10am

Where: Schreiber 309

Speaker: Michael Simkin, Harvard

Title: The Number of $n$-queens configurations



The $n$-queens problem is to determine $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 $1.94 < a < 1.9449$ such that $Q(n) = ((1 + o(1))ne^{-a})^n$. The constant $a$ is characterized as the solution to a convex optimization 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 approximating a given queenon. The upper bound uses the entropy method of Radhakrishnan and Linial--Luria. 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 over the space of queenons.

Based on arXiv:2107.13460