Speaker: Michael Simkin, Harvard CMSA

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. 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.