Acht-Damenproblem - Lösung

Eine erste Strategie ist, immer in jeder Spalte eine Dame zu stellen und jeweils im Springer-Abstand. Das kommt dann allerdings nach einigen Spalten nicht mehr hin, da sich die Damen diagonal schlagen, daher müssen einige Damen noch weiter geschoben werden. Man muss so lange suchen, bis eine Lösung gefunden ist, in der auch diagonal keine Bedrohung mehr stattfindet.

Wegen der Komplexität des Spiels wurde erst 1969 mit Computerhilfe gezeigt, dass es 92 Lösungen gibt, wenn man auch zueinander symmetrische Lösungen mitrechnet. Diese Lösungen kann man sich unten auflisten oder graphisch darstellen lassen.

Der im Programm verwendete Algorithmus sucht systematisch, indem spaltenweise jeweils eine neue Dame positioniert wird und die Positionen durchprobiert werden. Führt das nicht zum Ziel, wird jeweils in die vorige Spalte zurück gegangen und dort weiter probiert. Der Algorithmus benötigt für die erste Lösung 218 Durchläufe, d.h. bei der 218. Bearbeitung einer Spalte wird eine Lösung gefunden.