Groups and Group Actions in the n Queens Problem
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.
Groups and group actions are appropriate tools to handle questions of symmetry. These symmetries may be used for more efficient searching, and for better classification.
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.
There are two smaller groups, subgroups of D4, also used in connection with the n queens problem: the group Mirror, consisting only of the identity and the reflection at the vertical axis, and the group Rotate, consisting of the rotations by 0, 90, 180 and 270 degrees.
But more interesting are larger groups. The next larger group contains also shifts on the torus. I call that group the group "Congruency group" or 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 of the chess board. The latter may even be restricted to all regular affine mappings.
The group of similar motions needs some explanation; I apologize that I do not have it here on the page, I will insert it in the next months.
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, although the n queens problem is not mentioned in the book. Many of the basic ideas are certainly found in other books on group theory, also.