Backtracking | MathePrisma

Auch das n-Damen-Problem kann man systematisch mittels Backtracking lösen:

Bei einer Lösung steht in jeder Spalte des Brettes genau eine Dame.
Die Lösung kann durch eine Folge von Entscheidungen gefunden werden:
die i-te Entscheidung legt die Position der Dame in der i-ten Spalte fest.

Wieviele Möglichkeiten gibt es für die i-te Entscheidung?

Und wann ist eine Entscheidung erkennbar falsch?

wenn die Position von einer der bereits gesetzten Damen bedroht wird
wenn die neue Dame eine der bereits gesetzten bedroht
wenn die neue Dame auf ein Feld einer anderen Farbe als die zuletzt gesetzte kommt
wenn in der Spalte noch ein weiteres Feld unbedroht ist

Hier ist die Verwendung von Backtracking vorgeschrieben.

Es gibt immer nur genau ein Feld ('das richtige'), das du anklicken sollst. Dabei wird eine Dame gesetzt oder entfernt).
Erkennbar falsche Entscheidungen sollst du gar nicht erst treffen.
Die möglichen Entscheidungen für die Position in eine Spalte werden immer in der Reihenfolge 'von oben nach unten' gefällt.

Wenn du das Prinzip verinnerlicht hast, bearbeite folgende Aufgabe.

Und hier findest du die elegante Version

n-Damen rekursiv