n queen topics
Group actions
Search algorithm
Use symmetry, regular NQ problem
Evolution trees
Special properties
Necklaces
Conflicts
Conflict tables
World records
Tables of counting results
Images for n=8
Torus images for n=13
Other pages to the n queens problem
Bibliografy
 
 
Other themes
Primes from sums of factors
Primes from wrong binomic formula
Numbers by primes distribution
 
 
 
This page in another language
German

The n Queens Problem

ThreeColorImage
Three solutions for a 13 x 13 chess field, in different colors.

In this page, you will get informations on the n queens problem. The basic question of the n queens problem is:

can you place n queens on a n x n board in such a way that no one attacks another queen?
Derived from this basic question are other questions:
  • Is there a solution for every n?
  • How many solutions are there (i.e. counting the ways of placing the n nonattacking queens)
  • Are there special properties of such arrangements?
  • How can the solutions classified? Are some solutions similar or near to another, in some sense?
  • Can we depict a map of the solutions?
  • Are there connections to other famous problems? Can the problem be generalized, and what generalizations are the most interesting?
  • What are the best algorithms to find all solutions - or a special solution - or solutions with some given property?
Warning: The board and the queen are used in the sense of chess; however, there is no deeper connection to chess in that problem. The information in this page will not help you for chess problems.

Warning: the translation of these page to English is done by myself, and certainly not perfect. If you don't understand something, you might try to understand the German version. Or you might deduce the meaning form the context. In both cases, I will be glad if you send an improved version of a part in the text to me.

Introduction

The historical root of the problem is the case n=8 which was discussed in the 19th century; it was posed in 1848 by Max Bezzel, and also the famous mathematician Carl Friedrich Gauss dealt with it.

The most common -  and most useful - generalization is the "torus problem". That is explained below, on this side.

The problem has become a standard problem in computer science, in the 1970 years. There are many articles and pages in the net, and it is a challenge to find the numbers of solutions for larger chess board sizes. In this sense, I speak of world records on this site.

The subpages of this site contain information of tools that may be used to handle the n queens problem, on facts that are already known about the problem, some images that visualize these results, and some notes on world records. They will also contain information that is not yet validated sufficiently.

What means "torus problem"

Torus problem means that the queens are not limited in their movement by the borders. There are two ways to think of it: first you can think of the chess board as wrapped around a cylinder. Thats all you need concerning the n queens torus problem, although the wrapped board is only half the way from rectangle to a torus. The second step is that you form a ring - just like a life belt - from the cylinder, removing the other two borders. That's what mathematicians call a torus, and it's different from a cylinder in other aspects - yet equivalent for the n queens.

The second way to imagine the torus problem is to think of a borderless, endless plane and of infinite many queens on it in a periodic arrangement; the n changes its meaning from the size of the board to the periodic distance of these queens. We have a solution of the torus problem if there are exactly n queens in every n by n rectangle of the endless plane, and if every queen "attacks" only her "periodic sisters".

Two colorful images for n=13

For more details, there are images at Torus images for n=13. For a first glance, the next two images show some torus solutions for a 13 × 13 field, chosen at random; different solutions appear in different colors.
     

Additional information

Prof.Kosters in Leiden (Netherlands) maintains a  bibliografy. It contained over 80 articles on the nQueens problem about the year 2000, i.e. before the internet had become a common source. Meanwhile, it is enriched also with references in the world wide web, and has over 330 references.
Prepared by Matthias Engelhardt
Mail to Matthias Engelhardt
 
last change: 2014-02-05
Address of page: http://nqueens.de/index.en.html