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.