***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker:  Michael Simkin (MIT)

Thursday 29th February, 3:00 in Fine Hall 224.

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 chess 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". 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 of the upper bound.
The enumeration of n-queens configurations is then obtained by maximizing the
(concave) entropy function over the (convex) space of queenons.


		----------------------------------


Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)