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

Here are Zur Luria’s new results:

**Theorem 1:**

**Theorem 2:** , for some .

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

**Theorem 3:** For some constant , if is of the form then .

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

**Luria’s conjecture:** .

In view of recent progress in constructing and counting combinatorial designs this conjecture may be within reach. Zur also conjectures that for , 3 should be replaced by some .

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

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.

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.Pingback: Blog post on new bounds for the n-queens problem. Includes link to the relevant paper on arXiv. – Nevin Manimala’s Blog

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.

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

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