Skip to content.

TUD TU Dresden

Queens@TUD

DE EN 

TU Dresden » Faculty of Computer Science » Institute for Computer Engineering » Chair for VLSI – EDA » Queens
Queens@TUD-Logo

Queens@TUD

The World Record by FPGAs!

Q(26)=22,317,699,616,364,044

Queens@TUD is a massively-parallel, FPGA-based effort to find and count all the solutions to the N-Queens Puzzle.
When the project started in 2008, those counts were known known for all N up to 25. This project was the first to complete the solution count for N=26 on July 11, 2009, which turned out to be Q(26)=22317699616364044. (more)

We are currently evaluating the approach of Q(27). A timely completion of this problem definitely requires both: further methodological and algorithmic improvements as well as additional FPGA sponsoring. We would appriciate any useful input and cooperation partners.

Sponsors

Signalion

News

August 30, 2009
The Russian MC# Project completed its computation of the 26-Queens Puzzle on two super computers of the Top500 list (Juni 2009) confirming our result.
July 11, 2009
The last subboard solution was logged to the solutions database at 4:28 pm CEST. It finished the calculation of the N-Queens Puzzle for N=26, which started on October 14, 2008 at 10:10 am. The overall solution count was determined to be Q(26)=22317699616364044.
March 12, 2009
Our first sponsor Signalion has provided us with high-performance FPGA boards. We are currently working on their integration into our solver infrastructure.
November 27, 2008
We switched the design used by our solver slices. While the new design requires quite a few more clock cycles to finish a subboard, it is so much more compact so that the number of slice instances fitting onto an FPGA device could be quadrupled. Thus, a gain of computational power is achieved through a higher degree of concurrency. Further positive side effects are the better device utilization due to the finer granularity of the slices and the increased clock frequencies enabled by shorter critical paths in the design.
November 7, 2008
This project discovered discrepancies with the results of the competing NQueens@Home project. Identifying an overflow error in their world-wide distributed solvers, we also put an end to an open dispute over the number of solutions for N=24 — without performing any own computation on this problem! It had gone unnoticed by then that the mismatch in counts amounted exactly to 227514171973736 - 226732487925864 = 781684047872 = 0xb600000000 = 182·232, i.e. 182 overflows of the 32-bit counters used to add up the subtotals. Their work done so far for N=26 – well above 12 percent of the estimated overall work – is, at least, put in question.
Sponsors
Signalion
Contact

Prof. Rainer G. Spallek
rainer.spallek@tu-dresden.de

Thomas B. Preußer
thomas.preusser@tu-dresden.de

Bernd Nägel
bernd.naegel@mailbox.tu-dresden.de

Telefax
+49 (0)351 463 38324
Street Address
Nöthnitzer Straße 46, Room 1095
01187 Dresden
Mail Address
Chair for VLSI – EDA
Fakultät Informatik
Technische Universität Dresden
D-01062 Dresden