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