Gruppen und Gruppen-Wirkungen beim Damen-Problem
Meiner Meinung nach gibt es ein Haupt-Werkzeug, um die Lösungen des Damen-Problems zu klassifizieren und zu zählen. Das sind sogenannte Gruppen-Wirkungen (englisch: group actions). Dabei kann man sich auf endliche Gruppen beschränken, die auf eine ebenfalls endliche Menge wirken. Solche Gruppen-Aktionen werden in der heutigen Literatur zum Damen-Problem, so weit ich sie kenne, nicht diskutiert; ich denke jedoch, dies wäre nützlich.
Gruppen und Gruppen-Wirkungen sind das geeignete Werkzeug, um Symmetrie-Fragen zu behandeln. Diese Symmetrien kann man einerseits zu effizienterer Suche, andererseits zu einer besseren Klassifizierung verwenden.
In diesem Zusammenhang ist es natürlich, nicht nur die "normalen" und die Torus-Lösungen zu betrachten, sondern auch einige andere Mengen, in denen diese Lösungen enthalten sind.
Um zu Gruppen-Aktionen zu kommen, gehen wir von Bewegungen des Brettes aus. Sie wirken einerseits auf der Menge der Felder; andererseits induzieren sie aber auch Abbildungen zwischen den kompletten Lösungen.
Die einfachste solche Gruppe besteht aus Spiegelungen und Drehungen um 90° oder ein Vielfaches davon. Es ist klar, dass eine "normale" Lösung unter einer solchen Bewegung eine "normale" Lösung bleibt. Ebenso gilt dies für die Torus-Lösungen. Diese Gruppe bezeichnen die Mathematiker als die Dieder-Gruppe D4 (engl. dihedral group).
Zwei noch kleinere Gruppen, Untergruppen von D4, werden im Zusammanhang mit der Damen-Problem verwendet: die Gruppe "Mirror", die nur aus der Identität und der Spiegelung an der vertikalen Achse besteht, und die Dreh-Gruppe, die aus den Drehungen um 0, 90, 180 und 270 Grad besteht.
Interessanter sind natürlich noch größere Gruppen. Die nächstgrößere enthält zusätzlich die Verschiebungen auf dem Torus. Im weiteren nenne ich sie die Kongruenz-Gruppe oder Gruppe der kongurenten Bewegungen. Diese Bewegungen bringen allerdings eine Komplikation für die normalen Damen-Lösungen: nach einer Verschiebung muss eine Lösung keine Lösung mehr sein. Die Bahnen der Gruppen-Wirkung führen also aus der Menge der Lösungen heraus.
Um wieder eine "ordentliche" Menge zu bekommen, haben wir hier die folgende Überlegung: jede Damen-Lösung lässt sich als Permutation interpretieren. Nehmen wir alle Permutationen und übersetzen sie auf diese Weise in Stellungen, so ergibt das in der Schach-Sprache das n-Türme-Problem anstelle des Damen-Problems. Die Menge aller Turm-Stellungen - oder äquivalent dazu die Menge aller Permutationen - ist eine Menge, auf der die Kongruenz-Gruppe "ordentlich" wirkt, das heißt ohne die beschriebene Komplikation.
Damit haben wir die Grundmenge erheblich vergrößert, vielleicht zu viel. Es gibt auch Teilmengen der Permutationen, die wir betrachten können, wenn wir die Damen-Lösungen untersuchen. Dazu können wir jeder Permutation die maximale Anzahl von Damen auf einer Torus-Diagonale oder Gegen-Diagonale zuordnen. Die Teilmenge, bei der dieses Maximum 1 ist, ist genau die Menge der Torus-Lösungen. Die Teilmenge, bei der das Maximum <= 2 ist, enthält alle normalen Damen-Lösungen. Diese Menge ist gleichzeitig stabil unter der Wirkung der Kongruenz-Gruppe.
Es gibt jetzt noch (mindestens) zwei weitere Schritte für Gruppen-Aktionen, das heißt zwei größere Bewegungs-Gruppen, die man auf die Lösungen oder eine umfassendere Menge anwenden kann. Eine ist die Gruppe der Ähnlichkeits-Abbildungen, die andere die Gruppe aller affinen Abbildungen. Mit den Ähnlichkeits-Abbildungen passt die obige "Max Anzahl Damen auf Diagonale <= 2" Menge. Für die affinen Abbildungen muss man die Grundmenge der n-Permutationen erweitern. Welche Menge die geeignetste ist, weiß ich bisher nicht; sicherlich ist es eine Untermenge von "n aus n²", also der Menge der n-elementigen Teilmengen von n², oder in der Sprache des Schachs die Menge der Stellungen, die n gleiche Figuren überhaupt einnehmen können, ohne dass von "Schlagen" die Rede ist. Aber vielleicht sollte man diese Menge weiter einschränken. Die Menge der affinen Abbildungen kann man noch auf die regulären affinen Abbildungen einschränken, das heißt auf diejenigen, deren Determinante 1 ist.
Die Gruppe der Ähnlichkeits-Abbildungen bedarf noch der Erläuterung. Die habe ich hier noch nicht (sorry), werde sie aber in den nächsten Monaten einfügen.
Nebenbei: Ich habe viel über Gruppen-Aktionen in dem Buch "Applied Finite Group Actions" von A.Kerber, 2nd edition, Springer 1999, ISBN 3-540-65941-2 gelernt. Das Damen-Problem wird in diesem Buch nicht erwähnt, aber viele andere Beispiele. Natürlich gibt es auch etliche andere Bücher zur Gruppentheorie, in denen man die Grundlagen finden kann.