Zur Luria on the n-Queens Problem

Combinatorics and more 2018-05-10

The eight queens puzzle is the famous problem of placing eight chess queens on a chessboard so that no two queens threaten each other. The questions if this can be done and in how many different ways, as well as the extension to n queens on a n × n chessboard was raised already in the mid nineteen century. Apparently Gauss was interested in the problem and figured out that the number of solutions for the 8 × 8 board is 92, and Zur Luria gave a beautiful lecture about his new results on the number of solutions in our seminar earlier this week. The lecture follows Luria’s paper New bounds on the n-queens’s problem.

Before getting to Zur’s result a little more on the history taken from Wikipedia: “Chess composer Max Bezzel published the eight queens puzzle in 1848. Franz Nauck published the first solutions in 1850. Nauck also extended the puzzle to the n queens problem, with n queens on a chessboard of n × n squares. Since then, many mathematicians, including Carl Friedrich Gauss, have worked on both the eight queens puzzle and its generalized n-queens version. In 1874, S. Gunther proposed a method using determinants to find solutions… In 1972, Edsger Dijkstra used this problem to illustrate the power of what he called structured programming. He published a highly detailed description of a depth-first backtracking algorithm.” For more on the history and the problem itself see the 2009 survey by Bell and Stevens. Let me also mention the American Mathematical Monthly paper The n-queens problem by Igor Rivin, Ilan Vardi and Paul Zimermmann. (In preparing this post I realized that there are many papers written on the problem.)

Let $T(n)$ be the number of ways to place n non attacking queens on an n by n board, and let $Q(n)$ be the number of ways to place n non-attacking queens on an n by n toroidal board. $T(n)$ is sequence A000170 in the On-Line Encyclopedia of Integer Sequences. The toroidal case, also referred to as the modular n-queens problem was asked by Polya in 1918. Polya proved that $Q(n) \ne 0$ iff $n$ is 1 or 5 modulo 6. (Clearly, $Q(n) \le T(n) \le n!$ .)

Here are Zur Luria’s new results:

Theorem 1: $Q(n) = O(n^n/e^{3n})$

Theorem 2: $T(n) = O(n^n/e^{\alpha n 1+o(1)})$ , for some $\alpha >1$ .

As far as I know, these are the first non-trivial upper bounds.

Theorem 3: For some constant $c>0$ , if $n$ is of the form $2^{2k+1}+1$ then $Q(n) \ge n^{cn}$ .

Theorem 3 proves (for infinitly many integers) a conjecture by Rivin, Vardi, and Zimmermann, who proved exponential lower bounds. Luria’s beautiful proof can be seen (and this is how Zur Luria views it) as a simple example of the method of algebraic absorbers, and Zur mentions an earler application of a similar methods is in a paper of Potapov on counting Latin hypercubes and related objects. Rivin, Vardi and Zimmermann conjectured that the exponential generating function of $Q(n)$ has a closed form and understanding this generating function is a very interesting problem. Luria conjectures that his upper bound for $Q(n)$ is sharp.

Luria’s conjecture: $Q(n) = n^n/e^{3n (1+o(1))}$ .

In view of recent progress in constructing and counting combinatorial designs this conjecture may be within reach. Zur also conjectures that for $T(n)$ , 3 should be replaced by some $\beta<3$ .

More on chess on this blog: Chess can be a Game of Luck, Amir Ban on Deep Junior, and quite a few other posts.