Technical Report UEC-IS-2004-6, Version 2004-06-14
Graduate School of Information Systems, The University of Electro-Communications

Solving the 24-queens Problem using MPI on a PC ClusterKenji KiseÝ , Takahiro KatagiriÝ , Hiroki HondaÝ , and Toshitsugu YubaÝÝ
Graduate School of Information Systems
The University of Electro-Communications

Abstract

cussed in the context of computer science and has been used
as an example for the backtracking algorithms[4], the divideand conquer paradigm[5], and constraint satisfaction problems.
We attempted to speed up and parallelize the sequential
N-queens program for the purpose of calculating the solution of the 24-queens problem, which was not obtained until
recently[6].

The N-queens is a problem to place N queens on an N 
N chess board such that no queen can attack another. We designed a sequential program which attains an improvementin speed of from 7% to 14% compared to current programs.
The proposed program is parallelized using MPI, and thenumber of solutions for the 24-queens problem is calculated
for the first time. The main findings of the present study areas follows: (1) The optimization of memory reference andcontrol structure increases speed from 7% to 14% in the sequential program. (2) A master-worker scheme is effective
for parallelization. (3) The Hyper-threading technology ofthe Pentium4 processor provides an increases in speed ofapproximately 30%. (4) In the solution of a real problem, it
is important to consider the efficiency of the entire system.

2 Estimation of the computation time of thesolution to the 24-queens problem
The proposed program is based on a heavily optimized
C program written by Jeff Somers[7]. Somers program isalmost twice as fast as the world record breaking programused to calculate the solution to the 23-queens problem.
The proposed program is from 7% to 14% faster thanthe Somers program. This increase in speed is achievedby the optimization of memory reference and control flowstructure.
The processing speed of the proposed program is measured, and the time required to solve the 24-queens problem is estimated. We measured the time on a computer having a Pentium4 Xeon 2.8-GHz processor, which is widelyused and cost-effective. The computation time from N=17
to N=20 is acquired by measurement. Based on the obtained rate of increase, the computation time from N=21 to
N=24 is estimated. The problem size N and computation
time (seconds and days) are summarized in Table 1. The
estimated time is indicated in bold.
The estimation summarized in Table 1, reveals that 2,815
days are required in order to calculate the solution of the 24queens problem.

1 Introduction
The N-queens is a problem to place N queens on an N 
N chess board such that no queen can attack another. For example, the 6-queens problem has four solutions, as shown inFigure 1. This problem is commonly used as a benchmark
program [1, 2] for computer systems and as an example incomputer science.

Figure 1. Four solutions to the 6-queens problem.

3 Parallelization of the N-queens Program
The estimated computation time of 2,815 days or 7.7
years for the calculation of the solution of the 24-queens
problem is not realistic. However, the program can be parallelized and the computation time can be shortened to 44days by using a PC cluster having 64 CPUs. In this section,

The N-queens problem was originally introduced as the8-queens problem by a chess player named Max Bazzel in1848[3]. Since its introduction, this problem has attracted
the attention of several famous mathematicians, including
Carl Gauss. Recently, the N-queens problem has been dis1

Table 1. Number of solutions and estimated time required to solve the 24-queens problem on acomputer having one processor.
size N number of solutions
our code (sec) our code (day)Somers code (sec)
1795,815,104
55.5
0.00
59.5
18
666,090,624
384.8
0.00
440.5
19
4,968,057,848
3168.60.04
3417.520
39,029,188,884
24329.7
0.2827745.8
21314,666,222,712
2432972.82–
222,691,008,701,644
2432970
28.16–
23
24,233,937,684,440
24329700
281.59–24–227239317
2815.94–a technique for the efficient parallelization of an N-queens
program is summarized.
Parallelization of a sequential program requires the calculation to be divided into a large number of tasks. An algorithm that places queens in order from the upper row to
the lower row on an N  N chess board is adopted. Afterthe initial placement of a number of queens, the processing of the remaining queens is handled as one task. Eachgenerated task is calculable in parallel as an independentproblem. The first four decomposed tasks for the 6-queens
problem are shown in Figure 2. In the figure, each task isgenerated after the placement of the first two queens.

