Variants of the Eight-Queens Problem in chess have intrigued mathematicians for more than a century
Recreational programs are as old as computers. Most are written simply for fun; others, to acquire familiarity with a new programming language or to demonstrate a new piece of hardware. Occasionally such a program is taken up by an enthusiastic group of users, or is carried from place to place by an itinerant professional, but the usual fate of these programs is to be lost, forgotten or discarded. This series will attempt to provide a forum for these waifs It will not include programs which might be published as serious work; the more useless and entertaining the better. A notable example is the Eight-Queens Problem on the chessboard: In how many ways can eight queens be placed on an 8*8 chessboard so that no two queens can attack each other? In its broader form, the problem involves N queens on an N"N chessboard. First proposed by Franz Nauck about 1850, the problem was vigorously attacked by mathematicians in the 19th century. Their methods and results were recorded by Maurice Kraitchik in 1942. These pre-computer results contain an interesting error which has been perpetuated by modern plagiarists myself included.
The standard approach to the problem on a computer is exhaustive enumeration via backtracking techniques. This method is familiar to anyone who has written a game-playing program, and has become almost standard for solving combinatorial problems. The board is numbered as shown in Figure 1 below, with square 1 at the lower left and square 64 (or square N*N) at upper right. When a queen occupies square 3, for example, all the squares that she attacks in the rows above are incremented by 1, creating the arrowhead pattern shown in the next illustration, Figure 2. (For this reason the particular method of backtracking used in the queens problem is sometimes called the arrowhead.} Next, the row above is scanned for an empty square and the procedure is repeated. A solution is obtained if an empty square can still be found when the program reaches the top row.
Whenever the program cannot advance, either because it has found a solution or because there are no empty cells in the current row, then it backtracks: It removes the piece it has just placed in the previous row, decrements all the squares attacked by that piece, and searches for another empty cell in the previous (now current) row. In this way all solutions are found.
This procedure involves only two tricks that are worthy of note. The first is that the first queen need only be placed in squares 1 to 4 (half the possible positions), because placing her in squares 5 to 8 merely produces reflections. The second trick is that to find the number of inequivalent solutions one must check for rotational symmetry. For example, the illustration, Figure 3, below depicts a solution for N = 8, where there is a 180° symmetry. The program finds that the total number of solutions for N = 8 is 92, comprising 11 inequivalent solutions (which do not reflect or rotate into any other solution. The total is therefore 8*11 + 4*1 = 92.
There is a simple way to check for symmetry when the program has a solution. If (1st) + (8th)=65 then if (2nd) +(7th) = 65 then if (3rd) + (6th) = 65 then if (4th) + (5th) = 65 then the solution is symmetrical; if so, a further check is made to determine if the solution ha a 90° symmetry. The two simplest examples, Figure 4, are for N = 4 and N = 5, which can only reflect into a different pattern.
The latest results calculated by a program based on these techniques are summarized in Table 1. The total number of solutions rises roughly by a factor of 6 for each increment of N, and at N = 16 the machine time required is roughly one hour for an expertly coded program in Pascal running on a CDC 7600. It is fairly simple, however, to refine the program to search only for 90° symmetric solutions; these particular results have been calculated up to N = 29. From here on only these results will be considered.
The important point about a 90° symmetric solution is that each quadrant of the board must contain the same number of queens; therefore N or N-1 must be divisible by 4 (N-1, because one queen can - indeed in this case must - occupy the center square). The previous examples for N = 4 and N = 5 illustrate this point.
Strangely there are no solutions for N = 8 or N = 9, but at N = 12 and N = 13 a new symmetry becomes apparent, as shown in Figure 5. The eight solutions for N = 12 are depicted at upper right and the eight solutions for N = 13 at lower left. In both cases the eight solutions are obtained by permuting any three unconnected pieces and then rotating the pattern into the other three quadrants. One such solution for N = 12 is indicated by the positions of the three black queens.
There arc 64 solutions for N = 16, as indicated in Figure 6. Each quadrant represents, and can generate, 16 (2 to the 4th power) solutions by permuting any four unconnected queens. A single solution is indicated by the position of the black queens in the lower right quadrant. There are 128 solutions for N = 17, and for the sake of compression, these are shown in octants of the board in Figure 7.
At this point a generalization becomes obvious: If N/4 or (N-1)/4 is an integer m, then the number of 90° symmetric solutions will be a multiple of 2 to the (m-1)th power. Kraitchik knew this but did not make it clear in his book. In composing his table he neglected to multiply the 90° symmetric solutions by the appropriate power of 2; as a result the number of inequivalent solutions for N = 12 in his table seems to be 1765+18 + 1 = 1784. This error appeared in Ball and Coxeter's book as recently as 1972. A table that summarizes the latest results appears at right.
No simple formula or function will give the total number of solutions for any given value of N. The problem is similar to riffle-shuffling a deck of N cards; when N = 52 (as in the normal deck) then only eight shuffles are required to restore the original order, but if N = 50 or 54 then more shuffles are necessary. Further study of the shuffling problem reveals that when N is a power of 2 the solution is trivial. Similarly, when N in the Queens Problem is a power of 2 there appears to be a better chance of predicting the answer. Nevertheless this solution has yet to be demonstrated; I should be interested to hear from anyone who has an idea about this subset of the Queens Problem.
The 128 solutions for N = 17 are shown at top. A table of the latest results for the Queens Problem appears at right.
| N | TOTAL SOLUTIONS |
GROUPS | SYMMETRY OF INEQUIVALENT SOLUTIONS | ||
|---|---|---|---|---|---|
| NO SYMMETRY | 180° | 90° | |||
| × 8 | × 4 | × 2 | |||
| 1 | 1 | 1 | 1 × 0.5 | ||
| 2 | 0 | 0 | |||
| 3 | 0 | 0 | |||
| 4 | 2 | 1 | 1 × 1 | ||
| 5 | 10 | 2 | 1 | 1 × 1 | |
| 6 | 4 | 1 | 1 | ||
| 7 | 40 | 6 | 4 | 2 | |
| 8 | 92 | 12 | 11 | 1 | 0 × 2 |
| 9 | 352 | 46 | 42 | 4 | 0 × 2 |
| 10 | 724 | 92 | 89 | 3 | |
| 11 | 2680 | 341 | 329 | 12 | |
| 12 | 14200 | 1787 | 1765 | 18 | 1 × 4 |
| 13 | 73712 | 9233 | 9197 | 32 | 1 × 4 |
| 14 | 365596 | 45752 | 45647 | 105 | |
| 15 | 2279184 | 285053 | 284743 | 310 | |
| 16 | 14772512 | 1846955 | 1846189 | 734 | 4 × 8 |
| 17 | ? | ? | ? | 4012 | 8 × 8 |
| 18 | ? | ||||
| 19 | |||||
| 20 | 15 × 16 | ||||
| 21 | 22 × 16 | ||||
| 22 | |||||
| 23 | |||||
| 24 | 52 × 32 | ||||
| 25 | 51 × 32 | ||||
| 26 | |||||
| 27 | |||||
| 28 | 257 × 64 | ||||
| 29 | 342 × 64 | ||||
Since this paper was written, the University of Dresden has extended the table as follows:
16 1846955 17 11977939 18 83263591 19 621012754 20 4878666808 21 39333324973 22 336376244042 23 3029242658210 24 28439272956934 25 275986683743434 26 2789712466510289
