n-Damen-Idee

n-Damen: platziere n Damen so, dass keine zwei sich schlagen (gleiche Zeile, Spalte, Diagonale). Backtracking setzt zeilenweise und prüft Konflikte.

Die Zahl der Lösungen wächst schnell; Pruning ist essenziell.

Vollständige Platzierung: N-Queens [1].

Wo gebraucht

Kanonisches Constraint-Beispiel. Übertragbar auf Stundenpläne, Platzierung ohne Konflikte, Resource-Assignment mit harten Regeln.

Vertiefung

Beim n-Damen-Problem genügt es, zeilenweise genau eine Dame zu setzen. Der Zustand kann dadurch als Folge gewählter Spalten beschrieben werden. Besetzte Spalten und beide Schrägrichtungen liefern lokale Konflikttests, ohne jedes Mal alle bereits gesetzten Damen paarweise zu vergleichen.

Zwei Felder liegen auf derselben Schrägen, wenn Zeilen- und Spaltendifferenz betragsgleich sind. Praktisch lassen sich die Schrägen über die Kennzahlen Zeile minus Spalte und Zeile plus Spalte verwalten. Nach jeder Platzierung werden drei Mengen ergänzt und nach dem Rekursionsaufruf wieder bereinigt.

Schwierigkeitsstufen

1. Konflikte einer neuen Dame auf einem kleinen Brett erkennen.
2. Spalten und beide Diagonalrichtungen als Mengen modellieren.
3. Symmetrien nutzen, ohne Lösungen falsch zu zählen.

Fallstricke

Typische Fehler sind vertauschte Diagonalformeln und unvollständiges Entfernen beim Zurückgehen. Wer zusätzlich jede Zeile als frei oder belegt speichert, dupliziert Information und vergrössert die Fehlerfläche unnötig.