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

Results

Approach

We split the overall work of the 26-Queens Puzzle into subproblems by pre-placing the queens within the first six leftmost columns. Accounting for the symmetry about the center horizontal, the initial column only needed to be placed half way. The resulting total was doubled to comprise the explored pre-placements and their symmetric images. This division yielded exactly 25,204,802 subboards that have been explored by our solver instances.

Results

Total Solution Count

22,317,699,616,364,044 overall solutions.
Also, see the fundamental and self-symmetric solution counts.

Subtotals

Subtotals of Subboards

You may download the subtotals of all of the explored 25,204,802 subboards.
Be aware of the file size: 169.6 MByte (compressed), 639.7 MByte (uncompressed).

An initial overview is given by the table on the subboards obtained from the pre-placement of the two leftmost columns.

Progress

Computational Progress

The figure to the right depicts the computational progress over time. It clearly shows the periodic computation speed as well as its acceleration by out iterative design improvements and the joining of our sponsor Signalion. It also reveals an outage of our main performer FPGAs in the middle of May.

The 13 clearly convex periods in the computational progress correlate with the placements of the queen in the leftmost column. These placements were essentially processed in sequential order. It appears that the complexity of the exploration of a subboard grows as the queens of the pre-placement are located closer to the board center. Most notably, the determined subtotals follow the same trend.

Performance and Energy

Device Performance

This figure illustrates the relative performance of a few devices we employed for our computation especially also in contrast to a few high-performance general-purpose CPUs.

You should also note that we ran eight of the Virtex-4 LX160 devices from a single 400 Watts PC power supply. The power consumption of this system was measured to be 110 W at the wall plug. The delivered system performance matches the one of 8*22 2.5 GHz-QuadCore systems, each of which draws 180 W from the wall plug. Thus, a QuadCore system spends 288 times at much energy at the solution of one subproblem when compared to the FPGA setup. Using processors with fewer cores would even increase this ration as the load of the system peripherie is shared among fewer parallel computations.

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