Informatiker lösen das 27-Damenproblem nach über einem Jahr Rechenzeit

Für die Aufgabe, acht Damen (Schachfiguren) so auf einem Schachbrett zu platzieren, dass sich nicht gegenseitig schlagen können, gibt es 92 Möglichkeiten. Die rechnet ein PC in weniger als einer Sekunde aus. Aber wie viele Möglichkeiten gibt es, n Damen bedrohungsfrei auf einem n mal 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 damals mittels Hardwareimplementierung am Institut für Technische Informatik der TU Dresden. Jetzt haben Dresdner Informatiker um Dr. Thomas Preußer – das Queens@TUD-Team – erneut als weltweit erstes Team das 27-Damenproblem gelöst! Die von ihnen entwickelten Löser nutzten Field Programmable Gate Arrays (FPGA), die 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 2024110796 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 allerdings 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 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.

Informationen für Journalisten:
Dr. Thomas B. Preußer
Tel.: +49 (0) 351 463- 38456