n queen topics
This page in another language
Images for the normal n queens problem, n=8
Note: there are no torus solutions for n=8.
For the normal nQueens problem, there are 92 ways of placing the queens.
Ordering them by congruency in the square gives the decomposition
92 = 11 × 8 + 1 × 4
i.e. there are 12 solutions incongruent in the square (one of them having central symmetry).
Ordering them by congruency on the torus gives the decompositions
12 = 1 × 7 + 5 × 1,
i.e. 5 solutions are different also under torus shift, but the other 7 are equivalent;
92 = 1 × 56 + ( 4 × 8 + 1 × 4),
i.e. all solutions may be derived from six solutions on the torus.
These six solutions are given in the images below; they are moved to their lowest lexicografic representation.
Explanation for the images
To understand the images, you may need some explanations: if two queens stand on the same diagonal, then there is a "conflict". These conflicts are shown as transparent lines, different conflicts using different colors. Of course, you should think the diagonals as loops on the torus, so there are two arcs between the two queens. The images contain only one of them.
For each conflict, there are "separation points" forming "separation areas" which consist or four rectangles; the images show these areas in the same color. A point (corner point of a field) is a separation point of a conflict if and only if that conflict disappears when you shift the origin to that point and view the arrangement as "normal queens".
If a point lies in the intersection of all separation areas, then I call it a separation point for the whole solution. These points are shown by little red circles.
Table of images
As you see, the idea of similarity gives a reduction from 6 to 4 "base" solutions. In the case of n=8, affine motions do not reduce the number of base solutions further.