idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
idw - Informationsdienst
Wissenschaft
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
Merkmale dieser Pressemitteilung:
Journalisten, Wissenschaftler
Informationstechnik
überregional
Forschungsergebnisse
Deutsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
