Ein Schachproblem lösen und eine Million gewinnen

von Frederic Friedel
05.09.2017 – Die Aufgabe stammt aus dem Jahre 1845: Acht Damen so auf dem Schachbrett aufstellen, dass keine Dame eine andere angreift. Die Lösung wurde fünf Jahre später veröffentlicht, aber für ein komplizierteres Problem hat man bislang keine Lösung gefunden: n Damen auf einem n x n großen Schachbrett (z.B. 100 Damen auf einem 100 x 100 Brett) so aufstellen, dass keine Dame die andere schlagen kann. Moderne Computer brauchen für die Lösung dieser Aufgabe Tausende von Jahren. Wer ein Programm schreibt, das deutlich schneller ist, dem winken eine Million Dollar!

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


Chefredakteur der englischen ChessBase-Seite. Hat in Hamburg und in Oxford Philosophie und Linguistik studiert und sein Studium mit einer Arbeit über Sprechakttheorie und Moralsprache abgeschlossen. Eine Karriere an der Universität gab er auf, um Wissenschaftsjournalist zu werden und Dokumentationen für das deutsche Fernsehen zu produzieren. Er ist einer der Mitbegründer von ChessBase.
Nachricht an die Redaktion Bitte nutzen Sie dieses Feld für Kontakt mit der Redaktion



Diskutieren

Regeln für Leserkommentare

 
 

Noch kein Benutzer? Registrieren

rgorn rgorn 05.09.2017 05:34
Wie man ganz ohne Computer und nur mit Papier und Bleistift eine Loesung des n-Damen-Problems fuer beliebiges n ruckzuck angibt, ist schon seit Jahrzehnten bekannt. Der Artikel hier ist somit ein Beispiel fuer Fake News.

Tatsaechlich geht es naemlich um das Problem "n-Queens Completion". Es stehen schon m < n Damen auf dem Brett und gefragt ist, ob man diese Ausgangssituation mit weiteren n-m Damen zu einer Loesung des n-Damen-Problems ergaenzen kann.

Das kann man alles schon seit letztem Samstag unter

https://www.claymath.org/events/news/8-queens-puzzle

nachlesen.
DoktorM DoktorM 06.09.2017 07:19
Kein ernsthafter Informatiker nimmt an, dass P = NP gilt. Daher geht es darum, das Gegenteil zu beweisen. Der Beweis wäre bemerkenswert, sollte es einen geben (das ist gar nicht so klar). Aber irgendwelche großartigen Folgen für die Praxis aus diesem Beweis ergeben sich nicht. Man sollte seine Zeit sinnvoller nutzen.
1