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