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 possible solutions for those boards.
My definition of a "first
possible solution"
to the puzzle is simple and perhaps obvious, but it needs to be
defined.
So here it is:
Assuming we start with a blank chess board, and assuming we use the simple, step-by-step search algorithm which I describe here, we will step - laboriously, mechanically, sequentially and reliably - through every possible "no not yet" arrangement of Queens. The first possible solution is the first arrangement of Queens which allows all N Queens to sit uncontested on the board.
From this first possible solution onwards, as our algorithm continues its search for perhaps millions of other solutions, we can guarantee that every new solution will be a pattern of Queens that were placed in a later step of the sequence.
So here it is:
Assuming we start with a blank chess board, and assuming we use the simple, step-by-step search algorithm which I describe here, we will step - laboriously, mechanically, sequentially and reliably - through every possible "no not yet" arrangement of Queens. The first possible solution is the first arrangement of Queens which allows all N Queens to sit uncontested on the board.
From this first possible solution onwards, as our algorithm continues its search for perhaps millions of other solutions, we can guarantee that every new solution will be a pattern of Queens that were placed in a later step of the sequence.
Using this simple algorithm I have identified the first possible solution to all board sizes except two, from 1 x 1 (a hypothetical board), via a 4 x 4 board (which is a trivial puzzle), all the way up to a board size of 49 x 49. The two exceptions which I have not solved are the 46 x 46 board which has happily been solved by Matthias R. Engelhardt (as I describe on my Table Of First-Solutions page), and the 48 x 48 board, which is still 'cooking' on our PCs.
Click here
to see the full table of all the first
possible solutions that have been found so far, and 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:
