dimacs logo color

Events

Seminar Details

The Number of n-queens Configurations

  • Start Date: September 19, 2022
  • Event Start Time: 2:00 PM
  • Event End Time: 3:00 PM
  • Event Location: Hill Center-Room 705
  • Seminar Series: Rutgers Discrete Mathematics Seminar
  • Presenter(s): Michael Simkin - Harvard University
  • Event Additional Info: <p><strong>COVID-19 Regulations</strong>: Please note that mask-wearing is still required indoors.</p> <p>See:&nbsp;<a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
  • Presentation Type: Stand Alone Presentation
  • 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 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