Neuer Weltrekord für Queens@TUD-Team

Für die Aufgabe, acht Damen so auf einem Schachbrett zu platzieren, dass sich keine davon gegenseitig schlagen können, gibt es 92 Möglichkeiten, die ein PC in weniger als einer Sekunde ausrechnet. Aber wie viele Möglichkeiten gibt es, n Damen bedrohungsfrei auf einem n×n-Schachbrett zu platzieren und wie wächst dabei die Berechnungszeit?

Mehr als sieben Jahre sind vergangen, seitdem die erste Berechnung der Anzahl der Lösungen des 26-Damenproblems abgeschlossen wurde. Die Lösung erfolgt mittels Hardwareimplementierung am Institut für Technische Informatik der TU Dresden.

Jetzt haben Dresdner Informatiker um Dr. Thomas Preußer erneut als weltweit erstes Team das 27-Damenproblem gelöst! Ihre entwickelten Löser nutzten FPGAs (Field Programmable Gate Array), welche ein massiv paralleles Rechnen ermöglichen. Durch die Vorplatzierung einiger Damen wird der Lösungsansatz so zerlegt, dass die resultierenden Teilprobleme unabhängig und parallel zueinander bearbeitet werden können. Das 27-Damenproblem wurde in 2.024.110.796 Teilaufgaben zerlegt, von denen kontinuierlich um die 7000 gleichzeitig bearbeitet wurden. Für eine Aussicht auf Erfolg bedurfte es der weiteren mathematischen Optimierung des algorithmischen Ansatzes und einer enormen Steigerung der Leistungsfähigkeit von FPGAs. Schließlich mussten diverse FPGA-Boards an der Fakultät Informatik der TU Dresden immer noch über ein Jahr mit all ihrer Leerlaufzeit am 27-Damenproblem rechnen, bevor es geknackt war. Das Ergebnis ist eine einzige riesige Zahl, Q(27) = 234.907.967.154.122.528, die auch angibt, wie viele verschiedene Anordnungen von 27 Karten man als gut durchmischt ansehen kann. Es wird noch einige Zeit ins Land gehen, bevor diese Zahl auch für ein einfaches Skatblatt von 32 Karten bekannt sein wird.

In Anbetracht des explodierenden Rechenaufwandes und des dadurch begründeten langsamer werdenden Fortschritts bei der Analyse neuer Brettgrößen wird dieser Rekord wahrscheinlich über einige Jahre bestehen bleiben. Auch die Bestätigung dieses neuen Ergebnisses durch eine unabhängige Berechnung könnte auf sich warten lassen. Als hochparalleles Computer-Benchmark ist das n-Damenproblem inzwischen auch für Forscherteams interessant, die Grafikkarten als allgemeine Rechenbeschleuniger einsetzen (GPGPU). Die massiv parallele Architektur von GPUs könnte jedenfalls die Bewältigung ähnlicher oder gar größerer Problemgrößen ermöglichen.