## Zur Luria on the n-Queens Problem

(From Wikipedia )

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 $Q(n)$ be the number of ways to place n non attacking queens on an n by n board, and let $T(n)$ be the number of ways to place n non-attacking queens on an n by n toroidal board.  $Q(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 $T(n) \ne 0$ iff $n$ is 1 or 5 modulo 6. (Clearly, $T(n) \le Q(n) \le n!$.)

Here are Zur Luria’s new results:

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

Theorem 2: $Q(n) = O(n^n/e^{\alpha n})$, 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 $T(n) \ge n^{cn}$.

Update: In the lecture Zur noted that the proof actually works for all odd n such that -1 is a quadratic residue mod n.

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 $T(n)$ has a closed form and understanding this generating function is a very interesting problem. Luria conjectures that his upper bound for $T(n)$ is sharp.

Luria’s conjecture: $T(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 $Q(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.

This entry was posted in Combinatorics, Games and tagged , , , . Bookmark the permalink.

### 7 Responses to Zur Luria on the n-Queens Problem

1. Andy Drucker says:

Good stuff! Readers should note that Luria uses the opposite convention: Q(n) for the ordinary queens problem, and T(n) for the toroidal version.

• Gil Kalai says:

Many thanks, Andy. On the bright side I do use consistently Q(n) and T(n) throughout the post which is a small miracle (for me). I will try fixing it later…

GK: corrected.

2. Vincent says:

The picture is moving quite fast, so I cannot be entirely sure, but it seems to me that the picture taken together with Polya’s result further down the post proves that 8 is and odd number. This seems a bit, well, odd.

• Gil Kalai says:

Dear Vincent, the picture demonstrates an algorithm for the origibal problem not the toroidal one.

• Vincent says:

Dear Gil,
I see, but then I guess the letters Q and T got swapped again at some point. Poya’s congruence result holds for T rather than Q?

GK:oops corrected

3. Hi, since recently I was not aware that n-queens-problem exists. Then discover it and understood that I have solution back from 2005. for all n=p and n=p-1… Additionally, inpxp space anz two pre-placed queens are enough to find solution by very simple algorithm… more on bit.do/8-queens