## Combinatorics Seminar - Spring '21

When: Sunday, March 21, 10am

Where: Schreiber 309

Speaker: Michael Simkin, Harvard

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 \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

##