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

What means "torus problem"? It means that the queens are not limited by the borders in their movement. 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".
 
 

Main tool: group actions

To classify and to count the solutions, there is a main tool in my opinion. That tool is the idea of groups acting on a set. That is not discussed in the literature, as far as I know; but it should be discussed.
Dealing with that idea, it is natural to handle not only "normal" and torus solutions, but also some other sets in which these are contained.
To come to group actions, we start with some group of motions moving the fields of the board, and look if they induce an action on the solutions.
The most natural group acting on the board is the group consisting of reflection and rotation by 90 ° or a multiple of it. It induces actions on both normal and torus solutions: it is clear that a normal solution remains a normal solution if you rotate or reflect it. It is also clear that a torus solution remains a torus solution under reflection and rotation. This group is called the dihedral group D4 by the mathematicians.
The next bigger group contains also shifts on the torus. I call that group the group of congruent motions. However, that gives a complication for the normal solutions: a shifted solution may no longer be a solution.
Clearly, every solution is equivalent to a permutation. In the language of chess, that is the "n rooks problem" instead of the n queens problem. The set of all permutations is a set where the group of congruent motions acts properly.
There are also subsets of permutations which we should study when we search normal n queens solutions. We can assign to each permutation the maximum number of queens which share the same torus diagonal or torus anti-diagonal. Then the set of permutations having 1 as that maximum is just the set of torus solutions. The set of permutations having a maximum <= 2 contains all normal solutions - and it is a set which is stable under the action of congruent motions.
There are still two further steps for group actions; that means, there are two bigger groups which act on the solutions or a set containing them. One is the group of similar motions, the other the group of all affine motions. For similar motions, the last set described above works fine; for all affine motions, the set has to be extended. I do not know what is most appropriate until now; it is surely a subset of "n of n²", but maybe it may and should be confined in some way.

By the way: I have learned a lot on group actions in the book "Applied Finite Group Actions" by A.Kerber, 2nd edition, Springer 1999, ISBN 3-540-65941-2 (and I hope to learn still more), although the n queens problem is not mentioned in the book.
 
 

Results for counting

For counting the solutions, some information on the problem is contained in On-Line Encyclopedia of Integer Sequences. In the following table, you find links to special sequences.

The table is organized by the different sets and by the symmetries.
 
 

Tables of sequences:

 

Permutations as base sets (i.e. rooks instead of queens)

-	Permutations	Congruencies in the square, i.e. reflect and rotate	Congruencies on the torus, i.e. shift, reflect and rotate allowed	Similarity	?? regular affine mappings ??	all affine mappings
all	A000142	A000903	A006841	-	-	-
central symmetry (i.e. for rotation of 180°)	A037223	-	-	-	-	-
rotational symmetry (90°)	A037224	-	-	-	-	-
shift symmetries	-	-	-	-	-	-
other symmetries	Fixed by composition of rotation and reflection  A000085	-	-	-	-	-

 

Normal queens

-	Permutations	Congruencies in the square, i.e. reflect and rotate	Congruencies on the torus, i.e. shift, reflect and rotate allowed	Similarity	?? regular affine mappings ??	all affine mappings
all	-- classic case -- A000170	A002562	A062164	A062165	-	-
central symmetry (i.e. for rotation of 180°)	A032522	-	-	-	-	-
rotational symmetry (90°)	A033148	-	-	-	-	-
shift symmetries	-	-	-	-	-	-
other symmetries	-	-	-	-	-	-

 

Torus queens

-	Permutations	Congruencies in the square, i.e. reflect and rotate	Congruencies on the torus, i.e. shift, reflect and rotate allowed	Similarity	?? regular affine mappings ??	all affine mappings
all	A007705	-	A053994	A062166	-	-
central symmetry (i.e. for rotation of 180°)	-	-	-	-	-	-
rotational symmetry (90°)	-	-	-	-	-	-
shift symmetries	-	-	-	-	-	-
other symmetries	-	-	A054500 - 02	-	-	-

 

Permutations having at most 2 queens on a diagonal

-	Permutations	Congruencies in the square, i.e. reflect and rotate	Congruencies on the torus, i.e. shift, reflect and rotate allowed	Similarity	?? regular affine mappings ??	all affine mappings
all	-	-	A062167	A062168	-	-
central symmetry (i.e. for rotation of 180°)	-	-	-	-	-	-
rotational symmetry (90°)	-	-	-	-	-	-
shift symmetries	-	-	-	-	-	-
other symmetries	-	-	-	-	-	-

As you see, there are still many unknown sequences which are also of some interest.

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  containing 80 (or more) articles on the nQueens problem.
 
  Start of page
 
 

Prepared by Matthias Engelhardt       mailto: Matthias.R.Engelhardt@web.de    last updated: 2001-08-12