The First Solutions

This page lists the first possible solutions to the n Queens problem for various sizes of chessboard, and the numbers of Queens it is necessary to place whilst seeking those first solutions using our algorithm.

With three notable exceptions, the final Queen to be placed completes the first solution. Two of those exceptions are chessboard sizes 2×2 and 3×3, for which no solutions exist – their "Queens placed" counts are therefore the total numbers of Queen placements needed to search the entire chessboard. The third exception is the theoretical chessboard size 0×0, upon which zero Queens need to be placed to find the first and only technically valid solution to the problem of arranging 0 non-attacking Queens on a 0×0 chessboard – this is included both for the sake of completeness and for my own amusement.

Also worth mentioning here is the first and only technically valid solution for chessboard size 1×1, which – similarly to 0×0 – comprises just one Queen on the chessboard's single square.

Sources of data

The first solutions for all chessboard sizes that also have accurate Queen placement counts have been generated by a simple program written by my Dad, Colin using C++Builder. This is in fact the latest in a long line of similar programs that he's written to work on this puzzle over the years, beginning way back in 1975 using Assembly language on a big, slow old mainframe computer! The results for all chessboard sizes up to 39×39 have additionally been verified using a program I wrote independently in July 2008 using Turbo Pascal 7.01 (DOS Version); independent verifications by others for the first solutions (but not the Queen placement counts) for our remaining discoveries are credited in the right-hand column of the table.

For all other first solutions on this page (i.e. those with either partial, estimated, or no Queen placement counts), the earliest discovery known to us is again credited in the right-hand column of the table, along with a note stating whether or not we have verified them. And for the first solutions for some chessboard sizes larger than 55×55, please see this paper published on 26th February 2018 by Matteo Fischetti and Domenico Salvagnin of the University of Padua in Italy:

Chasing First Queens by Integer Programming
(with a local copy as backup)

I'm not aware of any further research that extends the list of first solutions beyond the above paper, but I would be very interested to know if any such research is published so that I might include it here.

Patterns in the data

We have found surprisingly few consistent patterns in the numbers of Queens placed whilst seeking the first solutions. As one might expect, there is a general trend for the numbers to increase along with the chessboard sizes, but within this trend the numbers actually fluctuate up and down quite considerably. The only consistent patterns we've identified so far are as follows:

• Each even-sized chessboard requires more Queens to be placed on it whilst seeking the first solution than the odd-sized chessboard immediately preceding it. For example, the total for 8×8 (876) is noticeably higher than the total for 7×7 (42).
• The total for an odd-numbered chessboard is always exactly divisible by the chessboard size. For example, the total for 11×11 is 517, which when divided by 11 gives 47.
• The total for an even-numbered chessboard is always exactly divisible by half the chessboard size, but it is NOT exactly divisible by the chessboard size itself. For example, the total for 6×6 is 171, which when divided by 3 gives 57, but when divided by 6 gives 28.5.

Fascinating facts

Some other details you might find interesting:

• The first chessboard size to require more than one million Queen placements to find its first solution was 20×20. With odd-sized boards generally producing their first solutions quicker than even-sized boards, the first odd-sized chessboard to require more than one million Queen placements was 25×25.
• Chessboard size 42×42 was the first to require more than one quadrillion (10¹⁵) Queen placements – that's a number with a massive sixteen digits! No odd-sized board within our research scope has required this many Queen placements.
• Two datasets from this research have been accepted into The On-Line Encyclopedia of Integer Sequences (OEIS): the numbers of Queens placed whilst seeking the first solutions on 26th June 2008 as sequence A140450, and the first solutions themselves on 10th July 2008 as sequence A141843.

Without further ado, here are the results of all our hard work, with the first solutions given in our simple co-ordinate notation. Click on any solution (in the third column of the table) to see it as a chessboard diagram.

As can be seen from the second column, we had continued searching for the first solutions to chessboard sizes 48×48, 50×50 and 51×51 even after Wolfram Schubert had discovered them, primarily because we were still interested in the numbers of Queens placed to reach them. However, eventually we did stop searching those three chessboards, and the partial counts of Queens placed in the table are the highest and most recent values from our research archive. Our progress on each of these chessboards can be summarised as follows:

48×48

The Queen on Row 15 ("Q15") was sitting in Column 10 when we stopped searching, with Q16 just over half-way across the board in Column 25. Q15's next available safe square would be in Column 24, which is where she would remain for the first solution; Q16 would then need to reach Column 26, which again would be swift as it would be her first safe square. It's therefore possible that this chessboard size would have completed its search within a reasonable timescale.

50×50

Here we had Q18 sitting in Column 29 with Q19 nearly two-thirds of the way across the board in Column 32. For the first solution Q18 needed to be in Column 36, and as every square between Columns 29 and 36 was safe, it probably would have taken her a long time to get there. Q19 similarly needed to be in Column 38 which also followed a long run of safe squares, thereby further slowing Q18's rate of progress.

51×51

On this chessboard Q20 was the next Queen that needed to reach her "first solution" destination. We had her in Column 34, just five safe squares away from where she needed to be in Column 39, which coincidentally Q21 currently occupied. As this is an odd-numbered chessboard it would probably have required fewer Queens to be placed than its even-numbered neighbour 50×50, and so this search might have finished second of the three, but still after a considerable length of time.

While we may return to this project in the future to continue counting the numbers of Queens placed for one or more of these chessboard sizes, without a significant investment of time and processing power it's unlikely we'd ever be able to fill the gap that is the 46×46 chessboard, so our dataset would always remain incomplete. As things stand, we have a continuous set of counts up to 45×45 – for many of which we were also the first to discover the first possible solution – and that in itself is a significant achievement.

Return to Top