Das 8-Damen-Problem ist ein mathematisches Rätsel auf Basis eines Schachbretts. Die Aufgabe ist es, 8 Damen auf dem Schachbrett so zu platzieren, dass sich keine zwei Damen gegenseitig schlagen können. Als Erinnerung: eine Dame kann sich von ihrem aktuellen Feld ausgehend senkrecht, waagrecht und auch diagonal beliebig weit bewegen! Anders ausgedrückt besteht die Aufgabe also darin, die Damen so zu platzieren, dass sich keine zwei Damen in einer Reihe, einer Spalte oder einer Diagonalen befinden.
Für dieses Rätsel gibt es tatsächlich ganze 92 Lösungen (schließt man symmetrisch identische Lösungen durch Drehung und Spiegelung aus, so verbleiben 12 Lösungen).
Wie würde man das Problem algorithmisch lösen? Am besten probierst du es ohne PC an einem normalen Schachbrett aus - wenn du keines zur Hand hast, kannst du diese Aktivität im Browser verwenden, um die 8 Damen auf einem virtuellen Schachbrett zu platzieren. Um mit weniger Feldern zu beginnen, kannst du auch die folgende Vorlageverwenden.
Lies hier erst weiter, nachdem du dir selbst Gedanken gemacht hast, wie du vorgehen könntest.
Wichtig ist die Erkenntnis aus der Einleitung: In keiner Reihe, Spalte oder Diagonalen dürfen sich zwei Damen befinden. Es ist daher sinnvoll mit der ersten Reihe zu beginnen und dort eine Dame zu platzieren. Um systematisch vorzugehen, werden wir in jeder Reihe die Damen zuerst ganz links platzieren und diese dann stückchenweise nach rechts verschieben. Als Tipp zur Vorstellung: In der Informatik beginnt das Koordinatensystem immer links oben. Die erste Reihe ist also die oberste! Bezogen auf das dargestellte Schachbrett steht die Dame in A8
.
Wenn die erste Reihe mit einer Dame gefüllt ist, ist klar, dass es danach mit der zweiten Reihe weitergehen muss. Auch dort versucht man zunächst, die Dame ganz links zu platzieren (A7
). Dort kommt es natürlich direkt zu einer Kollision mit A8
. Daher verschiebt man die Dame der zweiten Reihe eins nach rechts und probiert B7
. Auch dort gibt es wegen der Diagonalen eine Kollision. Also noch eins weiter verschieben auf C7
- nun ist die Dame "sicher".
Die dritte Dame wird in der dritten Reihe auf A6
platziert und du kannst dir sicher schon denken, wie es weitergeht!
Was hat das ganze nun mit Rekursion zu tun? Die Rekursion ist im Befüllen der einzelnen Reihen zu finden. Tatsächlich ist der Algorithmus so stark reduziert, dass es praktisch nur eine Methode gibt, deren Aufgabe es ist, eine einzelne Reihe korrekt/fehlerfrei zu befüllen. Welche Reihe das ist, wird als Parameter übergeben. Damit kann die Methode rekursiv wieder aufgerufen werden um die erste, dann die zweite, dann die dritte Reihe […] zu füllen.
// die Methode befuelleZeile(zeile) hat nur die Aufgabe, // die übergebene Zeile fehlerfrei zu befüllen befuelleZeile(zeile): wenn zeile < 8: für spalte von 0 bis 7: wenn istPositionErlaubt(zeile, spalte): setze Dame ins Feld [zeile][spalte] befuelleZeile(zeile+1) // Nächste Zeile befüllen loesche Dame im Feld [zeile][spalte] // Warum? sonst: druckeFeld() // Lösung gefunden - gib das komplette Feld aus!
Man startet diese Methode mit dem Aufruf von reihe(0)
.
Arbeite mit der folgenden Vorlage: https://codeberg.org/qg-info-unterricht/bluej-8-Damen-console
(A) Modelliere das Feld mit einem zweidimensionalen Array des Typs boolean
. Definiere das Feld als Attribut der Klasse, initialisiere es im Konstruktor.
(B) Implementiere eine Methode druckeFeld()
, die den gesamten Zustand des Schachbretts ausdruckt. Du kannst bei der Ausgabe z.B. einen Unterstrich für ein leeres Feld des Bretts, X für ein Feld mit einer Dame verwenden1). Teste deine Methode, indem du im Konstruktor das leere Feld ausgeben lässt, eine oder mehrere Damen setzt und dann das Feld mit den Damen ausgeben lässt.
(C) Implementiere eine Testmethode, die zurück gibt, ob an der aktuellen Position eine Dame gesetzt werden darf.
Um zu testen, ob eine Dame an eine bestimmte Position gesetzt werden darf, implementiert man die Methode
boolean istPositionErlaubt(int zeile, int spalte)
Diese gibt true
zurück, wenn die Dame platziert werden darf, andernfalls false
.
Einige Überlegungen zu dieser Methode:
Die Skizze stellt die Situation dar. Jetzt kann man sich überlegen, wie man an die Koordinaten der "gestrichelten" Felder kommt, die man überprüfen muss:
O(0…zeile-1|spalte)
zeileAktuell
zeilenweise von oben nach unten über das Feld iteriert, haben die Felder der "linken" Diagonalen die Koordinaten L(zeileAktuell|spalte-(zeile-zeileAktuell)
. Die Felder der rechten Diagonalen haben die Koordinaten R(zeileAktuell|spalte+(zeile-ZeileAktuell))
. In beiden Fällen muss man jedoch darauf achten, dass die berechnete Spalte sich innerhalb des erlaubten Bereichs für die Spaltenindex befindet: 0 bis N-1. Im Beispiel gibt es in Zeile 0 nämlich weder links noch rechts ein Feld auf der Diagonalen, da sowohl 2-(3-0)=-1
als auch 2+(3-0)=5
sich außerhalb des Feldes befinden. In Zeile 1 erhalten wir aber die Koordinaten der beiden Diagonalenfelder: L(1|2-(3-1)=L(1|0)
und R(1|2+(3-1))=R(1|4)
.
(D) Teste deine Methode istPositionErlaubt
:
(0|2)
(1|0)
, (1|1)
, (1|2)
, (1|3)
und (1|6)
gibt.Hilfestellung 1 zu "istPositionErlaubt":
Lösungsvorschlag zu "istPositionErlaubt":
(E) Wenn du geprüft hast, dass deine istPositionErlaubt
-Methode korrekt funktioniert, kannst du den Pseudocode für befuelleZeile
in deinem BlueJ-Projekt implementieren. Tipp: Nicht zuviel nachdenken, versuche den Pseudocode in Java zu "übersetzen".
Teste die Methode mit Schachbrettern 4x4 und 8x8. Überprüfe die ausgegebenen Lösungen stichprobenartig.
Was ist der Basisfall dieser Rekursion? Finde einen Weg, dir mit dem Debugger den Stack anzeigen zu lassen, wenn der Basisfall eintritt. Was fällt dir dabei auf?
Erweitere das Programm: Lass dir ausgeben, wie viele Lösungen gefunden wurden.
Auf der folgenden Seite siehst du visualisiert dieselbe Vorgehensweise bei der Lösungssuche: https://www.mathematik.ch/spiele/N_Damenproblem/
Filename | Filesize | Last modified |
---|---|---|
5damen-kollision.excalidraw.png | 95.5 KiB | 25.02.2025 07:52 |
8-damen-problem.zip | 3.9 KiB | 02.07.2024 12:30 |
n-damen-unplugged.odt | 95.0 KiB | 25.02.2025 14:42 |
n-damen-unplugged.pdf | 54.2 KiB | 25.02.2025 14:42 |