### 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"   We heartily congratulate Matthias on his earlier discovery!

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)

• While the numbers above tell us how hard our search algorithms had to work in order to find each First Solution,
this Table Of First-Solutions page here  shows the end results of that hard work, namely the actual puzzle solutions.

• Or click here to step through a sample 5 x 5 board which shows how these numbers were obtained using my own algorithm.

• You can download from here my FREE Windows®-based program that calculates these same values shown above, for board sizes up to 32 x 32.