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 My Own 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,395,077,000,000,000 Search still in progress
47 x 47 351,874,509,051,227 9 January 2008
48 x 48 More than  1,368,964,000,000,000 Search still in progress
49 x 49 192,114,366,691,401 6 June 2008
50 x 50 More than 297,368,000,000,000 Search still in progress


A Related Link:
My son Martin's Queens On A Chessboard web site presents the same information as above, but enhanced by his excellent full-sized diagrams for each of the First Solutions we have found so far.  He also gives detailed descriptions 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 count for the 42 x 42 board contained in the 16 digits 1,435,630,462,823,151  is so huge that it can't be represented as an ordinary integer in either OpenOffice.org Calc (tested up to version 3.2), or in Microsoft Excel !

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.4 million Queens per second = many more than 650 days so far, in April 2010

Indirectly-related Links:
OpenOffice.org - Documentation Project
Microsoft Office Excel 2007 - Excel specifications and limits
Page Updated:  21st August 2010
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