n queen topics
This page in another language
World records for the n queens problem
World records and world championship for the n queens problem
It is a big challenge to determine the number of solutions when the size of the board increases.
This is especially true for the "normal" n-queens problem, to a lesser extent also for the torus problem.
"Normal" solutions are much easier to find, but there are many more of them.
For the torus problem, you can use the symmetries much better which compensates for the harder search.
Of course, it is a question of taste whether to call a new number for a bigger board as a world record.
That's what we do here, but we do not mean it very serious.
Practically, if you have found a new number, you put it into the On-Line Encyclopedia of Integer Sequences.
So, your record is documented. You may then get questions or requests for partial results, from people who try to verify the new number.
Besides the basic counting, there is also a World Championship of n-queens computing;
it is a competition. Several teams, which have prepared a program and often a special computer, get the task to count a known part of the problem again,
and to do it in the shortest time. The last World Championship of n-queens computing I know
was held in the year 2007 in Peking (China).
In the following table, I have compiled what I know about these world records. The abbreviation
INRIA appears several times; it stands for "Institut National de Recherche en Informatique et en Automatique",
the national institute of computer science and automation of France.
The regular n queens problem
|Regular n-queens problem |
|up to n=11
||The numbers were determined until 1890, in laborious manual work
|n=12 und n=13
||A. Kopfermann from Berlin (Germany) determines the numbers, manually; unfortunately, an error creeps in.
in the year 1971, Mark B. Wells at Los Alamos Scientific Laboratory (USA) determines the correct numbers with a computer.
|n=14 bis n=20
||By use of computers, the numbers are found between 1972 and 1997; I do not know who found which number, and when it was found.
|n=21 bis n=23
||Sylvain Pion and Joel-Yann Fourre of INRIA, 1998. They use 300 processors,
which count and search for two months.
||A web project, NQueens@home, on the BOINC platform, computes the number;
again, an error creeps in: some partial results were too big, there were undetected overflows of 32 bit integers arthmetic, the number is wrong (too small).
On September 1, 2004, Kenji KISE from Japan found the correct numbers for Q24.
||Denis Caromel (Nizza University, and at INRIA) determines the number Q25 in 2005.
He usese 260 usual PCs, which work about three quaters of a year.
||On July 11th, 2009, a team of TU Dresden (technical university of Dresden, Germany)
published its result for Q26. The team consists of Thomas Preußer, Bernd Nägel, and Rainer Spallek.
They have used FPGAs (= field programmable gate array) to find it.
According to a publication of March, 2009, it is 11 computers controlling 377 FPGAs.
Shortly after that, on August 30th, 2009, the russian project MC# confirms the number.
The project MC# has used two super computers, number 54 and 82
of the Top500 list of computers of June 2009.
They needed the time from November 19th, 2008, to August 30th, 2009, for the computation.
Yet, I do not know if they needed the complete time, or if they just used
time not used by other projects.
On September 19, 2016, Thomas Preußer of TU Dresden and his team did it again:|
Q27 = 234,907,967,154,122,528.
Again, they used FPGAs, which have evolved quite a bit, since 2009.
Another point: this was the first time that symmetries were exploited in a better way (see also Use symmetry for regular n-queens problem).
The team used coronal preplacements instead of the first columns. It was a two cell coronal margin, instead of six coulmns with the n=26 case.
More information on Neuer Weltrekord für Queens@TUD-Team, a page of TU Dresden, at present in German.
More information on Q27.
The torus problem
For the torus variant, there are solutions only, if n is not divisible by 2 nor divisible by 3.
Up to n=11, only regular solutions exist, what means that there is a constant distance
from a queen in a row to the queen in the next row.
The problem becomes intresting only from n=13.
Start of page
|n=13, n=17, n=19
||I do not know who computed these numbers first.
I would appreciate hints if you should know who it was, and when.
||The number was computed first in a project
concerning the programming language LeLisp;
it was done on 20 SUN workstations at INRIA.
It needed 267 days of CPU time, over all. I do not know when it was exactly,
but it must have been before 1994.
||December 17th, 1999, by the author of this site, Matthias Engelhardt;
the search needed about 4 weeks of CPU time on a 75 MHz Intel computer.
For the algorithm, the minimisation of the search space was most important.
||January 11th, 2001, also by the author of this site.
The search needed about 200 days of CPU time on a 300 MHz Intel computer.
For the final compilation of all solutions, a 800 MHz computer was used, which needed about 2 days.
The serch algorithm is described here;
it uses the group action "congruency on torus".
||May 1st, 2005, also by the author of this site.
Again, the search lasted about 200 days, using five PCs
of 120 MHz, 300 MHz, 800 MHz, 1,6 GHz and 1,9 GHz.
Therefore, I have no good estimate for the overall CPU time.
The search algorithm is described in this site,
in the section "Improvement 7: Further, bigger groups of symmetries", at the end;
it uses the group action "similarity on the torus".
||The author is working to prepare and execute the search this size, since more than a year.
This is described in a own page.
The search uses the action of a still larger group and the methodology of the "Easy counting lemma".
Even with these tools, the search needs much computing effort. This is supported by Lino GmbH in Mainz:
the search may use one of its servers under idle times.