The N-Queens Problem


The N-Queens Problem
OR newsletter, January 1997, pp.13-14

Robert Simons's article in the October Issue of ORN described the n-queens problem and this has prompted me to try the problem myself. Bob Hattersley was quoted as saying that solving the problem for n = 30 in 35 sec on a 486 33Mhz machine was a fine achievement.

Although described as very hard, this problem is not so difficult to solve. On a thirty by thirty board, the 30 queens may be placed on squares (1,2), (2,4), (3,6) etc and (16,1), (17,3), (18,5) etc. Where n is one bigger, the second chain can be continued to the square: (31, 31). This pattern solves all boards where n has a remainder of 0, 1, 4 or 5 on division by 6.

[A book by J Beasley, 'The Mathematics of Games", gives the solution for the other cases. If n = 6k + 2 = 2r, then start with one line of queens (1,1),(2,3),(3,5) up to ... (r-l, n-3), (r,n-l). Then move the queens from the squares ( 1,1) and (r- 1 ,n-3) to the squares (r- 1,1) and (l,n-3). The queens on the remaining files should then be placed by axial symmetry. Adding a queen at the square (n+l,n+l) solves the board n+l x n+l where n+l =6k+3.]

Noticing that 30 = 6 x 5, with r = 6 and s = 5, the problem can be factored into the 6 queens problem where each square consists of a 5x5 board, and each 5x5 board is solved with (1,2), (2,4), (3,1), (4,3), (5,5). There is some subtlety here as it might have happened that two 5x5 squares a knight's move away from each other on the 6x6 board would interfere with each other, but inspection shows that they do not. This technique does not work for s = 4, but it does work for s = 5 and for s = 7 and presumably for other values, (perhaps where s is one more or less than a multiple of 6?).

The problem is not as large as might be thought from the comment that there are 1017 potential solutions to try when n = 30. A brute force search procedure, (taking each file in turn, and going back a stage whenever a file is blocked by previous choices), is feasible. The running times on a 486 66Mhz machine using a C programme gave n = 20, lOsec; 21=ls; 22=46s; 23=2s; 24= 29s; 25=3s;26=33s; 27=39s; 28=270s; 29=144s; 30 = 96min 32sec. This is a fascinatingly irregular pattern of times - which, of course, depends on where in the search the first solution comes. Unfortunately the exponential nature of the problem is beginning to get the better of this approach at n = 30. But if you throw in the constraint that queens on the left hand side of the board should be on a white square on odd files and on a black square on even files and vice-versa on the right hand side of the board, the machine gives a solution for n=30 in ONE SECOND!

I have also tried using a genetic algorithm approach. It is easy enough to get a near optimum result, eg with only two or three diagonal clashes, but getting a clean solution requires both luck and judgement. The distinctive step in a GA is to mate two trial solutions with each other in a way where there is a good possibility - not necessarily a probability - that the child solution is better than the two parents. In this way a population of trial solutions evolves so that its best member becomes an acceptable solution to the problem. With the n-queens problem, it is not obvious how to combine two patterns of n queens, so that we might take the best of each pattern. Of course, one can adopt some mechanistic procedure eg: for each file, put a queen on a rank occupied by a queen on that file in one of the parent patterns. However, a better method is to penalise squares which are attacked diagonally by a queen in either pattern, and then place a queen on the least penalised square in each file. Using this idea, one can get a solution for n = 30, in about 5 mins run time on the same computer. However, not much should be read into this time, as the programme is not claimed to be optimised for speed.

All in all, there are several ways to skin this cat.

Kenneth Evans
Time and Tide Ltd