tasks, and the average time required to complete one task.
In the case of 24-queens, the set of calculations is broken up
into 75,516 tasks. The average time to complete one task is
as long as 3,009 seconds, and it is possible to conceal theparallelization overhead.
The task-scheduling algorithm is examined next. In thecase of the 23-queens problem, the calculation is broken
up into 64,072 tasks. Measurement revealed that the computation time of each task varied from 45 seconds to 840
seconds. The 64,072 tasks were sorted according to calculation time, and the distribution of the calculation times isshown in Figure 3. The vertical axis shows the computationtime. Prediction of the calculation time and the adoption of
static scheduling appear difficult. We therefore parallelize
our N-queens program using a master-worker scheme. One
process is assigned as a master and all other processes operate as workers. MPI, a standard of parallel programming,is used for parallelization.

4 Parallelization efficiency of the N-queens
programFigure 2. The first four decomposed tasks outof 24 tasks for the 6-queens problem. Eachtask is generated after the placement of thefirst two queens.

4.1 Efficiency of the parallelized programThis section discusses the efficiency of the parallelized
program. The measured increase in speed when the program is run on a PC cluster having four Pentium4 Xeon
2.8-GHz processors is summarized in Figure 4. The horizontal axis is the problem size N, and the vertical axis is thespeedup based on the elapsed time of the sequential program without the parallelization overhead. Hyper-threading
technology, which uses one physical CPU as two logicalCPUs is available on Pentium4 Xeon processor. The increase is measured for configurations in which the Hyperthreading is either on or off.
The speedup without Hyper-threading technology is discussed. When the problem size is N=16, the elapsed timeis short and the overhead for parallelization becomes notable. The speedup of 3.16 is much lower than the numberof processors. On the other hand, the speedup approaches

Table 2. Number of decomposed tasks andestimated time per task.
size N number of tasks time (sec) per task
2030,880
0.91
2141,176
6.13
2249,480
45.93
2364,072
354.662475,516
3009.15
The calculation after the placement of the first fourqueens is considered to be one task with respect to both thenumber of tasks and the calculation time for an individualtask. Table 2 summarizes the problem size N, the number of2

Figure 3. Distribution of the elapsed time of 64,072 tasks in 23-queens. All tasks are sorted by elapsedtime.

Figure 4. Increase in speed for calculation performed on a PC cluster having four physical CPUs.

4.2 Speedup with respect to the increase in thenumber of nodes

the ideal value 4 as problem size becomes large. When theproblem size is N=20, the speedup is 3.91 using four CPUs.
This is as high as 97.8% of the ideal speedup for four CPUs.

This section discusses the speedup with respect to theincreases in the number of nodes. The 34-node PC cluster
called FireCore is used in our evaluation. Each computer
node is an SMP having two Pentium4 Xeon 2.8-GHz processors. Clustermatic 4[8] is used as middleware. Photosof a computer node and the FireCore cluster are shown inFigure 5.
The speedup for the 20-queens problem as the numberof nodes increases is shown in Figure 6. The vertical axis isthe speedup based on the elapsed time with one node. Eachnode uses Hyper-threading technology and four processes
are generated per node. Figure 6 indicates that an improvement in speed of approximately 35 times is attained usingThe speedup using the Hyper-threading technology isdiscussed. In solving the 24-queens problem, the part ofwhere the problem size becomes large is important. Whenthe problem size is N=20, the high rate of speedup of 5.12,
which exceed the number of physical CPUs, is achieved.
Compared to the case in which Hyper-threading is off, a30% improvement in speed is achieved.
These results show that Hyper-threading technology
works effectively for the N-queens program. In the solutionof a real problem, it is important to consider the efficiencyof the entire system.
3Figure 5. Photographs of a node computer having two processors and the 34-node PC cluster called
FireCore.

Figure 6. Increase in calculation speed of the 20-queens solution on the FireCore Cluster as thenumber of nodes increases. Hyper-threading technology is used.

4

6 Discussion
Table 3. Number of solutions calculated
and the elapsed calculation time using theFireCore Cluster to solve the N-queens problem.
size N
number of solutionstime (sec)
11–
20–
30–
42–
510–
64–
740–
892–
9352–
10724–112,680–
12
14,200–13
73,712–
14
365,596–15
2279,184–
16
14,772,512–
17
95,815,104–
18
666,090,624
12.02
19
4,968,057,848
42.56
20
39,029,188,884
286.0921
314,666,222,712
2497.8222
2,691,008,701,644
21002.19
23
24,233,937,684,440
204750.38
24
227,514,171,973,736 1879831.94

