Das Damenproblem
Das Damenproblem verlangt acht Damen auf einem Schachbrett, von denen keine zwei einander angreifen. Der Schachkomponist Max Bezzel veröffentlichte es 1848, und es ist zum klassischen ersten Beispiel für die Backtracking-Suche geworden.
Ein Schachrätsel aus dem Jahr 1848
Max Bezzel, ein deutscher Schachkomponist, stellte das Rätsel 1848 in einer Berliner Schachzeitschrift. Franz Nauck veröffentlichte 1850 alle 92 Lösungen und stellte dieselbe Frage für größere Bretter. Carl Friedrich Gauß verfolgte das Rätsel mit Interesse und besprach es in seinen Briefen.
Eine Dame pro Reihe und Spalte
Acht Damen, die sich nicht gegenseitig angreifen, müssen in acht verschiedenen Reihen und acht verschiedenen Spalten stehen. Eine Lösung ist also eine Umordnung der Zahlen 1 bis 8, eine Permutation, mit einer zusätzlichen Regel: Keine zwei Damen dürfen auf derselben Diagonale stehen. Von den 40.320 Permutationen kommen nur 92 durch.
Backtracking
Backtracking baut eine Lösung Stück für Stück auf und geht zurück, sobald es in eine Sackgasse gerät. Für die Damen heißt das: Setzen Sie eine Dame auf das erste sichere Feld der nächsten Reihe, und wenn eine Reihe kein sicheres Feld hat, gehen Sie zur Reihe darüber zurück und schieben diese Dame weiter. 1972 nutzte Edsger Dijkstra das Rätsel, um mit genau dieser Suche die strukturierte Programmierung zu erklären.
Symmetrie
Drehen Sie das Brett eine Viertelumdrehung weiter oder spiegeln Sie es, und eine Lösung bleibt eine Lösung. Das ergibt bis zu acht Versionen jeder Lösung. Die 92 Lösungen zerfallen in 12 solcher Familien: elf mit 8 Mitgliedern und eine mit nur 4, weil diese Lösung nach einer halben Umdrehung gleich aussieht.
Das n-Damen-Problem
Auf einem n×n-Brett lautet die Frage genauso, mit n Damen. Für jedes n ab 4 gibt es Lösungen, und ihre Zahl wächst schnell: 2 bei 4×4, 92 bei 8×8 und 14.200 bei 12×12. Eine Formel für die Anzahl ist nicht bekannt; die Rekordwerte stammen aus großen Computersuchen.
In PictorX ausprobieren
Öffnen Sie Acht Damen und klicken Sie auf ein Feld, um eine Dame zu setzen; klicken Sie erneut darauf, um sie wieder zu entfernen. „Angriffe anzeigen“ setzt einen Punkt auf die Felder, die Ihre Damen angreifen, und rote Damen greifen sich gegenseitig an. Lösen führt die Backtracking-Suche Schritt für Schritt aus und lässt die Damen stehen, die Sie gesetzt haben. Nächste Lösung geht alle Lösungen der Reihe nach durch, und Größe ändert das Brett von 4×4 bis 12×12.
Häufig gestellte Fragen
Wer hat das Damenproblem erfunden?
Max Bezzel, ein deutscher Schachkomponist, im Jahr 1848. Franz Nauck veröffentlichte 1850 die erste vollständige Sammlung der Lösungen.
Wie viele Lösungen gibt es?
92 auf dem normalen Brett. Zählt man Drehungen und Spiegelungen als eine, sind es 12.
Warum hat das 6×6-Brett so wenige Lösungen?
Es hat nur 4, alle aus einer einzigen Familie. Das kleinere 5×5-Brett hat 10. Größere Bretter haben immer mehr: 40 bei 7×7 und 92 bei 8×8.
Lädt PictorX etwas hoch?
Nein. Das Brett wird auf einer Leinwand in Ihrem Browser gezeichnet. Speichern lädt ein PNG herunter, und Bearbeiten öffnet das Bild im PictorX-Editor.
Verwandte Tools
Acht Damen
Setzen Sie acht Damen so auf ein Schachbrett, dass keine eine andere angreift. Probieren Sie es selbst, sehen Sie zu, wie die Backtracking-Suche Schritt für Schritt eine Lösung findet, und gehen Sie alle 92 Lösungen durch.
Springerproblem
Springen Sie mit dem Springer genau einmal auf jedes Feld des Bretts. Spielen Sie selbst mit Warnsdorff-Hinweisen, oder sehen Sie zu, wie Lösen eine offene oder geschlossene Tour vollendet. Speichern Sie den Weg als PNG.
Das Springerproblem
Geschichte und Mathematik des Springerproblems: Euler und Warnsdorff, offene und geschlossene Touren, warum Bretter mit ungerader Seitenlänge keine geschlossene Tour haben und wie ein Computer eine findet.
Türme von Hanoi
Versetzen Sie im Browser einen Turm aus Scheiben über drei Stäbe. Immer nur eine Scheibe, nie eine größere auf eine kleinere. Die kürzeste Lösung hat 2ⁿ − 1 Züge.
Türme von Hanoi
Die Türme von Hanoi: drei Stäbe, immer nur eine Scheibe und nie eine größere auf einer kleineren. Die kürzeste Lösung hat 2ⁿ−1 Züge. Édouard Lucas stellte das Rätsel 1883 vor.
Langtons Ameise
Starten Sie Langtons Ameise im Browser. Sehen Sie Symmetrie, Chaos und die 104-Schritte-Autobahn, und probieren Sie dann mehrfarbige Regeln, mehrere Ameisen, ein Sechseckgitter und Turmiten.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Acht Damen ausprobieren