Das Acht-Damen-Problem

Setze acht Damen so, dass keine zwei einander angreifen: keine gemeinsame Reihe, Linie oder Diagonale. Viele Lösungen gibt es, wenn man jede Platzierung einzeln zählt; weit weniger bleiben, sobald Drehungen und Spiegelungen des Bretts als dieselbe Lösung gelten. Ein guter Einstieg ist die Methode der Teillösung: beginne mit einigen gültigen Damen und erweitere, bis ein Konflikt zum Zurückgehen zwingt.

Die Bedingungen sind so eng, dass die meisten Teilstellungen scheitern. Systematisches Setzen, Prüfen und Zurücknehmen ist deshalb besser als zufälliges Probieren. Symmetrie dient der Buchhaltung: kongruente Lösungen werden nicht mehrfach gezählt.