Symmetrien nutzen beim normalen Damen-Problem

Es ist schon überraschend, dass Symmetrien beim Zählen der Lösungen für das normale Damen-Problem wenig genutzt wurden. Wie man es anstellen muss, liegt nicht auf der Hand, das ist wohl der Grund. Es ist aber auch nicht furchtbar schwer.

Die Symmetrie, die man nutzen kann, stammt, mathematisch gesprochen, von der Wirkung der Dieder-Gruppe auf die Lösungen (siehe auch Gruppen-Wirkungen). Ohne Gruppen-Theorie ist die wesentliche Formel gut auf der Seite der TU Dresden erläutert. Diese Formel lautet:

    Q(n) = 8 * A(n) + 4 * P(n) + 2 * R(n), falls n > 1.

Dabei ist Q(n) die Anzahl der Lösungen, A(n) die Anzahl von Bahnen asymmetrischer Lösungen, P(n) die Anzahl von Bahnen von Punkt-symmetrischer Lösungen, und R(n) die Anzahl von Bahnen von Rotations-symmetrischer Lösungen

Der Grund-Gedanke ist: man sucht so, dass man von jeder Bahn nur eine Lösung erhält. Ist diese asymmetrisch, so führt sie zu acht Lösungen. Die Bahn der Lösung besteht aus acht Einzel-Lösungen. Hat die Lösung "nur" Punkt-Symmetrie (Drehung um 180°, aber nicht um 90°), so sind es vier einzelne in der Bahn. Eine Rotations-symmetrische Lösung liefert nur zwei.

Und wie macht man es, dass man wirklich jede Bahn beim Suchen nur einmal erwischt? Das ist vermutlich der Punkt, an dem Viele bisher nicht weiterkamen. Man kann es erreichen, wenn man vom gewohnten Schema abweicht. Das gewohnte Schema ist, dass man die Damen Reihe für Reihe setzt. Um die Symmetrie auszunutzen, soll man am besten mit eine kompletten Damen-Konstellation auf den Rand-Linien beginnen. Wir brauchen also drei oder vier Damen, die die erste und die letzte Reihe sowie die linke und die rechte Rand-Spalte besetzen. Der Fall mit drei Damen kommt dann vor, weinn eine der Damen auf einem Eck-Feld steht und sowohl eine Rand-Reihe als auch eine Rand-Spalte besetzt. Ginge es um Türme und nicht um Damen, so würden in Einzelfällen sogar nur zwei Figuren reichen, nämlich auf Eck-Feldern, die sich diagonal gegenüberliegen. Bei den Damen ist das nicht erlaubt, sie könnten sich ja schlagen.

Fast immer unterscheiden sich die Lösungen derselben Bahn in ihren Rand-Damen. Man kann einfach sehen, was mit der Rand-Konstellation unter der Wirkung der Dieder-Gruppe (d.h. bei Drehungen und Spiegelungen) passiert. Erhält man acht verschiedene Rand-Konstellationen, dann ist sie völlig unsymmetrisch. Ergänzt man sie durch weitere Damen, so kann die Lösung dadurch nicht symmetrisch werden. Deswegen braucht man nur eine von diesen acht Rand-Konstellationen.

Aufpassen muss man aber, wenn man eine symmetrische Rand-Konstellation zu einer vollständigen Lösung ergänzt. Zwar muss man auch hier nur eine Rand-Konstellation als Ausgangspunkt nehmen. Aber es können zwei Dinge passieren: man weiß nicht, ob die gefundene Lösung noch symmetrisch ist, und man kann mehrere Lösungen derselben Bahn finden. Man muss also bei jeder gefunden Lösung prüfen, wieviele Symmetrie-Varianten sie hat. In der Sprache der obigen Formel heißt das: gehört die Lösung zu den A(n), zu den P(n), oder zu den R(n)? Und andererseits muss man eine Lösung einfach "vergessen" oder "wegschmeissen", wenn man einen weiteren Vertreter derselben Bahn bereits gefunden hat oder noch finden wird. Das erreicht man am besten, indem man alle Vertreter der Bahn herstellt (die hat man vielleicht schon von der Symmetrie-Prüfung), dann diejenigen aussortiert, die nicht zur aktuellen Rand-Konfiguration passen, und zum Schluss nachsieht, ob die gefundene Lösung die kleinste unter den übrig-gebliebenen ist. Ist sie das nicht, dann muss man diese Lösung vergessen. Nur eine Lösung pro Bahn darf man zählen!

Für diejenigen, die damit arbeiten wollen, aber die Mühe scheuen, sich die Anfangs-Konstellationen selbst herzustellen, habe ich dies getan. Unter Anfangs-Konstellationen kann man sich eine Zip-Datei herunterladen, die für jede Brett-Größe zwischen 4 und 30 zwei Dateien enthält, und zwar eine Datei mit den asymmetrischen, und eine mit den symmetrischen Rand-Konstellationen.

Das Format der Dateien ist binär und fast selbst-erklärend. Die Datei besteht aus Sätzen variabler Länge, was man früher "sequential access method" nannte. Jeder Satz beginnt mit einem Satz-Längen-Feld von zwei Byte. Addiert man dieses auf die aktuelle Position innerhalb der Datei, so kommt man zum nächsten Satz.

Innerhalb eines Satzes steht zunächst ein Kennzeichen 'PP', dann eine Versions-Nummer (meist x01). Dann folgt in einem Byte die Größe des gedachten Brettes, und in zwei Bytes die Anzahl der Damen. Entsprechend dieser Anzahl folgen dann die Koordinaten-Paare x/y, pro Dame. Dabei laufen x und y von 0 bis zur Brett-Größe - 1.