1. 3

The n-queens problem is to determine (n), the number of ways to place n mutually non-threatening queens on an n×n board. We show that there exists a constant α=1.942±3×10−3 such that (n)=((1±o(1))ne−α)n. The constant α is characterized as the solution to a convex optimization problem in ([−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 ([−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. 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.

  1.