Informatik

Backtracking
 
Mal wieder zur Einführung in die Problematik eine "sehr anwendungsbezogene" Aufgabe - n Damen sollen auf einem nxn-Schachbrett so hingestellt werden, dass sie sich gegenseitig nicht bedrohen. Eine Dame kann beim Schach senkrecht, waagerecht und diagonal so weit ziehen, wie sie will.
 
Das 8-Damen-Problem ist ein klassisches Schachproblem, das zuerst von M. Bezzel 1845 in einer Schachzeitung veröffentlicht wurde. 1850 hat der blinde Dr. Nauk sämtliche 92 Lösungen publiziert, der Mathematiker Gauß hatte bis zu diesem Zeitpunkt erst 72 gefunden.
 
Um den Algorithmus zu verdeutlichen, fangen wir mit 4 Damen auf einem 4x4-Schachbrett an.
(Beim 1x1-Brett ist die Lösung trivial, beim 2x2- und 3x3-Brett läßt sich leicht die Unlösbarkeit zeigen.)
Schachbrett Wir beginnen mit einer Dame in der ersten Zeile und ersten Spalte.
In der ersten Zeile kann nun keine Dame mehr gesetzt werden, da sie bedroht wäre. So kann in jeder Zeile und jeder Spalte nur eine Dame stehen, wir setzen unsere Versuche also in der zweiten Zeile fort.
Schachbrett Spalte 1 und 2 sind hier bedroht, wir setzen die nächste Dame also in die 3. Spalte.
Schachbrett Die beiden gesetzten Damen bedrohen nun alle Felder der dritten Zeile, wir gehen eine Zeile zurück und setzen die Dame ein Feld weiter nach rechts.
Schachbrett Diese Feldbelegung läßt nun eine Dame in Zeile 3 zu, wir setzen sie in die 2. Spalte und prüfen die Bedrohungen in der 4. Zeile.
Schachbrett Leider sind nun in der 4. Zeile alle Felder bedroht, keine Dame ist mehr setzbar. Wir ziehen uns eine Zeile zurück und suchen dort ein weiter rechts liegendes, nicht bedrohtes Feld. Dies gibt es nicht, wir gehen wiederum eine Zeile zurück und suchen einen weiter rechts liegenden Platz für die Dame in der zweiten Zeile. Sie steht schon am rechten Rand, also gehen wir in die erste Zeile und suchen einen neuen Platz für die erste Dame. Das ist leicht, noch kein Feld ist bedroht.
Schachbrett Diese Setzung läßt uns in der zweiten Zeile nur die 4. Spalte frei. Dorthin setzen wir die Dame und prüfen die Setzmöglichkeiten in der nächsten, der dritten Zeile.
Schachbrett Wir finden sofort eine nichtbedrohte Position in der ersten Spalte. Nun versuchen wir die 4.Zeile.
Schachbrett Die dritte Spalte in der 4. Zeile bleibt unbedroht, wir haben eine Lösung gefunden.
 
Ein Teilziel ist erreicht, es sollen aber möglichst alle Lösungen gefunden werden.
Wir entfernen die letzte Dame und suchen einen alternativen Platz in der 4. Zeile, den gibt es nicht. Nun ziehen wir uns eine Zeile zurück und versuchen dort einen unbedrohten, anderen Platz für die Dame zu finden, auch dort vergeblich. So landen wir schnell wieder in der ersten Zeile und rücken dort unsere Dame ein Feld weiter, prüfen dann die Möglichkeiten in der nächsten, also zweiten Zeile, dann in der dritten und vierten.
Schachbrett Wir erhalten die nebenstehende, zweite Lösung, wenden das gleiche Verfahren erneut an, haben aber keine weiteren Erfolge.
Nun sind Sie an der Reihe, formulieren Sie einen möglichst allgemeingültigen Algorithmus, diese Aufgabe für ein nxn-Schachbrett zu lösen.
 


 

Pfeil

verantw.: J. Frank