The 24x24 Peaceful Queens ProblemIan ParberryDepartment of Computer Science and Engineering University of North Texas December 2008
IntroductionFor n ≥ 1, let Q(n) denote the number of ways of placing n queens on an n by n chessboard in such a way that no queen threatens to take any other (recall that in the game of chess a queen can move along any row, column, diagonal, or back diagonal of the board). This is known variously in the literature as the peaceful queens problem or the n queens problem. For example, Q(6) ≥ 4 since a solution can be constructed by placing the first queen in the second column of the first row and subsequent queens via knight's moves two columns across and one row down until the rightmost edge of the board is reached, then placing a queen in the first column of the subsequent row and again in knight's moves across the board. Three other distinct configurations can be obtain from this by rotations and reflections (see below).
What is Known as of 2008The following table from The On-Line Encyclopedia of Integer Sequences summarizes the state of knowledge about Q(n) as of the end of 2008.
Although Q(26) is the next open value, Q(24) is currently in contention since the NQueens@Home project claims that
compared to the 2004 figure of
from Kise et al. (Kenji Kise, Takahiro Katagiri, Hiroki Honda, and Toshitsugu Yuba, Solving the 24-queens Problem using MPI on a PC Cluster, Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communications, 2004.)
Somers' AlgorithmCommon opinion attributes the fastest known implementation of backtracking for the peaceful queens problem to Jeff Somers (see The N Queens Problem: A Study in Optimization). Benchmark running times for this program on a modern PC (Intel 3.3GHz quad core using a single core; we will return to the issue of multi-core computing in the next section) are given in the next table:
MultithreadingSomers' backtracking algorithm lends itself easily to multithreading to take full advantage of modern multi-core computers if we break the problem of counting all solutions to the peaceful queens problem into subproblems by computing independently the number of solutions with a queen in column m of row 0, for all 1 ≤ m ≤ n/2 (the latter number is n/2 not n because Somers' program uses a reflection about the vertical axis to reduce the running time), and then summing the results. This gives us potentially 12 threads for computing Q(24) Repeating this for the second row gives n2/2 threadable subproblems, of which one less than 3n/2 are null due to placement of the second queen in the same column, diagonal, or back diagonal as the first queen, or a total of n(n-3)/2 + 1 threads. This gives us potentially 253 threads for computing Q(24). Even more threads are made possible by utilizing the third row in this manner.Improvements to Somers' AlgorithmWe have been able to improve the performance of Somers' program by taking advantage of symmetries, for an improvement of around 20% over the original version.
Our ResultsIn October-November 2008 we ran our version of Somers' algorithm to recompute Q(24) on 12 Dell XPS quad-core computers in the Laboratory for Recreational Computing at the University of North Texas, finishing on November 11, 2008. Our result confirmed the value obtained in 2004 by Kise et. al., that is,
Our total elapsed time was 26 days, using approximately 39 months of single-core computing time. Our results are listed in detail here in the form of a 6-column table. The first 3 columns describe a subproblem of the 24-queens problem (that is, they list the columns in which queens can be placed in the first 3 rows of the solution), the fourth column lists the number of solutions for that subproblem, the fifth column lists the elapsed number of seconds for solving that subproblem, and the sixth column gives a comment on subproblems with zero solutions. For example, the following line from the table: 
tells us that there are 8,260,385,186 solutions that start with the following three queens:
Note that the number of solutions for each subproblem will be different from that obtained by Somers' code since we are using symmetries to reduce computation time. We also have data for 16x16, 18x18, 20x20, and 22x22 boards, but these are of less interest except to verify that the implementation of our modifications to Somers' algorithm is correct. |