The n Queens Problem
In this page, you will get informations on the n queens problem. The basic question of the n queens problem is:
- 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 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
