The N-Queens is a problem to place N queens on an N x N
chess board such that no queen can attack another (see http://en.wikipedia.org/wiki/Eight_queens_puzzle). More precisely, a
problem is to obtain the number of all such placements.
The last world
record was established for N =
25
2 207 893 435 808
352
and has been
owned by INRIA since 2005. The cumulated computing time was over
50 years for one processor.
Our solution is based on an algorithm
which uses symmetries. The corresponding code of a sequential program in
C# can be found here.
The algorithm consists of
two basic for-loops. We extracted these loops to the two separate (parallelized)
programs (see part I and part II).
For N = 26 it is
needed
(1)
23 runs of "part I"
program
(for BOUND1 = 2,3, ... , 24)
and
(2) 12
runs of "part II"
program
(for
A = 1,2, ... , 12).
In fact, for part II for A = 1 we divided the job further
on to 23 subjobs and for A = 2, ... , 12 we diveded each job on to 21 subjobs. A
total number of jobs for running on cluster was 277.
The number of solutions obtained
for each job can be found in the given
table
.
The total number of
solutions for N = 26
is
22 317 699 616 364 044
Our computation was
started on November 19, 2008 and ended on 30 August, 2009. To obtain a solution
of N-Queens problem for N = 26 we used two clusters
-
1) "SKIF MSU"
("Chebyshev", http://parallel.ru/cluster/skif_msu.html, #82 in June,
2009 Top 500),
Scientific Research Computational Center of the Moscow State University,
and
2) MVS-100K (http://www.jscc.ru/hard/mvs100k.shtml, #54 in June, 2009
Top 500),
Joint Supercomputing Center of Russian Academy of Sciences.
A sample
output protocol of one of the jobs can be found here. Zip-archive of all protocols can be
downloaded from here (0.5
Mbytes).
Our solution is a confirmation of
the result achived for the first time on July 11,2009 using FPGA technology (see
here
).