This is just one of many pages from my analysis of the N-Queens puzzle, on which I've worked as a pastime since 1975. More recently, in collaboration with my son Martin, this analysis has 'expanded' from these now mundane 2-dimensional boards, into much more challenging 3-dimensional Cube versions of the puzzle.
Size Of Board | Count Of Tentative Queen Placements Needed Prior To Discovery Of First Solution | Date Of Our Discovery Of The First Solution | Other Notes |
1 x 1 | 1 | This 'solution' is one single Queen! | |
2 x 2 | 6 | No solution exists for size 2x2 | |
3 x 3 | 18 | No solution exists for size 3x3 | |
4 x 4 | 26 | 1975 | |
5 x 5 | 15 | 1975 | |
6 x 6 | 171 | 1975 | |
7 x 7 | 42 | 1975 | |
8 x 8 | 876 | 1975 | |
9 x 9 | 333 | 1991 or earlier | < 1 second on a Tulip^{®} 80386/25 PC |
10 x 10 | 975 | 1991 or earlier | < 1 second on a Tulip^{®} 80386/25 PC |
11 x 11 | 517 | 1991 or earlier | < 1 second on a Tulip^{®} 80386/25 PC |
12 x 12 | 3,066 | 1991 or earlier | < 1 second on a Tulip^{®} 80386/25 PC |
13 x 13 | 1,365 | January 1991 | < 1 second on a Tulip^{®} 80386/25 PC |
14 x 14 | 26,495 | January 1991 | < 1 second on a Tulip^{®} 80386/25 PC |
15 x 15 | 20,280 | January 1991 | < 1 second on a Tulip^{®} 80386/25 PC |
16 x 16 | 160,712 | January 1991 | < 1 second on a Tulip^{®} 80386/25 PC |
17 x 17 | 91,222 | January 1991 | < 1 second on a Tulip^{®} 80386/25 PC |
18 x 18 | 743,229 | January 1991 | 18 seconds on a Tulip^{®} 80386/25 PC |
19 x 19 | 48,184 | January 1991 | 1 second on a Tulip^{®} 80386/25 PC |
20 x 20 | 3,992,510 | January 1991 | 1 min 46 s on a Tulip^{®} 80386/25 PC |
21 x 21 | 179,592 | January 1991 | 6 seconds on a Tulip^{®} 80386/25 PC |
22 x 22 | 38,217,905 | January 1991 | 18 min 3s on a Tulip^{®} 80386/25 PC |
23 x 23 | 584,591 | January 1991 | 17 seconds on a Tulip^{®} 80386/25 PC |
24 x 24 | 9,878,316 | January 1991 | 4 min 48 s on a Tulip^{®} 80386/25 PC |
25 x 25 | 1,216,775 | January 1991 | 37 seconds on a Tulip^{®} 80386/25 PC |
26 x 26 | 10,339,849 | January 1991 | 5 min 15 s on a Tulip^{®} 80386/25 PC |
27 x 27 | 12,263,400 | January 1991 | 6 min 32 s on a Tulip^{®} 80386/25 PC |
28 x 28 | 84,175,966 | January 1991 | 45 min 5 s on a Tulip^{®} 80386/25 PC |
29 x 29 | 44,434,525 | January 1991 | 25 min 25 s on a Tulip^{®} 80386/25 PC |
30 x 30 | 1,692,888,135 | January 1991 | 16 h 7 min 37 s on a Tulip^{®} 80386/25 PC |
31 x 31 | 408,773,285 | January 1991 | 4 h 2 min 47 s on a Tulip^{®} 80386/25 PC |
32 x 32 | 2,799,725,104 | 17 May 1997 or earlier | |
33 x 33 | 4,618,568,460 | 17 May 1997 or earlier | |
34 x 34 | 78,016,579,095 | 28 July 2008 | Verified & corrected on this date |
35 x 35 | 8,244,234,495 | 7 February 1998 | |
36 x 36 | 883,134,227,754 | 11 February 2002 | See Note 3 below |
37 x 37 | 37,481,487,475 | 7 February 1998 | |
38 x 38 | 605,847,021,365 | 9 February 2002 | |
39 x 39 | 444,710,580,405 | 12 December 2001 | |
40 x 40 | 18,325,192,478,100 | 13 August 2008 | Verified & corrected on this date |
41 x 41 | 670,447,199,438 | 15 February 2002 | |
42 x 42 | 1,435,630,462,823,151 | 8 March 2008 | See Note 2 below |
43 x 43 | 9,387,957,604,049 | 26 March 2002 | |
44 x 44 | 168,220,196,252,658 | 15 November 2004 | |
45 x 45 | 151,162,963,331,040 | 14 July 2005 | |
46 x 46 | More than 1,650,468,000,000,000 (Matthias counted backtracks - See note below) |
30 April 2011 | Discovered by Matthias R. Engelhardt |
47 x 47 | 351,874,509,051,227 | 9 January 2008 | |
48 x 48 | More than 1,813,325,000,000,000 | Search still in progress | |
49 x 49 | 192,114,366,691,401 | 6 June 2008 | |
50 x 50 | More than 388,476,000,000,000 | Search still in progress |
Update On The First Solution For The 46 x 46 Board
As I have explained in more detail on my Table Of First-Solutions page, Matthias Engelhardt successfully revealed the algorithmically-first solution to the 46 x 46 board on 30th April 2011. In his solution searches, Matthias used a significantly different algorithm and methodology from the one that Martin and I have used so far, and whereas Martin and I have been counting the number of tentative queen-placements that occurred prior to my algorithm's discovery of a First Solution, Matthias has maintained a count of the number of backtracks that his algorithm negotiated during its search. Matthias describes his (evidently more efficient!) algorithm and his more sophisticated methodology on his own web-page here - My search algorithm for the n queens problem. Matthias's work on this puzzle has been more mathematically-based than my own, and I readily commend his notes to you!
Note that the Count Of Tentative Queen Placements shown in this 46 x 46 row of the table is the approximate count - accumulated over many years - of queen-placements recorded by one of Martin's computers, prior to Matthias's discovery of this board's First Solution. Naturally Martin stopped running his instance of my search program once we knew that Matthias had "got there first" We heartily congratulate Matthias on his earlier discovery!
A Related Link:
My son Martin's Queens On A Chessboard web site presents the same information as in my table above, but his presentation is enhanced by excellent full-sized diagrams for each of these First Solutions. He includes a very detailed description of his own work on this puzzle.
Additional Information On The Table Above:
Note 1: The values in rows coloured green have been verified by Martin Pearson.
Given that any verification of these results should be obtained using methods as different as possible from my own long-in-the-tooth C++ code, Martin has written his own solution-search program, entirely from the ground up in Turbo Pascal. Importantly, he uses a variation on my search algorithm, plus a search-optimisation scheme which I did not use to obtain my original values. We look forward to having all the values verified (or corrected if appropriate!) in due course.
Note 2: The magnitude of the counts shown in RED above are so huge that they cannot be represented as ordinary integers in either OpenOffice.org Calc (tested up to version 3.2.1), or in Microsoft Excel. These spreadsheet programs comply with the IEEE 754 Standard for Binary Floating-Point Arithmetic, which also influences the storage and handling of integers, so they can only accept and display integers of 15 digits or fewer without the probability of errors occurring after the numbers have been entered. (See "Indirectly-related Links" below).
Note 3: Correction - 2nd April 2010
The 36 x 36 board was solved by me no later than 11th Feb 2002, not 2007 as was previously shown. Sorry!
The approximate uninterrupted CPU time needed to calculate some of these terms are as follows:
Using a Borland (Inprise) Builder C++ program which was not especially optimised for speed,
running under Microsoft Windows XP Professional, SP3 (32-bit)
on an Intel x86, Family 15, Model 6, 3.4GHz Pentium D CPU 945 (using one core only):Board size 35 x 35 at 24.0 million Queens per second = 6 minutes
Board size 38 x 38 at 22.8 million Queens per second = 7 hours
Board size 45 x 45 at 20.9 million Queens per second = 84 days
Board size 47 x 47 at 20.5 million Queens per second = 199 days
Board size 48 x 48 at 18.5 million Queens per second = more than 1000 days (as measured in December 2010)
Indirectly-related Links:
OpenOffice.org - Documentation Project
Microsoft Office Excel 2007 - Excel specifications and limits
Floating-point arithmetic may give inaccurate results in Excel - Microsoft Knowledge Base Article 78113
Standard for Binary Floating-Point Arithmetic - IEEE 754
Page Updated: 28th October 2011
Content on this CSP Queens site
by Colin S Pearson and Martin S Pearson
is licensed under a Creative Commons Attribution-Non-Commercial-Share Alike 2.0 UK: England & Wales License. Permissions beyond the scope of this license may be available via the feedback page. |