n queen topics
Home
Group actions
Search algorithm
Use symmetry, regular NQ problem
Evolution trees
Special properties
Necklaces
Conflicts
Conflict tables
Smallest solutions and greedy sequence
Tables of counting results
Images for n=8
Torus images for n=13
Other pages to the n queens problem
Bibliografy
 
 
Other themes
Primes from sums of factors
Primes from wrong binomic formula
Numbers by primes distribution
 
Back to page about world records of all sizes.
 
 
This page in another language
German

World record Q27

Kleinste Lösung
The smallest solution

On this page, you can find some additional information about search and count of the (regular) n-queens solutions for a 27 by 27 board.

A memory aid for the number.

For people who can remember the first 1000 digits of Pi, the 18 digits of Q27 = 234,907,967,154,122,528 are obviously no problem. For all others, I give these hints:

  • Roughly speaking, the number is "a close quarter of a quintillion"; furthermore, the digits of the first group are a simple ascending sequence. This gives 234,000,000,000,000,000 (234 quadrillions) as approximation, neglecting rounding which would disturb the simple sequence 2-3-4.
  • The second and the third group of digits share begin and end, i.e. 9x7; for x, insert first 0 and then 6.
  • The last three groups are only one digit apart from a square, by a difference of one:
    group 4: 154 = 144 + 10, the decade is increased by one as against the square of 12.
    group 5 (last but one): 122 = 121 + 1, the unit position is increased by one as against the square of 11.
    group 6 (last group): 528 = 529 - 1, the unit position is decreased by one as against the square of 23.

Of course, you can also remember the prime decomposition: 234,907,967,154,122,528 = 32 * 7 * 17 * 83 * 277 * 397 * 6,785,533. No prime powers, except for the first term 32 which is two to the fifth. But be aware that you do not get the product back with a pocket calculator of 8 or 10 digits; even the pocket calculator of a smartphone will fail!

Validation of the result?

The result is not easy to validate. One should search and count again with a independent algorithm. Faster computers of the future will make it possible, but up to now (2020, January) I have not heard of someone undertaking this search.

Of course, one can check partial aspects and partial results from a independet point. Basically, the method is described here. Main question there: how can one exploit symmetry at all?

Next, one can review the theory thoroughly which was used in the project. It is available in the article Die Lösung des 27-Damen-Problems in the german periodical "Spektrum der Wissenschaft", with focus on practical aspects; more general and a bit more abstract in article An easy counting lemma in journal "Discrete applied mathematics".

Another validation is to apply the same algorithm to smaller boards. We did it for n = 17 to n=22, and we got the values which are known from former search and count.

Then, one can check partial results. As the problem was split into 2,024,110,796 (a good two billions) partial problems, each with 4 to 8 queens as preposition, one can check some of these cases by an independent program. We did it for a bunch of them, and could verify all these values. It included the two "big" prepositions of only four queens, and it included some prepositions of eight queens which give no solution at all.

If somebody is interested in doing more validation, we are happy to provide the database (ca 30 GB) or special entries of it.

Comparision with previous results

Previous searches had similar tables or databases. They had preplacements of all admissible placements of queens on the first four to six columns; with every item, the number of raw solutions found. For the 26 by 26 board, we have such a table; if you need it, we can provide it for you. We would be interested to get it also for sizes 23, 24, and 25.

Due to the different approach of the Q27 search, we do not have such a table of four or more columns for the preset. We have only a coarser table of preplacements for two columns. You may download it here for Q27, and the correspondig table for Q26 also. The same data, a bit edited, are available also in a LibreOffice spreadsheet; but caution - the sum in the end is not precise! This leads to the next section.

What is the problem for Excel or OpenOffice / LibreOffice, to show the number?

Above, I said that pocket calculators are not able to show the percise number. But also wide-spread spreadsheet editors like Excel (Microsoft) or OpenOffice / LibreOffice do not show the precise number. What is the reason for it? The number is big, but for a start not too big for a variable of type 'long' in Java or in C; these numbers are stored with 64 bit, minus one bit for the sign. The Q27 number has 58 bits "only", it fits into this format.

But the spreadsheet calculation programs do not use the Integer- or Long Integer format; they use the format of a 'double' variable in Java instead. This format has also 64 bits, but 12 of it are used for sign and an exponent; the remaining 52 Bits called mantissa are not enough! For complete presentation of the Q27 number, 6 bits are lacking! By the way, it is the same for the Q26 number; for Q25 the 52 bits are just enough.

Graphic charts for the distribution of the solutions.

Here, you can see some graphic charts for the distribution of the solutions.

Start of page
Prepared by Matthias Engelhardt
Mail to Matthias Engelhardt
 
last change: 2020-01-21
Address of page: http://nqueens.de/sub/WorldRecord_Q27.en.html