Combinatorics Seminar - Michael Simkin

16:15-18:00

Speaker: Michael Simkin

Title: The number of n-queens configurations

Abstract: 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 board. We show that there exists a constant $\alpha =1.942\pm 3\times 10^{-}$ such that $\mathcal{Q}(n)=((1\pm o(1))n{e}^{-\alpha }{)}^n$. The constant $\alpha$ is characterized as the solution to a convex optimization problem in 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 the space of Borel probability measures on the square. 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.