The N Queens Puzzle

My Estimate For 46 by 46

After we had verified Matthias Engelhardt's discovery of the first solution for the 46 by 46 chessboard on 4th July 2011, I decided to compare it with the progress so far of our own program and see if I could estimate when its search might come to an end, and how many Queens it might need to place along the way. What I came up with is very much an educated guess, but it's probably not too far off-target.

Rate of Progress

The lowest Queen that differs between our current progress and the first solution is the one that occupies Row 15 (hereinafter referred to as "Q15"). In the first solution this Queen is sitting in Column 24, but our program has it still in Column 10. However, a quick hand-drawn diagram of the fourteen Queens below it soon revealed that all of the squares on Row 15 between Columns 10 and 24 were at risk of capture by other Queens, so Column 24 would be its next step. I then turned my attention to the Queen in Row 16 ("Q16") to see how long Q15 might take to make that leap.

Q16 moved from Column 29 to Column 30 on the afternoon of 23rd July 2011. According to the log files the program has been keeping over its many years of processing, it moved into Column 29 from Column 28 around 16th April 2010, which tells us that Q16 moves about once every fifteen months.

Completion Date

Now we know the approximate rate at which Q16 moves, we can estimate how long it might be before we reach the first solution. Before Q15 can jump from Column 10 to Column 24, Q16 needs to complete its journey across the board. It currently has seventeen Columns left to traverse - Columns 30 to 46 inclusive - so given that it occupies each Column for about fifteen months and none of them appears to be at risk of capture by any other Queens, from 23rd July 2011 it will probably be:

17 Columns × 15 months = 255 months or 21¼ years

...before Q15 is able to move again. From that point I suspect it wouldn't take long for the Queens above to arrange themselves into the first solution, so I would suggest a conservative finish time of January 2033. We were somewhat surprised - not to say disappointed - by this, but in the end we decided that another 21½ years of counting Queens wasn't worth the wait and called a halt to our search for the first solution for 46 by 46.

Number of Queens Placed

But how many Queens might we have ended up counting over the next 21½ years if we'd carried on? A look back at the last few months' log files revealed that on average our program counted 23,000,000,000,000 (that's 23 trillion) Queens per month. Given my conservative finish time of 21½ years, this means we would count a further:

258 months × 23,000,000,000,000 Queens = 5,934,000,000,000,000 (5.934 quadrillion) Queens

...before we found the first solution. Adding that to the 1.691 quadrillion Queens our program has already placed gives us an estimated total of 7.625 quadrillion Queens placed in the search for the first solution for the 46 by 46 chessboard.