Die Erweiterung des Acht-Damen-Rätsels
Wahrscheinlich kennen Sie dieses Problem: Man soll acht Damen auf einem gewöhnlichen 8×8 Schachbrett so anordnen, dass keine der acht Damen eine der anderen Damen schlagen kann, d.h. keine zwei Damen dürfen auf der selben Linie, Reihe oder Diagonale stehen.
Dieses Problem stammt aus dem Jahre 1848, gestellt hat es Max Bezzel. Die ersten Lösungen lieferte Franz Nauck 1850, der das Rätsel auch auf n Damen auf einem n x n großen Schachbrett erweitert hat. Seitdem haben sich viele Mathematiker, darunter auch Carl Friedrich Gauss, an dem Acht-Damen-Rätsel und seiner Verallgemeinerung, der n-Damen Version, versucht.
Ein unendliches Schachbrett — Bild aus dem Video Infinite Chess | Quelle: PBS Infinite Series YouTube channel
Auf diesem großen JavaScript-Brett, das Ronald Daenzer entwickelt hat, und das unter The JavaScript Source zur Verfügung steht, können Sie versuchen, das 8x8 Problem zu lösen (wenn das Brett links nicht erscheint, probieren Sie es hier).
Aber passen Sie auf: das birgt ein wenig Suchtgefahr und man kann eine Menge Zeit darauf verwenden, unterschiedliche Lösungsansätze zu verfolgen. Wie in einem Artikel über den unvergessenen Martin Gardner erwähnt, hat das Acht-Damen-Problem 92 unterschiedliche Lösungen — zwölf, wenn man die nicht mitrechnet, die sich nur in Bezug auf Symmetrie (Spiegelungen und Rotationen) unterscheiden.
Die zwölf Lösungen findet man am Ende des Artikels.
Gardner erweiterte das Problem: man sollte drei weiße und fünf schwarze Damen auf einem 5x5 großen Schachbrett so aufstellen, dass keine Dame einer Farbe eine Dame der andere Farbe angreift. Wenn man Spiegelungen und Rotationen nicht berücksichtigt, gibt es hierfür nur eine Lösung. Vielleicht möchten Sie sich an der Lösung dieses Rätsels versuchen - obwohl das nicht das Thema des vorliegenden Artikels ist.
Die Eine-Million-Dollar Frage
Das Acht-Damen-Problem ist ein Beispiel des allgemeineren "n-Damen Problems", das verlangt, dass man n Damen auf einem n x n großen Schachbrett platziert. Dabei gibt es Lösungen für alle natürlichen Zahlen n (mit Ausnahme von n=2 und n=3).
Professor Ian Gent und Dr Peter Nightingale | Foto: Phys.org © Stuart Nicol
Die Computerwissenschaftler Professor Ian Gent und Dr Peter Nightingale von der St. Andrews University in Schottland fordern Programmierer jetzt dazu auf, dieses Problem zu lösen, wenn die Werte für n sehr groß sind. Mit schierer Rechenkraft brauchen moderne Computerprogramme bei dem 8x8 Problem nur Bruchteile von Sekunden, aber die Wissenschaftler haben festgestellt, dass die Computerprogramme die Aufgabe bei sehr großen Zahlen nicht mehr in einer angemessenen Zeit lösen konnten, z.B. wenn das Schachbrett 100 x 100 Felder oder 1.000 x 1.000 Felder groß war. Tatsächlich würden moderne Programme dann theoretisch 1.000 Jahre zur Lösung des Problems brauchen.
Deshalb versprechen Gent und Nightingale demjenigen, der es schafft, eine schnellere Lösung zu entwickeln, einen Preis von $1.000.000. Die Lösung dieses Rätsels ist von einiger Bedeutung, denn, so Gent, "Wenn man ein Computerprogramm schreiben kann, dass dieses Problem wirklich schnell lösen kann, dann könnte man dies für viele der wichtigsten Probleme, mit denen wir täglich zu tun haben, entsprechend anpassen. Das umfasst triviale Herausforderungen wie festzustellen, wie hoch die größte Zahl von Facebook-Freunden ist, die sich untereinander nicht kennen, oder wichtigere, wie die Codes zu knacken, die alle unsere Online-Transaktionen sicher machen."
Lösungen
Hier sind die oben erwähnten zwölf Lösungen, bei denen Rotationen und Spiegelungen nicht berücksichtigt werden:
Ergänzung, 5. September
Aufmerksame Leser haben darauf hingewiesen, dass die Aufgabenstellung des Problems im Artikel ungenau beschrieben ist. Hier deshalb ein Auszug einer Erklärung des Clay Institutes:
Die neue Forschung betrifft das n-Damen-Ergänzungs-Problem, bei dem nicht nur das Brett größer ist, sondern auch bereits ein paar Damen auf das Brett gestellt wurden. Gibt es also eine Lösung für das n-Damen-Problem, bei der keine dieser Damen gezogen wird? Der technische Beitrag, der in diesem Paper behauptet wird, besteht darin, dass das n-Damen-Ergänzungs-Problem zur Klasse gehört, die man als NP-Complete bezeichnet. Das heißt, dass jeder Algorhithmus, der das n-Damen-Ergänzungs-Problem lösen kann, indirekt genutzt werden kann, um jedes andere Problem in der NP-Klasse zu lösen. Das gilt nicht für das ursprüngliche n-Damen Problem, denn die Ergänzung durch die vorher aufgestellten Damen ist entscheidend.
"Leider haben einige Berichte über unsere Arbeit den Eindruck vermittelt, dass die Lösung der 8-Damen-Problems oder des n-Damen-Problems für alle n zum Gewinn des Millenium-Preises führen können. Das ist aus zwei Gründen nicht der Fall. Erstens behandelt das Paper, wie eben erwähnt, das n-Damen-Ergänzungs-Problem, nicht das ursprüngliche n-Damen-Problem. Zweitens wäre die Entdeckung einer algorithmischen Lösung des n-Ergänzungs-Problems für alle n nicht ausreichend. Was notwendig wäre, wäre entweder ein Beweis, dass es einen Algorithmus gibt, der das n-Damen-Ergänzungs-Problem in polynomialer Zeit löst oder ein Beweis, dass kein solcher Algorithmus existiert."
Links
