Volltextsuche über das Angebot:

11 ° / 7 ° wolkig

Navigation:
Google+
Dresdner Informatiker der TU stellt Weltrekord für ein Schachproblem auf

27 Damen auf einem Brett von 27 mal 27 Feldern Dresdner Informatiker der TU stellt Weltrekord für ein Schachproblem auf

Es ist eine eher theoretische Frage: Wie kann man 27 Schachdamen auf einem Schachbrett von 27 mal 27 Feldern so aufstellen, dass keine eine andere schlagen kann? An der TU Dresden fand man die Antwort.


Quelle: Monage: Eylert

Dresden. Für die Aufgabe, acht Damen aus einem Schachspiel so auf einem normalen Schachbrett zu platzieren, dass sie sich nicht gegenseitig schlagen können, gibt es 92 Möglichkeiten. Die rechnet ein PC in weniger als einer Sekunde aus. Aber was ist, wenn die Zahl der Damen ebenso ansteigt wie die Größe des Schachbretts? Neun Schachdamen auf einem 9x9-Felder-Brett, zehn Schachdamen auf einem 10x10er-Brett und so fort.

Zugegeben: eine eher theoretische Frage. Aber die Rechenkomplexität steigt immens an, ebenso die Berechnungszeit. Der Informatiker Dr. Thomas B. Preußer von der Technischen Universität Dresden hat mit seinem Studenten Benedikt Reuter und dem Nürnberger Mathematiker Matthias Engelhardt jetzt einen neuen Weltrekord aufgestellt. Sie berechneten, wie viele Möglichkeiten es gibt, auf einem Schachbrett von 27x27 Feldern 27 Damen so aufzustellen, dass keine eine andere schlagen kann: Ergebnis: 234 907 967 154 122 528. In Worten knapp 235 Billiarden verschiedene Stellungen.

Seit September 2015 nutzten die drei Forscher am Institut für Technische Informatik freie Kapazitäten auf so genannten FPGAs, Halbleiterchips, auf denen sie selbstbestimmte Schaltungen konfigurierten, die an der Lösung des 27-Damen-Problems arbeiteten. Auf einem Chip ließen sich mehrere 100 Löser unterbringen, die alle parallel nach den Damenstellungen suchten. Zeitweise waren über 30 FPGAs gleichzeitig an der Arbeit, wenn sie nicht gerade von anderen Studenten gebraucht wurden. Das 27-Damen-Problem wurde in 2 024 110 796 Teilaufgaben zerlegt, von denen stets um die 7000 gleichzeitig bearbeitet wurden. Es gibt bei dieser Fragestellung bislang keine Formel, mit der sie berechnet werden kann; vielmehr ist es eine riesige Suche nach Lösungen, die natürlich immer umfangreicher wird, je größer die Zahl der Felder und der Damen ist.

Hat das Suchen nach den Damenstellungen einen praktischen Nutzen? Es sei ein Luxusproblem, räumt Preußer schmunzelnd ein. Die Aufgabenstellung könne allerdings durchaus schon genutzt werden, um etwa die Leistungsfähigkeit von Rechenplattformen zu messen, das sei zum Beispiel für Grafikkarten interessant. Und überhaupt: „Bei der Mathematik weiß man nie, wozu es einmal gut ist.“

Auf jeden Fall hat das Problem der Schachdamen auch eine Parallele zum allseits beliebten Kartenspiel. Das Ergebnis gibt nämlich auch an, wie viele verschiedene Anordnungen für eine „gute Durchmischung“ es gibt – bei der zwei Karten nicht einfach nur vertauscht oder in der direkten Reihenfolge verändert sind. Aber mit den 27 Damen ist das Problem auch nur für ein Blatt mit 27 Karten gelöst. Bis zum klassischen 32er-Skatblatt ist es noch ein weiter Weg...

Übrigens: Auch die Lösung der vorherigen Stufe – 26 Damen auf einem 26x26er Schachbrett – fand das Queens-Team der TU (Queen: englisch für die Dame beim Schach) zuerst. Das ist sieben Jahre her und war ein knappes Rennen. „Anderthalb Monate später hatten die Russen das Ergebnis mit ihren Superrechnern auch“, erinnert sich Preußer.

Von Bernd Hempelmann

Voriger Artikel
Nächster Artikel
Mehr aus Bildung
  • 13. Februar

    Ob Gedenken, Täterspuren oder Menschenkette: Alle Infos finden sie in unserem Special zum 13. Februar in Dresden mehr

  • Semperopernball
    Semperopernball

    Alle Infos, alle Highlights, die schönsten Bilder - der Semperopernball in Dresden. mehr

Städtewetter
Heute -° / -° -
- -°/-° -
- -°/-° -
Wettersponsor

Das Wetter in und um Dresden präsentiert Ihnen die Toskana-Therme Bad Schandau.