Backtracking anhand des Damenproblems

Was ist das Damenproblem ?

Bei dem Damenproblem handelt es sich um ein Mathematisches Problem, dass auf den bestehenden Schachregeln beruht.

Gegeben ist ein quadratisches Schachfeld, welches mindestens n > 3 Felder groß sein muss. Auf diesem wird nun in jeder Spalte eine Dame platziert. Diese Damen dürfen sich aber nicht gegenseitig mit den bekannten Schachregeln schlagen dürfen, sondern müssen so angeordnet sein, dass sie sich gegenseitig nicht bedrohen. Für jede Anzahl an Felder gibt es dabei mindestens eine Lösung.

Im obigen Bild ist eine mögliche Lösung für das Damenproblem zu erkennen.

Lösung im Pseudocode

Das Vorgehen, um eine Lösung zu finden könnte folgendermaßen aussehen:

function backtrack {

	BETRACHTE Moeglichkeiten Zeile
	
	WENN 0 Moeglichkeiten
		DANN GIB keine Loesung zurueck
	SONST
		FÜR jede moeglichkeit
			SETZE Dame auf moeglichkeit
			backtrack fuer naechste Zeile
			
			WENN Loesung gefunden
				GIB Loesung zurueck
}	

Die oben abgebildete Lösung habe ich mit Simon erarbeitet. Ähnlichkeiten könne also vorkommen.

Bei diesem Vorgehen wird jede Möglichkeit, eine Dame zu platzieren, betrachtet. Sollte es jedoch keine Möglichkeit geben, auf die eine Dame gesetzt werden kann, so bricht man ab, und führt das ganze eine Zeile vorher aus. Andernfalls wird jede gefundene Möglichkeit getestet. Dabei wird die Dame auf die jeweilige Möglichkeit gesetzt und für die nächste Zeile wird die Funktion rekursiv aufgerufen, sodass man die Anzahl der Lösungen für die weiteren Zeilen weiß. Anhand dieses Ergebnisses, kann nun festgestellt werden, ob man die Dame auf ein nächstes Feld setzen muss, oder die Lösung gefunden hat.

Backtracking

Wie oben schon angedeut, ist das Problem mit Backtracking gelößt worden.

function Backtrack
  Suche Lösung
  wenn Lösung gefunden
    führe Backtracking für nächste Zeile
  Sonst 
    führe Backtracking für letzte Zeile durch

Am einfachsten ist es, sich dieses Verfahren an einem Baumdiagramm vorzustellen: Jeder Ast stellt eine Lösung dar. Dabei gehen wir solange einen Ast entlang, bis keine Lösung mehr gefunden werden kann. Ist dies der Fall, so gehen wir zurück bis zum letzten Knoten und gehen den nächsten Ast entlang.

Implementierung

Nachdem eine Dame gesetzt wurde, muss für alle Felder, die diese Dame bedroht, auch die Bedrohung um 1 erhöht werden.

private void bedrohungenDurchDame(int x, int y, int delta, Zuhoerer zuhoerer) {
	for (int i=0; i<n; i++) {
		aendereBedrohung(x, i, delta, zuhoerer);            // Spalte
		if (i!=x) aendereBedrohung(i, y, delta, zuhoerer);  // Zeile (ohne erneut eig. Feld)
		aendereBedrohung(x-i, y-i, delta, zuhoerer);        // Diag. links runter
		aendereBedrohung(x-i, y+i, delta, zuhoerer);        // Diag. links hoch
		aendereBedrohung(x+i, y-i, delta, zuhoerer);        // Diag. rechts runter
		aendereBedrohung(x+i, y+i, delta, zuhoerer);        // Diag. rechts hoch
	}
}

x und y sind dabei die Position, auf die die Dame gesetzt wurde. Zusätzlich gibt delta an, ob eine Bedrohung hinzukommt, oder ob eine weggenommen wurde. Würde also eine Dame gesetzt werden, so würde delta = 1 sein, weil delta bei jedem Feld auf die vorhandenen Bedrohungen addiert wird.

Das Vorgehen bei dieser Methode ist, dass man sich ein Quadrat vorstellt, welches nach jedem Durchlauf der for-Schleife sich um 1 vergrößert. Dabei bleibt die Anzahl der zu ändernden Felder gleich, unabhängig von der Größe des Quadrates. Damit hat man dann alle Felder abgedeckt, die durch die Dame bedroht werden. (Waagerecht und Diagonal)

public Pos[] backtrack(int row, Zuhoerer zuhoerer) {
	Pos[] moeglichkeiten = getMoeglichkeiten(row);

	for (Pos p : moeglichkeiten) {
		setzeDame(p.getX(), p.getY(), zuhoerer); //Setzt Dame auf die Möglichkeit
		aktualisiereFeld();
		Pos[] loesung = backtrack(row + 1, zuhoerer); //Für die nächste Reihe Lösungen speichern

		if (loesung != null) return loesung; //Lösung wurde gefunden
		entferneDame(p.getX(), p.getY(), zuhoerer); 
	}
	return null;
}

private Pos[] getMoeglichkeiten(int row){
	List<Pos> moeglichkeiten = new ArrayList<>();

	for (int i = 0; i < bedrohung[row].length; i++) {
		if (bedrohung[row][i] == 0) moeglichkeiten.add(new Pos(row, i));
	}

	return moeglichkeiten.toArray(new Pos[0]);
}

Alle Möglichkeiten werden in einem Array vom Typ Pos gespeichert. Diese werden durch die Methdode getMoeglichkeiten() für jede Reihe berechnet. Dannach wird die Dame auf eine Möglichkeit gesetzt. Für die nächste Reihe wird dann die Methode backtrack() rekursiv aufgerufen. Dabei kann dann festgestellt werden, ob für die Position der Dame eine Lösung gefunden werden kann. Sollte also eine Lösung gefunden worden sein, so kann mit return die for-Schleife abgebrochen werden. Andernfalls setzte man die Dame auf die nächste Lösung. Am Ende ist die for-Schleife komplett über alle Positionen iteriert und die Methode gibt null zurück, da keine Lösung gefunden wurde.

Alle Lösungen finden

Weiterhin besteht die Möglichkeit, dass man alle Möglichkeiten für n zurückgibt:

backtrack_all()
    FALLS die Anzahl der Damen n ist
        Speichere die Position der Damen
        GIB keine Lösung zurück
    finde die erste Spalte ohne Dame
    DURCHLAUFE ALLE Felder dieser Spalte
        FALLS das Feld unbedroht ist
            setze eine Dame auf das Feld
            backtrack_all()
            entferne die Dame wieder vom Feld
    GIB keine Lösung zurück