idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
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.: 0351 463- 38456,
thomas.preusser@tu-dresden.de
27 Damen
Kerstin Knochenhauer
None
Criteria of this press release:
Journalists, Scientists and scholars
Information technology
transregional, national
Research results
German
27 Damen
Kerstin Knochenhauer
None
You can combine search terms with and, or and/or not, e.g. Philo not logy.
You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).
Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.
You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).
If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).
