Sackgassen und Rückzüge

Verfahren, die schrittweise Möglichkeiten durchprobieren und im Falle von ``Sackgassen'' zuvor gemachte Schritte wieder zurücknehmen, um neue Varianten zu probieren, nennen sich Backtracking-Verfahren.

Eine Sackgasse beim 8-Damen-Problem zeigt das obige Diagramm, da es nicht möglich ist, eine weitere Dame unterzubringen.
Hinweis: Hier wurde versucht, in jedem Schritt eine weitere Dame in der nächsten Zeile unterzubringen, beginnend mit der obersten (Zeile 8) und dann weiter nach unten fortfahrend.

Um zu einer Lösung zu gelangen, muß hierbei nicht nur die 5. Dame zurückgenommen werden, sondern sogar alle Damen mit Ausnahme der allerersten.

Erst wenn die 2. Dame von C7 auf E7 (oder auf F7 oder G7) vorgeschoben wird, gibt es eine Lösung.

	Verfahren, die schrittweise Möglichkeiten durchprobieren und im Falle von ``Sackgassen'' zuvor gemachte Schritte wieder zurücknehmen, um neue Varianten zu probieren, nennen sich Backtracking-Verfahren.
	Eine Sackgasse beim 8-Damen-Problem zeigt das obige Diagramm, da es nicht möglich ist, eine weitere Dame unterzubringen. Hinweis: Hier wurde versucht, in jedem Schritt eine weitere Dame in der nächsten Zeile unterzubringen, beginnend mit der obersten (Zeile 8) und dann weiter nach unten fortfahrend.
	Um zu einer Lösung zu gelangen, muß hierbei nicht nur die 5. Dame zurückgenommen werden, sondern sogar alle Damen mit Ausnahme der allerersten.
	Erst wenn die 2. Dame von C7 auf E7 (oder auf F7 oder G7) vorgeschoben wird, gibt es eine Lösung.