8.3 Backtracking

Anhand des hier vorgestellten 4-Damen-Problems (eine Vereinfachung des bekannten 8-Damen-Problems) wird das Prinzip des Backtrackings vorgestellt. Die folgenden Bilder verdeutlichen noch einmal den Ablauf des Verfahrens. Die Damen-Steine werden inkrementell in die Reihen gesetzt, in denen Sie keine anderen Steine schlagen. Wenn keine weiteren Möglichkeiten vorhanden sind, wird ein Backtrack-Schritt eingelegt und bei einem vorhergehenden Stein eine andere Position gewählt.

      

      

      

      

      

      

      

      

      

An dieser Stelle erfolgt dann ein Backtrack-Schritt:

      

      

      

      

      

      

      

      

      

      

      

An dieser Stelle erfolgt dann ein Backtrack-Schritt:

      

An dieser Stelle erfolgt dann wiederum ein Backtrack-Schritt:

      

      

      

      

      

Jetzt wird in der Veranstaltung ein Fehler gemacht, es hätte direkt der Stein in die erste Zeile gesetzt werden sollen, anstatt in die zweite Zeile:

      

      

So wäre es direkt richtig gewesen:

      

Und mit dem letzten Schritt, kommen wir dann zur Lösung:

      

      

Lösung

      

Abschliessend wir dann noch die Lösung als Vektor skizziert:

Algorithmus