### Counting How Many Queens Are Placed Tentatively While Seeking A First Possible Solution To The N x N Queens Puzzle.

Since I started writing computer programs in 1975, I've been intrigued by this puzzle of placing N Queens on an N x N board so that no Queen is challenged by any other Queen.

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.

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:
 Size of board Number of tentative Queen placements needed prior to discovery of the first solution 4 x 4 26 5 x 5 15 6 x 6 171 7 x 7 42 8 x 8 876 9 x 9 333 10 x 10 975 11 x 11 517 12 x 12 3066
The only 'pattern' in those numbers is that the even-numbered board sizes demand a higher number of tentative Queen-placements than the odd-numbered board sizes.  Otherwise, the degree by which adjacent board sizes differ is deliciously unpredictable!

Click here to see a table which shows the counts of 'tentative Queen placements' for most of the board sizes calculated so far, from the hypothetical 1 square by 1 square up to the enormous 49 squares by 49 squares.

The Queen-Placement Algorithm
The following pages describe one specific method of searching for a solution to the N-Queens on a chessboard.  There are other search schemes, but this one (which, for the sake of clarity if not conciseness I'll call the "one Queen at a time, tentative-placement scheme") is the one I've used in the C and C++ programs that I've written and dabbled with for decades.  A key feature of this algorithm is that, while it can find all possible solutions to an N x N board, it is guaranteed always to identify the first of those solutions. (Note that for this illustration, I stop immediately on the first solution and I don't look beyond it for any of the large number of further solutions that would appear if it was allowed to continue running.)

This algorithm can be applied to any board size.  In the example that follows I use a board size of 5 x 5 because it needs the fewest number of tentative placements while still showing a reasonable number of intermediate steps.  I make no claims about possible optimisations or shortcuts which could speed up this algorithm.  In fact the algorithm is simple, mechanical and pedantic and - unless you're a computer - it's very boring ... But it is thorough, it is repeatable and it is exact.

My aim is simply to show how this algorithm finds the very first possible solution for a particular board size, and to show how I count the number of Queens placements that lead to that solution.

• Click here to see the sample  5  x  5  board which illustrates the counting scheme I've used.
• Click here to see a proposed "known next coordinate" notation schema for describing solutions to this puzzle.