For years (totalling thousands of hours) I have run my programs as a background task on various computers and servers, using progressively faster CPUs. But rather than seek the total number of solutions for each board size, for which I knew many others were searching, I focussed on seeking only the first solutions for those boards.
I define a "first
solution"
to this N-Queens puzzle as follows:
Assuming we start with a blank chess board, and assuming that we use the simple, step-by-step search algorithm which I describe here, where we step - laboriously, mechanically, sequentially and reliably - through every possible "no not yet" arrangement of Queens, then the "first solution" is the first arrangement of all N Queens which results in a "YES, GOTTIT" outcome.
From this point onwards, as our algorithm continues its search for maybe millions of subsequent solutions, we can guarantee that every subsequent arrangement of Queens will contain Queens in the same or later columns (or Files) on the board. No Queen on a particular row (or Rank) in any subsequent solution will appear in any earlier column than those discovered in that "first solution".
Assuming we start with a blank chess board, and assuming that we use the simple, step-by-step search algorithm which I describe here, where we step - laboriously, mechanically, sequentially and reliably - through every possible "no not yet" arrangement of Queens, then the "first solution" is the first arrangement of all N Queens which results in a "YES, GOTTIT" outcome.
From this point onwards, as our algorithm continues its search for maybe millions of subsequent solutions, we can guarantee that every subsequent arrangement of Queens will contain Queens in the same or later columns (or Files) on the board. No Queen on a particular row (or Rank) in any subsequent solution will appear in any earlier column than those discovered in that "first solution".
So - by using the algorithm which I summarise below, I have identified the first possible solution to all but two board sizes from 1 x 1 (a hypothetical board), via a 4 x 4 board (a trivial puzzle), all the way up to a board size of 49 x 49. The two exceptions which are still 'cooking' on my PCs are for board sizes 46 x 46 and 48 x 48.
Click here
to see the full table of all the First
Solutions I have found, most of which have been independently verified
by my son Martin.We like to think that maybe someone, somewhere, seeking other solutions (or all solutions) for a specific board size, might be helped by knowing the coordinates of the Queens as they appear in these first possible solutions.
Counter-intuitive Counter-swings
As well as seeking those first solutions to this puzzle, I have recorded how hard our Queens have had to 'work' as they step millions of times from square to square to square, trying to find those elusive squares on which they can rest, unchallenged by other Queens. Those counts of "tentative Queen placements" for the different board sizes have shown some fascinating and unexpected swings in magnitude!
As an example, comparing a 4 x 4 board with a 5 x 5 board: In order to add 4 non-clashing Queens to a simple board of 4 x 4 squares, we need to place a tentative new Queen 26 times before we discover the first combination that allows all Queens to sit unchallenged. However, when it comes to the board size of 5 x 5, one row and one column larger than the previous board, we only need to place our tentative new Queens 15 times before we discover the first combination of 5 unchallenged Queens! That smaller number of tentative Queens required for the larger board size seems (to me) to be delightfully counter-intuitive and illogical, and we see similar oddness and unpredictability while seeking that first solution on all of the larger board sizes.
Here's a table showing just some of the magnitude swings:
