MIT-Harvard-MSR Combinatorics Seminar

Wednesday, October 06, 2021 at 4:15pm to 5:15pm

MIT-Department of Mathematics, Room 2-139

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 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 are a convex set in 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. 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.


Event Type


Events By Interest


Events By Audience

MIT Community

Events By School

School of Science


Department of Mathematics
Add to my calendar

Recent Activity