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
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.
