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.

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s