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 $\hat{I}\pm =1.942\pm 3\times 10^{-3}$ such that $\mathcal{Q}(n)=((1\pm o(1))n{e}^{-\hat{I}\pm }{)}^n$. The constant $\hat{I}\pm$ 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 queenons. These form 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 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 in the space of queenons. Along the way we prove a large deviations principle for $n$-queens configurations that can be used to study their typical structure.

60 pages, 4 figures. Filled in a gap by adding Lemma 3.5. Corrected various minor errors