Queens, at first glance

Sometimes obsession is a good thing. Without the ability to focus our thoughts we'd be nowhere today. Without a Dutchman obsessed with pornography we'd have no auto-focusing lenses on our cameras. Without a Japanese comic book artist steadfastly refusing to take her psychotic medication, we wouldn't have Sailor Moon. And finally, without Microsoft's obsession with copying every innovative high-tech company in the business, we wouldn't have the Xbox, Live Search, Zune, or a bunch of other products that no one uses. Cheap shot, I know.

It was obsession that led me to the subject matter at hand. A while ago I was called to do some interviewing. For this interview I had to think of a question. I was kind of lacking creativity that day so I decided to look at the Eight Queens problem. My introduction to this problem was way back in the ninth grade playing 7th Guest. It's a pretty easy problem to understand, and actually pretty fun to solve by hand. The goal for my interview question would be, obviously, to find a solution by computer. At that time, I decided that if I was going to ask this question, I better be able to solve it myself! So I took a quick lunch break to do so. It wasn't too hard—a fun diversion if you're programming-minded—and my own initial solution was pretty straightforward.

Soon, I wanted to make sure that my program was correct. I designed it to spit out all the solutions that it found and checked the first few by hand. They all looked fine. Then I saw the total number of solutions: on an 8 by 8 chessboard, my program claimed that there were 92.¹ So I cross-checked this against a known list and hey, whaddayaknowit, it matched. To make super-extra sure, I checked the number against some different sizes of chessboards. The numbers were weird, but they matched. Good, I think, it works.

The part of me that went through combinatorics (man that's a lot of links... am I really that hard to understand?) decided to think about how these numbers grow and how to count the number of solutions without actually going through the messy legwork of finding them all.² Well, it turns out that no one knows of a better way. In order to find out that there are 2 quadrillion-and-whatever solutions for a 25 by 25 board, you actually need to find each and every one of them. Not only that, you also need to find all the possibilities that could have led to solutions but didn't. That's just about 500 bajillion others.³

Twenty-five, by the way... that's the biggest chessboard anyone has ever solved. It's a world record, as far as I know. So that's when I wonder... what would be involved in conquering lucky number 26? So then I see the web page of the current record holder. The results? Over a period of six months, they used the combined resources of 260 machines. That was for a 25 by 25 board.

For 26, it's estimated that there are ten times as many solutions and that the computation will take ten times as long. That means that we either spend five years waiting for this thing to finish with 260 machines, or we somehow recruit 2600 suckers for a period of six months. I don't know about you, but I have better things to do for five years, and I don't even know 200 suckers, let alone 2000.

So what's a programmer to do? World record, interesting challenge, epic computation. I'm sold. Put it on my Visa. I'll pay in installments. I'm gonna take my shot at finding the twenty-something-quadrillion magic number.

But wait, you say, hold it a sec. What about the kabillion-jillion computations and the mind-numbing years it will take to solve this? You really don't know me, do you? Insert smilie here. I'm going to work smarter, not harder. That means, if I have ten times as much work to do, using the same amount of resources as you have, then I've got to pump out my solutions ten times faster than you. But that's okay. Won't be the first time I've done something like this.

And I'm going to need help. Lots of help.

(1) This count is for unique solutions. There are actually 12 solutions unique up to symmetry. Two solutions are considered the same up to symmertry if you can rotate the chessboard 90 degrees in either direction or flip it horizontally or vertically to transform one solution into the other. I'm only interested in counting solutions without symmetry.

(2) The best conjecture right now is that the number c(n) of solutions for an n by n chessboard is asymptotic to n! / (2.54^n). That means that c(26) is about 10 times greater than c(25). So the number of solutions we're expecting for c(26) is in the range of 22 quadrillion, or 22,000,000,000,000,000, give or take a few hundred trillion.

(3) My current algorithm appears to make around 38 times more steps than the total number of solutions. For example, on a 16 by 16 board, there are 14,772,512 solutions. The algorithm takes 570,595,151 steps to find all these solutions, giving a factor of almost 38. This trend appears to continue. I haven't found any references about calculating the number of guesses taken by various solutions. This also means that the solution to 26 will require about 836 quadrillion steps to make sure we've found them all. Now you see why we've no time to dawdle?

References.

ProActive NQueens World Record [http://proactive.inria.fr/nqueens25.htm]. Current world record holder. Used a distributed computing solution to solve the 25 by 25 case. The figures for the amount of computation required is taken from their web site. Their computation was later repeated and confirmed independently by a team in Taiwan.

Online Encyclopedia of Integer Sequences [http://www.research.att.com/~njas/sequences/A000170]. All known values of this sequence are here. So are links to existing record holders and the conjecture for the asymptotic growth of the solution count.

Wikipedia [http://en.wikipedia.org/wiki/Eight_queens]. Solution counts and a list of all solutions for an 8 by 8 board up to symmetry. Also includes a number of interesting links and variations of the puzzle. Note that the section "The eight queens puzzle as an exercise in algorithm design" seems to (confusingly) discuss two forms of the puzzle without explicitly stating which form is under discussion. The form I propose to undertake counts the total number of solutions for a given board size. The latter half of that Wikipedia section talks about finding a single solution on a large board, which is a much simpler problem.