My search algorithm for the n queens problem
On this page, I describe how I organised the search for torus solutions on a 29 by 29 cell chess board. Some remarks pertain to the 31 by 31 board.
First of all: my algorithm is also a backtracking algorithm, as is described in many lectures. I took it as a basis and improved it step by step.
Improvement 1: more look ahead - not only next row.
Most programs check only the next row for the next queen; i.e. they check if there is a free field in the next row. Probabaly, many lectures recommend that to minimize the effort for the single step. And probably that's right also for the n queens problem with smaller chess boards, say up to a 12 by 12 fields. Here, my program invests more work:
The program maintains an n by n array containing, for every field, how many queens which are already set can reach that field. With that array, the program determines if, in any row that has not yet a queen, there is no free field left; if so, it tracks back.
To illustrate it: if, on a 8 by 8 chess board, I put queens on rows 1 to 4, and if in that situation all fields of row 7 are "threatened" by some queen, then my program will move the queen in row 4; it will not try to place queens on row 5 and 6, although that may be possible.
A second difference to other program is that my program does not necessarily handle the rows in their natural order. If it is handling row 4 and "sees" that in row 7 only 2 possible fields are left while there are 3 or 4 in the rows 5, 6 and 8, then it will place the next queen in row 7.
With this improvement, I made the run for the 25 by 25 torus problem.
Improvement 2: Using also columns and diagonals for BackTrack.
All other programs that I know handle the board row by row. But that is not necessary. It is only necessary to split the problem into cases in a way that the program catches all possibilities. (Placing a queen in the next row means to split the rest of the problem into cases). And for that splitting of the problem, columns are as good as rows. For the torus problem, additionally you can do it on diagonals or anti-diagonals.
(Diagonals mean lines where x - y is constant, anti-diagonals lines where x + y is constant).
And the order of these split-cases may depend dynamically on the queens that are already on the board.
I think that improvement gives a significant advantage; but I must admit that I did not test it, as I implemented it together with the next improvement.
Improvement 3: Avoidance of indexing, chaining of neighbor fields.
I wrote my program not only to find n queens solutions but also to learn the Java programming language. By the time, I suspected that the large number of indexed variables made the program slow. And they made it a little difficult to understand also.
At that point, I made a step towards object orientation. I introduced a class QField for the single fields and a class QLineInfo for the lines (rows, columns, (anti-)diagonals). All instances of these classes are allocated at program start, and all basic linking is done. During search, an instance of QField is only switched from active to passive and vice versa, and it is linked to or delinked from the chain of fields which still must be handled.
As stated above, I did that together with using columns and diagonals for case differentiation; together it gave a considerable improvement in performance, but I do not know how much is effected by which improvement.
Improvement 4: Making partial runs possible.
For large n (i.e. n >= 23), the program needs long time. So it is more and more necessary to split it into partial runs. For that, I implemented a couple of commands in the program. They are given here:
Placing a fixed queen
The command "Set 1 1" instructs the program to set a queen on field 1/1 for the complete run. Several Set commands are allowed, but they should not contradict.
Blocking of a field
The command "Block 1 1" blocks field 1/1 for the complete run. No queen may be set on that field. Also for this type, several commands are possible for a run.Setting a minimal distance between two queens
The command "MinDist 4" instructs the program to set queens on neighbor lines no too close to each other, but to keep a minimal distance between them. Line means row and column here, not including - as above - (anti-)diagonals.If, for instance, a queen is on 7/11, then with MindDist 4 no queens may be on the fields 6/8, 6/9, 6/13, 6/14, 8/8, 8/9, 8/13, 8/14, 4/10, 5/10, 9/10, 10/10, 4/12, 5/12, 9/12 and 10/12. This command is allowed only once per run.
Note that this command works dynamically: with each queen set during the run, the affected fields will be blocked, and they are freed when the queen is removed during backtrack. The effort for every step increases, but over all the run accelerates significantly as it searches only fewer, more special solutions.
Setting a secondary minimal distance
The command "SecMinDist 7" causes the program to ensure another minimal distance for all pairs of queens that are set in the primary minimal distance. As the previous command, also this makes sense only once for a run.
An example for the effect of the command: "MinDist 2" (that's the default value) and "SecMinDist 7", together with queens on 7/11 and 8/13 makes the program block the fields 6/5, 6/6, 6/7, 6/8, 6/9 on the left side of the 'MinDist pair', and 9/15, 9/16, 9/17, 9/18 and 9/19 on the right side.
Avoidance of a "knight line"
The command "NoKniLine" tells the program never to set three queens in a "knights line", for example on 3/5, 5/6 and 7/7. A third queen in perpendicular direction to the first two queens - that would be on 4/8 or 6/4 in the example - is allowed.
Avoidance of more than one "knight neighbors" for a queen
The command "SingleKnight" forbids, for two queens in knights distance, also further "knight neighbors" in perpendicular direction.
Improvement 5: Splitting of the problem and compiling the results.
To split the total search and to compile the results, every partial run stores the solutions that it finds in a file. In a further program, I sort and merge these files, eliminating solutions that I found twice or more often.
Of course, the number of solutions increases rapidly, too fast to save them all. To handle the problem effectively, you have to save representatives for a whole subset of solutions. The choice of a representative comes in a natural way by considering symmetries of the set of all solutions.
Improvement 6: Exploitation of symmetries.
In special cases, exploitation of symmetry has been implemented often. Yet most programs use only the very basic symmetry by reflection. They set the first queen, in the normal, classical 8 by 8 board, only in the left half of the first line, and multiply the found number by two at the end.
Mr.U.Schimke went one step further in this direction. I had a few E-Mails with him on the subject. His program also recognizes if a new found solution is a rotated image of a solution that he found before.
Considering these symmetries while searching makes the program a bit complex; in my program, I can avoid that, because I save the solutions in a file and evaluate them later in other programs. The complexity is transferred to these other programs.
Searching for torus solutions, you have also to take in account shift operations. That reduces the range of search significantly.
For more intensive application of symmetry, you need some group theory; see Group actions.
All symmetries that I used stem from groups of movements which map
the chess board onto itself. The most simple group consists of the identity map
and the vertical reflection only, it is isomorfic to 
2.
The next level is what handled Mr.Schimke for the normal n queens problem; here, the group includes the horizontal reflection and the 90° rotations also. That gives the dihedral group D4. That is the group of congruent mappings within the given border, i.e. without shifts on the torus.
For the torus problem, you can start with the group of all shifts,
i.e. n × n
in mathematical notation. That's also
mentioned at the end of the article of Rivin, Vardi and Zimmermann.
It is more natural, however, to go to a group containg both previous groups.
That means, the group of all congruent mappings on the torus.
That leads to more complex symmetries, for instance the composition of a reflection
and a shift. For group theory, the new group is a wreath product
of D4 and n x n.
A pattern is called symmetric with respect to a motion (an element of the group) if and only if it is mapped onto itself by the motion. Or in group theoretic language: if and only if the motion is in the stabilizer of the pattern.
In this aspect, the set of all solutions is decomposed to the orbits of the group under discussion. The search for all solutions is reduced to finding a transversal of all solutions with respect to the group.
For the search of the T29 solutions, I did exactly that. To see simply if I had a solution before, I transformed every solution to the lowest element of its orbit, in alfabetic order. Then I stored that solution, for further processing. Some details are given below.
Improvement 7: Further, bigger groups of symmetries.
In the meantime, I considered further groups of mappings which map the chessboard onto itself. First, you can go from congruent mappings to similar mappings. A central expansion is also meaningful for these finite sets if and only if the expansion factor k is relative prime to n, the size of the board; this condition is necessary to keep the mappings bijective. And you can also consider affine mappings, either all bijective affine mappings or the special affine group of mappings whose determinant is 1 or -1.Exploiting similar mappings for the search leads to the following algorithm:
Step 1: Manage to get a transversal for all necklaces, with respect to similarity (necklaces in the mathematical sense, of course; also, the notion of similarity of necklaces may be new).
Step 2: Then start with necklaces containing many beads; corresponding to these beads, set queens on the 'main knights diagonal' (k, 2k). For all n that have torus solutions at all, that will not yield conflicts.
Step 3: Try to complete every incomplete solution of step 2. Doing that, you may avoid all solutions that have an other necklace that you have already worked on any knights line.
The last step will be to find all solutions that have only one queen on any knights line.
Having collected all these solutions, you get a transversal by sorting and merging. That is a transversal for the group of similar mappings. From there, you can generate also transversals for congruence on torus, or you can investigate numbers and properties of interest directly.
I used this 7th improvement in the search for the T31 solutions.
My steps for searching the torus solutions for n = 29, in detail
Searching the torus solutions for the 29 × 29 board, I did the following steps:
First I searched all solutions that have at least three queens in a "knigth line".
That is, the following commands for my program:
Set 1 1
Set 2 3
Set 3 5
To keep the single runs small, I added a forth queen in the forth row.
On the other hand, I blocked some fields to make sure that the knight line
starts at 1/1, and to avoid solutions that I had already by their symmetric image.
That gives, for instance, the complete command set:
Set 1 1
Set 2 3
Set 3 5
Set 4 10
Block 29 28
Block 29 27
Block 29 26
Then I searched solutions that have two queens in knights distance but not in a knights line. And these cases, I divided further in the cases where one of the queens has an second "knight neighbor" in right angle to the first, and those cases where she has not. The first case, I sorted as "NoKnightLine", the second as "SingleKnight". In the latter case, which needs most effort, I additionally used secMinDist.
An example for the commands for SingleKnight:
Set 1 1
Set 2 3
Set 3 7
SecMinDist 4
SingleKnight
and perhaps another fixed queen, just for partitioning the runs.
An example for the commands for NoKnightLine:
Set 1 1
Set 2 3
Set 4 2
NoKniLine
and also perhaps another fixed queen for partitioning the runs.
Finally, I searched the solutions having a higher minimal distance,
as "MinDist".
These runs had the commands, for example:
Set 1 1
Set 2 5
Block 29 26
MindDist 4
and perhaps more partitioning.