The Number of n-queens Configurations
September 19, 2022, 2:00 PM - 3:00 PM
Location:
Hill Center-Room 705
Michael Simkin, Harvard University
The n-queens problem is to determine Q(n), the number of ways to place n mutually non-threatening queens on an n x 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 from 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
COVID-19 Regulations: Please note that mask-wearing is still required indoors.