CMSA Interdisciplinary Science Seminar: The number of n-queens configurations

CMSA EVENTS

View Calendar
September 23, 2021 9:00 am - 10:00 am
via Zoom Video Conferencing
Speaker:

Michael Simkin - CMSA

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. The problem has a storied history and was studied by such eminent mathematicians as Gauss and Polya. The problem has also found applications in fields such as algorithm design and circuit development.
Despite much study, until recently very little was known regarding the asymptotics of Q(n). We apply modern methods from probabilistic combinatorics to reduce understanding Q(n) to the study of a particular infinite-dimensional convex optimization problem. The chief implication is that (in an appropriate sense) for a~1.94, Q(n) is approximately (ne^(-a))^n. Furthermore, our methods allow us to study the typical "shape" of n-queens configurations.
Zoom ID: 950 2372 5230 (Password: cmsa)