CSP Queens - Analysis Of The N-Queens Puzzle

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.
How Many Queens Must Be Placed Tentatively *
While Seeking A First Solution To The N-Queens Puzzle
(* "Tentative" is used here to mean all the "no solution yet" steps taken by my search algorithm.)
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" smile!  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
Document made with KompoZer 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. 		Creative Commons License