Reduzierung des Lösungsraumes

Backtracking ist eine systematische Suche des gesamten Zustandsraumes nach akzeptablen Zuständen.

In vielen Fällen ist der gesamte Zustandsraum zu umfangreich, um in akzeptabler Zeit vollständig untersucht zu werden. So gibt es beim n-Damen-Problem insgesamt
n²!
(n²-n)!
Möglichkeiten, n Damen auf einem Schachbrett unterzubringen. Im Falle von n = 8 sind dies nicht weniger als
64!
56!
= 178.462.987.637.760 > 10¹⁴
Möglichkeiten.

Bei der schrittweisen Vorgehensweise des Backtracking liegt es daher nahe,

die Auswahl der möglichen Züge geschickt zu begrenzen und

sofort zu überprüfen, ob von der Teil-Lösung gewisse notwendige Kriterien eingehalten werden, die sich aus der Bedingung für eine akzeptable Gesamt-Lösung ableiten lassen.

Beim n-Damen-Problem ist es deswegen sinnvoll,

bei der k-ten Dame nur die k-te Zeile auf dem Schachbrett für die nächste Position zu berücksichtigen und

jede neu hinzukommende Dame sofort dahingehend zu untersuchen, ob sie bereits von den zuvor gesetzten Damen bedroht wird.