Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Mathematische Unterhaltungen: Die Lösung des 27-Damen-Problems

Deutsche Informatiker haben einen Weltrekord aufgestellt. Wir wissen jetzt, wie viele Anordnungen von 27 Damen es auf einem Schachbrett der Größe 27·27 gibt, die sich gegenseitig nicht bedrohen.
Schachbrett-Muster

Die Geschichte fängt ganz harmlos an. Der fränkische Schachmeister Max Bezzel (1824 – 1871) warf vor reichlich 160 Jahren die Frage auf, ob man acht Damen so auf die Felder eines Schachbretts setzen könne, dass keine eine andere bedroht. Das "Acht-Damen-Problem" wurde berühmt, und viele Leute versuchten sich an seiner Lösung. Mit dem Schachspiel hat es eigentlich nichts zu tun; vielmehr ist es eine kombinatorische Aufgabe. Die Fachleute nennen es ein "constraint satisfaction problem" ("Bedingungserfüllungsproblem"): Es sind Werte für die Variablen – hier die Positionen der Damen – zu finden, die eine Reihe vorgegebener Bedingungen erfüllen. Man findet die Lösung des Acht-Damen-Problems im Wesentlichen durch Probieren, und die Kunst besteht darin, alle denkbaren Stellungen möglichst schnell durchzutesten.

Bei der Rechenleistung heutiger Computer muss man sich dabei keine besondere Mühe geben. Schon ein einfacher Suchalgorithmus findet nach kurzer Zeit die 92 Lösungen, die es gibt. Wenn man Anordnungen, die durch Drehungen oder Spiegelungen ineinander übergehen, als "eigentlich dieselbe" zählt, sind es nur zwölf. Da es acht solcher Transformationen gibt, die das (quadratische) Schachbrett auf sich selbst abbilden – die Identität, die nichts tut, mitgezählt –, kann man aus jeder der zwölf "Urlösungen" acht machen. Aber dann müssten es doch insgesamt 96 und nicht 92 Lösungen sein? Schon. Aber eine der zwölf ist ihrerseits punktsymmetrisch und erzeugt daher nur vier statt acht verschiedene Lösungen. ...

  • Quellen und Literaturtipps

Preußer, T.B., Engelhardt, M.R.:Putting Queens in Carry Chains, No. 27. In: Journal of Signal Processing Systems 2016

Delahaye, J.-P.:Le problème des 8 reines ... et au-delà. In: Pour la Science 459, S. 78 – 83, 2016

Schreiben Sie uns!

1 Beitrag anzeigen

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.