Acht-Damen-Problem

Acht-Damen-ProblemDas Acht-Damen-Problem wurde 1845 von M.Bezzel erstmalig in einer Schachzeitung veröffentlicht. Fünf Jahre später gab Dr. Nauk, ein blinder Schachspieler, alle 92 möglichen Lösungen an.

Die Aufgabe beim Acht-Damen-Problem ist es, alle möglichen Positionen von acht Damen auf dem Schachbrett zu ermitteln, sodass diese sich nicht gegenseitig bedrohen. Da es aber insgesamt 88 = 16777216 Gesamtmöglichkeiten für das Aufstellen von acht Damen auf einem Schachbrett gibt, sodass in jeder Zeile genau eine Dame steht, ist dieses Problem gegenwärtig nur mit einem nichtpolynomialen Algorithmus lösbar.

Prinzipiell ist es nicht notwendig, ein Schachbrett mit 8 x 8 Feldern zu betrachten. Daher können Sie im Programm die Größe des Spielfeldes von 4 x 4 bis 15 x 15 Felder an dem Rollbalken einstellen. Nach Auswahl des Schalters Simulation werden alle möglichen Kombinationen ermittelt und deren Suche grafisch veranschaulicht. So ergeben sich z.B.:

Feldgröße 4×4 5×5 6×6 7×7 8×8
Möglichkeiten 2 10 4 40 92
Feldgröße 9×9 10×10 11×11 12×12
Möglichkeiten 352 724 2680 14200

Berücksichtigt man ausschließlich Lösungen, die nicht durch Spiegelung und Drehung auseinander hervorgehen, so gibt es eindeutige Lösungen:

Feldgröße 4×4 5×5 6×6 7×7 8×8
Möglichkeiten 1 2 1 6 12
Feldgröße 9×9 10×10 11×11 12×12
Möglichkeiten 46 92 341 1787

Wählen Sie das Feld Belegungen, trägt das Programm alle gefundenen Damenstellungen in die Liste ein. Nach Beendigung der Berechnung können Sie durch Auswahl dieser Einträge die möglichen Positionen auf dem Schachbrett nachvollziehen. Die in der Liste enthaltenen Zeilen beschreiben die jeweilige Spaltennummer einer Dame auf dem Brett. Zum Beispiel bedeutet der erste Eintrag bei einem 10 x 10-Feld : 1368A59247, dass eine Dame in der 1. Zeile/1. Spalte, 2. Zeile/3. Spalte, 3. Zeile/6. Spalte usw. steht. Der Eintrag 10. bis 13. Spalte erfolgt hexadezimal, also mit den Buchstaben A, B, C und D.

Die Berechnung erfolgt unter Ausnutzung der Symmetrie der Lösungen, d.h. es wird z.B. bei dem 8×8-Spielfeld nur solange gesucht, bis erstmals das Feld E8 belegt würde.

Spielmodus

Sie können in diesem Teilprogramm einen Spielmodus testen. Haben Sie diesen aktiviert, werden Sie aufgefordert:

Positionieren Sie mit der linken Maustaste xx Damen auf dem Spielfeld !

Dabei steht für xx jeweils die Größe des Spielfeldes, voreingestellt 8. Ihre Aufgabe besteht nun darin, die acht Damen so auf dem Spielfeld unterzubringen, dass sie sich nicht schlagen können. Positionieren Sie eine Dame falsch, markiert das Programm sie mit einem roten Kreuz. Durch erneutes Anklicken entfernen Sie eine gesetzte Spielfigur.

Superdamen-Problem

Eine Dame besitzt im Schachspiel die Zugmöglichkeiten der anderen Figuren, mit Ausnahme des Springers. Betrachtet man eine „Superdame“, die auch zusätzlich wie ein Springer ziehen kann, so ergibt sich erneut die  Frage, ob man n derartige Superdamen auf einem n x n-Spielfeld positionieren kann, ohne dass sie sich gegenseitig bedrohen.
Es zeigt sich, dass dies erst ab n = 10 möglich ist. Auf dem 10 x 10-Feld existieren 4 dreh- bzw.  spiegelsymmetrische Lösungen.
Markieren Sie das Feld Superdame, so ermittelt das Programm nur Lösungen für diese Art von Dame.