6.1 Verification
We next argue the validity of the obtained number of solutions. As one means by which to confirm the validity ofthe obtained number, we confirmed that the number of solutions for the 17-queens problem to the 23-queens problem calculated using our program was in agreement with
the number of solutions obtained in the past. This calculation was performed under an environment identical to thatfor the 24-queens calculation.
The computer used to obtain the number of solutions
for the 24-queens problem uses highly reliable Pentium4
Xeon processors. The main memory functions as the ECC,
which performs detection and correction of incorrect values. The FireCore cluster used to obtain the data is located in a temperature-controlled computer room. The obtained data was calculated on a computer having these highreliability components and was located in a desirable environment. The reliability of the data is high.

6.2 The N-queens problem as a benchmark program
Our program is described compactly using the C language and its code is easy to understand. All codes aredescribed in one file, and compiling and execution are veryeasy.
From these features, our program is suitable for use asa benchmark program for computer systems. Our sequential N-queens program and an MPI parallelized version areavailable from our web site. The program can be used as abenchmark program and as a base for solving the 25-queensproblem.

32 nodes.
The results in Figures 4 and 6 indicate that our parallelization of the N-queens program works well.

6.3 Solution on a large-scale PC cluster

5 Calculation result for the N-queens problem

Large-scale PC clusters, such as the ASCI Lightning,
having 2,816 processor, were constructed. The solution oflarge problems may be calculated on a large-scale PC cluster. In the case of 2,816 processors, as compared with thePC cluster of 68 processors used for the 24-queens problem,
an improvement in speed of approximately 40 times can beexpected. If the large-scale cluster is used, the solution to
the 24-queens problem is calculable in approximately 14
hours and the solution to the 25-queens problem may be
calculable in approximately six days.
However, in order to run on a large-scale cluster, it isnecessary to describe a program under the consideration of
the failure of a computer node. Moreover, it is difficult touse a very expensive large-scale cluster for a long time. If
these problems are solved, the use of a large-scale cluster
will be an attractive choice.

The number of solutions of the N-queens problem calculated using our program is summarized in Table 3. The
elapsed time on the FireCore cluster is shown for cases inwhich problem size is larger than 18.
We successfully calculated the 24-queens problem forthe first time. The bold letters in Table 3 indicate the number of solution and the elapsed time for the solution ofthe 24-queens problem. It required about 22 days. The
computation was started at 3:00 a.m. on March 21, 2004
and ended at 9:00 p.m. on April 11, 2004. The value
227,514,171,973,736 was acquired as the number of solutions of the 24-queens problem.
57 Summary
We attempted speedup and parallelization of a sequential
N-queens program for the purpose of calculating the number of solution of the 24-queens problem.
We designed a sequential program which achieves a 7%
to 14% improvement in speed compared to the currently
used program. Our program is parallelized using MPI andthe number of solutions for the 24-queens problem is calculated for the first time using a PC cluster.
The primary findings of the present study are as follows:(1) Optimization of memory reference and control structure
achieves a 7% to 14% increase in speed for a sequentialprogram. (2) A master-worker scheme is effective in theparallelization. (3) The Hyper-threading technology of thePentium4 processor achieves an increase in speed of approximately 30%. (4) In the solution of a real problem, it
is important to consider the efficiency of the system as awhole.

References[1] J. R. Gurd and D. F. Snelling. Manchester data-flow: aprogress report. In Proceedings of the 6th international
conference on Supercomputing, pages 216–225, 1992.
[2] Michael D. Noakes, Deborah A. Wallach, andWilliam J. Dally. The J-machine multicomputer: anarchitectural evaluation. In Proceedings of the 20th annual international symposium on Computer architecture, pages 224–235, 1993.
[3] Cengiz Erbas, Seyed Sarkeshik, and Murat M. Tanik.
Different perspectives of the N-Queens problem. InACM annual conference on Communications, pages
99–108, 1992.
[4] Solomon W. Golomb and Leonard D. Baumert. Backtrack programming. J. ACM, 12(4):516–524, 1965.
[5] Bruce Abramson and Moti Yung. Divide and conquer
under global constraints: a solution to the n-queens
problem. J. Parallel Distrib. Comput., 6(3):649–662,1989.
[6] http://www.research.att.com/ njas/sequences/. The OnLine Encyclopedia of Integer Sequences.
[7] http://www.jsomers.com/. The N Queens Problem, astudy in optimization.
[8] http://www.clustermatic.org/. CLUATERMATIC! Redesigning the Cluster Architecture.

6