Backtracking

Problem: Finde eine Stellung für n Damen auf einem Schachbrett der Größe n x n, so daß sie sich nicht gegenseitig bedrohen.

Lösungsidee:

Schritt für Schritt eine Lösung aufbauen, indem eine Dame nach der anderen auf das Brett gestellt wird.

Wenn es keinen zulässigen Platz für die k-te Dame gibt, wird die (k-1)-te Dame vom Brett zurückgenommen und eine andere (noch nicht vorher probierte Position verwendet).

Dies wird solange durchprobiert, bis entweder eine Lösung gefunden wird oder alle Möglichkeiten durchprobiert sind und damit feststeht, daß es keine Lösung gibt.