# 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

**Abstract**:

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
- Events By School
- Website

- Department
- Department of Mathematics
- Add to my calendar

#### Recent Activity

No recent activity