Skip to: ContentEnd


My home on the Web

My Estimate for 46×46

The first solution for the 46×46 chessboard was taking our program an unusually long time to discover. Fortunately, in October 2010 we had been contacted by a German mathematician named Matthias R Engelhardt who shared our interest in the problem (and has also researched it from many other angles, all detailed on his website), and six months later on 30th April 2011 he offered us a first solution for the 46×46 chessboard generated by his own program. Using a copy of his program (and a German-to-English dictionary) we were able to verify this first solution on 4th July 2011, and naturally we were – and remain – very pleased to welcome Matthias's contribution to our research.

Matthias's program employed an improved version of the same basic algorithm that we were using, which analysed the progress at each stage to determine the optimal next step. Whilst this proved much quicker at discovering the first solutions, it wasn't able to count the number of Queens that would need to be placed to complete an exhaustive search – so I decided to compare the solution for the 46×46 chessboard with the progress so far of our own program to see if I could estimate when its search might come to an end, and how many Queens might need to be placed 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 differed between our program's progress and the first solution was 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 had 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 attack by other Queens, so Column 24 would be its next available step.

Turning my attention then to the Queen in Row 16 ("Q16") to see how long Q15 might take to make that leap, I found that Q16 had moved from Column 29 to Column 30 on the afternoon of 23rd July 2011. According to the log files the program had been keeping over its many years of processing, it moved into Column 29 from Column 28 around 16th April 2010, which indicated that Q16 moved about once every fifteen months.

Completion date

Now we knew the approximate rate at which Q16 moved, I could estimate how long it might be before we reached the first solution. Before Q15 could move from Column 10 to Column 24, Q16 needed to complete its journey across the board. It currently had seventeen Columns left to traverse – Columns 30 to 46 inclusive – so given that it occupied each Column for about fifteen months and none of them appeared to be at risk of attack by any other Queens, from 23rd July 2011 I calculated that it would probably be:

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

...before Q15 was able to move again. From that point I imagined that it wouldn't take long for the Queens above to arrange themselves into the first solution, so I suggested 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 own program's search for the first solution for the 46×46 chessboard.

Number of Queens placed

But how many Queens might we have ended up counting 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 estimated finish time of 21½ years (or 258 months), this meant we would count a further:

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

...before we found the first solution. Adding that to the 1.691 quadrillion Queens our program had already placed gave us an estimated total of 7.625 quadrillion Queens placed throughout an exhaustive search for the first solution for the 46 by 46 chessboard. Incredible!