Raising the Bar - New World Record by Exploring the 27-Queens Puzzle on FPGAs

It has been more than seven years since the first computation of the number of solutions of the 26-Queens Puzzle completed. It was a handful of field-programmable gate arrays (FPGAs) that were able to unfold the concurrency it takes to tackle this intriguing combinational problem whose simple formulation hides an enormous computational complexity. In fact, the computation of the solution count asks for an extensive backtracking search. Only very few mathematical shortcuts are known.

The rigor, with which the N-Queens Puzzle is eluding its capture by conceivable mathematical measures, is astonishing.

In the end, it is equivalent to differentiating the set of good shuffle from the poor ones. While a set of N elements is well-known to have N! different rearrangements, it is extremely hard to discount those that include trivial moves as shifting the position of groups of elements or simply switching places. It is exactly the solutions to the N-Queens Puzzle that represent each a shuffle, in which not a single pair of elements is allowed to maintain their relative distance.

At least three compute efforts were after the 26-Queens Puzzle in 2009. All of them were also exploiting massive concurrency. The Queens@Home project built on computer idle time donated by users from all over the world over the BOINC infrastructure that also backs the well-known SETI@home experiment. They gave up after Thomas Preusser of the competing Queens@TUD team discovered circumstantial evidence that they were underestimating the magnitude of the partial results and their compute client produced undetected numerical overflows. While the Queens@TUD team obtained their result with a distributed FPGA computation, the competing MC#-Project using two Russian supercomputers of the then-current TOP500 list could confirm their result not even two months later.

The record of exploring the 26-Queens Puzzle lasted for more than seven years, which is a good indicator of the enormous computational challenge behind the next step. It took the further mathematical analysis by Thomas Preusser and Matthias Engelhardt to break down the problem complexity by the exploitation of all of its inherent symmetries as well as an enormous increase of the computational power of FPGA devices to cope with what this effort left. It took more than a year of crunching exploiting every idle minute of FPGA resources at the Department of Computer Science at TU Dresden to complete this computation. And it yielded a single number: Q(27) = 234,907,967,154,122,528. So, it is already hard only to imagine how many ways there are to shuffle a deck of 27 cards really good. And yet, there is still a long way to go in mathematics and in computing before we know the number of good shuffles of the traditional German Skat deck of 32 cards.

Considering the exploding computational complexity and the slowing progress in computing new board sizes suggests that this record renewed by an FPGA computation might last a while. Even the confirmation of this very result by an independent group may require some patience. However, the puzzle has raised some interest in the GPGPU community as a performance benchmark. And GPUs offer, indeed, a platform that might reasonably be able to push forward to similar problem sizes and beyond.