Wissen
Samstag, 01. August 2009

22.317.699.616.364.044 Lösungen: Das 26-Dame-Problem

Wie viele Möglichkeiten gibt es, 26 Dame-Figuren auf einem Schachbrett der Fläche 26 mal 26 Felder zu verteilen – ohne dass sich die Damen gegenseitig bedrohen? Die Frage klingt verrückt, hat in der Informatik aber große Bedeutung, weil sich daran viele andere Probleme demonstrieren lassen.

Mit 26 sich nicht bedrohenden Damen hat die TU Dresden einen neuen Weltrekord aufgestellt.
Mit 26 sich nicht bedrohenden Damen hat die TU Dresden einen neuen Weltrekord aufgestellt.(Foto: Pixelio: Jürgen Reitböck)

Das Institut für Technische Informatik der Technischen Universität Dresden hat sich eigens hoch spezialisierte Schaltkreise geschaffen, um das sogenannte 26-Dame-Problem zu lösen. Diese Chips hatten fast zehn Monate zu tun, aber nun steht das Resultat fest. Es wurden genau 22.317.699.616.364.044 Möglichkeiten ermittelt, 26 sich nicht bedrohende Damen auf einem 26x26-Feld zu platzieren. Damit wurde der alte Weltrekord – die Lösung des 25-Dame-Problems im Juli 2005 – nach 49 Monaten geknackt, berichtet die TU Dresden.

Extra Schaltungen für die Damen

Ursprünglich war es einmal darum gegangen, acht Damen so auf einem Schachbrett aufzustellen, dass keine davon eine andere nach den Regeln des Spiels schlagen kann. Es dürfen also keine zwei Damen die gleiche Reihe, Linie oder Diagonale teilen. Diese Aufgabe lässt sich auf eine beliebig große Zahl von Damen auf einem beliebig großen Schachbrett erweitern. Statt zur Lösung ein Computerprogramm zu schreiben und dies auf Standard-PCs abarbeiten zu lassen, wählten die Dresdner programmierbare logische Schaltungen (FPGAs). Diese sind nur zu einem einzigen Zweck geschaffen, können also nur am Dame-Problem arbeiten – dies aber sehr schnell.

Quelle: n-tv.de

Empfehlungen