Using symmetry for the regular n queens problem

It is a bit surprising that symmetry rarely has been used to count n queens solutions. Probably, this is due to the fact that it is not quite obvious how to use the symmetry. On the other hand, it is not too tricky.

From a mathematical standpoint, the symmetries to use stem from the action of the dihedral group on the solutions (see also group actions). But also without group theory, the main formula is well explained on the page of TU Dresden. This formula is:

    Q(n) = 8 * A(n) + 4 * P(n) + 2 * R(n), if n > 1.

Here, Q(n) means the number of solutions, A(n) the number of orbits of asymmetric solutions, P(n) the number of orbits of solutions having central symmetry, and R(n) the number of orbits of solutions having rotational symmetry

The basic thought is: search in a way that you get only one solution of every orbit. If this solution is asymmetric, it leads to eight solutions. The orbit consists of eight single solutions. If the solution has symmetry, it yields four or two: four if it is only central symmetry; this case means the solution is symmetric under 180° rotation, but not under 90°. A rotation-symmetric solution (90°) gives only two.

But how do you search to actually get only one solution of every orbit? This is probably the crucial point where many gave up. You should abandon the usual way of search where you place the queens row by row. To benefit from symmetry you should start with a complete constellation of queens on the broder lines. This is, you need three or four queens who occupy the first and last row, and the leftmost and rightmost column. Three queens are sufficient if one of them is on a corner field where she occupies a border row and a border column at the same time. If we had rocks instead queens, we had even only two rocks, on corners lying opposite on a diagonal, in a very special case. That is not allowed for queens, as they threaten each other.

With rare exceptions, solutions of the same orbit differ in their border queens. One can check what happens on the border constellation, under action of the dihedral group, i.e. under reflection and rotation. If you get eight different border constellations, the solutions of the orbit are completely asymmetric. Filling in more queens according to the rules cannot change this to symmetry. Therefore, you need only one of these border constellations.

But you have to take care when you fill up a symmetric border constellation to a complete solution. As in the other case, you need only one of the start configurations. But two things can happen: first, you do not know if the completed solution is still symmetric, or of same symmetry type. Second, you might find more than one solutions of the same orbit.

You must check with every solution which symmetry type it is. In the notations of the formula, you must find out if it belongs to A(n), to P(n), or to R(n). And you must throw away a solution, if you already found another solution of the same orbit, or will find it under the continuation of the search. That is done best by building all members of the orbit (perhaps you have them already, from the symmetry check), filter out those which do not fit to the border constellation, and check if your solution is the smallest of the remaining. If not, you must forget the solution! Only one of each orbit must be counted.

For those who want to search and use symmetry, but would like to avoid the tedious work to build the start constellations, I did this part. You can load down a zip file, under start constellations. This file contains two files of start constellations, for every n between 4 and 30, one for asymmetric, and one for symmetric start constellations.

The format of the files is binary and nearly self-explaining. The file is made up of variable length records; that was called "sequential access method" in the age of mainframe systems, corresponding to the suffix ".sam". Every record starts with a record length field of 2 byte. Adding the length field to the actual position in the file leads you to the next record.

Within a record comes a marker 'PP' (for planar pattern) first, then a versions byte (always x01, up to now). The size of the board follows in one byte, and then the number of queens in two byte. According to this number, the next bytes contain pairs of coordinates x/y, per queen. These x and y run from 0 to the board size - 1.

Begin of page