26-Damen-Problem gelöst

Eine Forschergruppe der TU Dresden hat durch massiv paralleles Rechnen auf FPGAs einen Rekord aufgestellt.

In Pocket speichern vorlesen Druckansicht 376 Kommentare lesen
Lesezeit: 2 Min.
Von
  • Dr. Harald Bögeholz

Die Aufgabe, acht Damen so auf einem Schachbrett zu platzieren, dass sich keine davon gegenseitig schlagen können, läuft früher oder später jedem Informatik-Erstsemester über den Weg. 92 Möglichkeiten gibt es, und ein aktueller PC benötigt ungefähr null Sekunden, um sie alle auszurechnen. Doch wie bei vielen kombinatorischen Problemen werden die Zahlen und damit die Zeiten, sie zu ermitteln, schnell gigantisch, wenn man die Aufgabe größer macht: Wie viele Möglichkeiten gibt es, n Damen bedrohungsfrei auf einem n×n-Schachbrett zu platzieren?

Bis vor kurzem waren die Lösungen bis n=25 bekannt; für n=25 dauerten die Berechnungen durch die Forschergruppe OASIS von Oktober 2004 bis Juni 2005 und verschlangen insgesamt 53 Jahre an CPU-Zeit. Das Projekt Queens@TUD der Technischen Universität Dresden hat sich daraufhin der Frage n=26 angenommen und am 11. Juli fertiggezählt: 22.317.699.616.364.044 Möglichkeiten gibt es.

Um diese Zahl zu ermitteln, gossen die Dresdner das Problem in Hardware, genauer in FPGAs. Ein Field Programmable Gate Array ist ein programmierbarer Logikbaustein: Seine Software ist sozusagen ein Schaltplan, und einmal programmiert, lässt sich solche eine Schaltung mit einer Taktfrequenz in der Größenordnung von 100 MHz betreiben. Das klingt im Vergleich mit aktuellen Allzweckprozessoren nicht nach viel, doch kann ein Spezialprozessor, dessen alleiniger Daseinszweck das Überprüfen von Damen-Stellungen ist, diese Aufgabe in erheblich weniger Taktzyklen erledigen.

Zunächst wurde das Problem in Teilprobleme aufgeteilt, bei denen die Damen in den ersten sechs Spalten fest platziert waren. Nach Symmetrie-Überlegungen blieben etwa 25 Millionen solcher Teilprobleme übrig, die dann von den FPGAs durchgekaut wurden. Nach neun Monaten massiv parallelen Rechnens auf zwischenzeitlich noch erweiterter Hardware stand das Ergebnis schließlich fest. Das konkurrierende NQueens@Home-Projekt, das dieselbe Aufgabe mit verteiltem Rechnen übers Internet zu lösen versucht, rechnet übrigens immer noch ... (bo)