8-Damen-Problem

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 probiert man es einmal ohne PC an einem normalen Schachbrett aus!

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 reihe(r) hat nur die Aufgabe, die übergebene Reihe r fehlerfrei zu befüllen
reihe(r):
    wenn r < 8:
        für jede Spalte s (0-7):
            wenn die Spalte frei ist:   // lagere die Überprüfung in separate Methode aus!
                setze Dame ins Feld [r][s] 
 
                wenn kollisionsfrei auf Diagonalen:    // lagere die Überprüfung in die bereits VORGEGEBENE Methode aus!
                    reihe(r+1)     // Die aktuelle Dame ist korrekt platziert -> fülle die nächste Reihe
 
                // wenn ich wieder aus der Rekursion zurückkomme ODER wenn es eine diagonale Kollision gab:
                entferne Dame aus Feld [r][s]
    sonst:
        druckeFeld()   // Lösung gefunden - gib das komplette Schachfeld aus!

Man startet diese Methode mit dem Aufruf von reihe(0).

1. Lade die Vorlage herunter und mache dich mit dem bereits vorgegebenen Code vertraut.
2. Überlege dir, welcher Datentyp für das Spielfeld sinnvoll ist. Setze den Typ in der Instanzvariablen und initialisiere das Spielfeld / die Variable im Konstruktor.
3. Implementiere den Pseudocode im vorgegebenen Methodengerüst. Für die Kollisionsprüfung auf der Diagonalen kannst du die bereits vergegebene Methode kollisionsfrei() nutzen. Implementiere dabei auch die folgenden zusätzlich nötigen Methoden:
   1. druckeFeld(): Druckt den gesamten Zustand des Feldes, wenn eine Lösung gefunden wurde. Tipp: Unterstrich für ein leeres Feld, X für eine Dame.
   2. spalteFrei(int spalte): Prüfe für die übergebene Spalte, ob diese komplett frei ist.

Was ist der Basisfall dieser Rekursion?

Erweitere das Programm: Lass dir ausgeben, wie viele Lösungen gefunden wurden.

Wenn du früh fertig bist, dann kannst du überlegen, ob du selbst eine andere/eigene Lösung für die Kollisionsprüfung auf der Diagonalen findest (das ist ziemlich knifflig, wenn man nicht den mathematischen Kniff der Vorlage nutzt).