Nach fast zehnmonatiger Laufzeit hat das vom Institut für Technische Informatik erdachte Queens@TUD, am 11. Juli 2009 seine Berechnung zum 26-Damenproblem beendet. Es wurden genau 22.317.699.616.364.044 Möglichkeiten ermittelt, 26 sich nicht bedrohende Damen auf einem 26x26-Schachbrett zu platzieren.

Der mit der Berechnung des 25-Damenproblems im Juli 2005 aufgestellte alte Weltrekord wurde damit nach 49 Monaten geknackt.

Das Damenproblem ist eine schachmathematische Aufgabe, bei der ursprünglich jeweils acht Damen auf einem Schachbrett so aufgestellt werden, dass keine davon eine andere nach den Schachregeln schlagen kann. Es dürfen also keine zwei Damen die gleiche Reihe, Linie oder Diagonale teilen. Im Mittelpunkt steht dabei die Frage nach der Anzahl der möglichen Lösungen. Diese Aufgabe kann für eine beliebige Anzahl von n Damen auf einem nxn-Schachbrett verallgemeinert werden.

Mit der Idee das 26-Damenproblem mittels Hardwareimplementierung zu lösen, trat Bernd Nägel vom Institut für Künstliche Intelligenz an das Institut für Technische Informatik und den Lehrstuhl von Professor Rainer Spallek heran.

Der Diplominformatiker Thomas Preußer entwickelte daraufhin einen Entwurf zur Lösungsberechnung durch einen hoch parallelisierten, FPGA-basierten Ansatz zur Suche und Zählung aller Lösungen zu einem gegebenen n-Damenproblem.

Die dafür benötigte Technik entstammte den Laboren der Professur und wurde durch die Leihgabe eines äußerst leistungsfähigen FPGA-Systems von der Dresdner Signalion GmbH als Sponsor dieses Projektes aufgestockt.

Begonnen haben die Wissenschaftler damit, systematisch alle gültigen Stellungen der 26 Damen auf dem 26x26-Schachbrett zu konstruieren und zu zählen. Der dazu durchkämmte Suchraum wäre allerdings mit einem einfachen Ansatz nicht zu bewältigen gewesen und auch nach einigen Optimierungen in der Suche hätte ein einzelner Prozessor dazu mehrere hundert Jahre benötigt.

Durch die Vorplatzierung einiger Damen ließ er sich allerdings so zerlegen, dass jedes der resultierenden Teilprobleme unabhängig und zeitgleich, also parallel, zu den anderen bearbeitet werden konnte. Um diese hohe Parallelität zu bewerkstelligen, haben die Informatiker so viele Löser wie möglich auf speziell programmierbare integrierte Schaltkreise, die sogenannten FPGAs, konfiguriert. Auf den größten davon konnten 142 parallele Löser implementiert werden. Damit haben die Wissenschaftler das 26-Damenproblem in 25.204.802 handlichere Teilaufgaben zerlegt, von denen sie kontinuierlich über 1.500 gleichzeitig bearbeiteten.

Gerade den Weltrekord geknackt, beschäftigen sich die Forscher von Queens@TUD schon mit dem 27-Damenproblem.

Weitere Informationen:
Thomas Preußer
Tel.: 0351 463-38456

http://queens.inf.tu-dresden.de