Das Damen-Problem
Auf dieser Seite finden Sie Informationen zum Damen-Problem (engl: n queens problem); dabei geht es darum, n (Schach-)Damen so auf ein n x n (Schach-)Brett zu stellen, dass keine von ihnen eine andere schlagen kann.
- Gibt es für jedes n eine Lösung?
- Wie viele Lösungen gibt es? (d.h. Abzählen der verschiedenen Möglichkeiten, die n Damen "friedlich" aufzustellen)
- Haben solche Aufstellungen besondere Eigenschaften?
- Wie kann man diese Lösungen klassifizieren? Sind manche Lösungen in irgend einem Sinn "benachbart" oder "ähnlich"?
- Kann man eine Landkarte aller Lösungen zeichnen?
- Gibt es Verbindungen zu anderen bekannten Problemen? Kann man das Problem verallgemeinern, und welche Verallgemeinerungen sind am interessantesten?
- Was sind die besten Algorithmen, um alle Lösungen zu finden - oder um eine Lösung zu finden - oder um Lösungen mit gegebenen speziellen Eigenschaften zu finden?
Warnung: auch wenn in dieser Erklärung zweimal von Schach die Rede ist - für echte Schach-Probleme wird Ihnen die Information auf dieser Seite nichts bieten.
Einführung
Die historische Wurzel des Problems ist der Fall n=8, also das ganz normale Schachbrett; es wurde schon im 19ten Jahrhundert diskutiert. Zuerst aufgestellt hat es Max Bezzel im Jahr 1848, und auch der große Mathematiker Carl Friedrich Gauss hat sich damit befasst.
Die üblichste - und nützlichste - Verallgemeinerung ist das "Torus-Problem".
Was heißt "Torus-Problem"? Es bedeutet, dass die Damen in ihren Bewegungs-Möglichkeiten nicht durch die Ränder des Brettes eingeschränkt sind. Es gibt zwei Möglichkeiten, sich das zu veranschaulichen: einerseits kann man sich das Brett elastisch und auf einen Zylinder aufgewickelt vorstellen. Für das Damen-Torus-Problem ist das schon alles, was notwendig ist, obwohl eine aufgewickeltes Brett erst der halbe Weg von einem Rechteck zu einem Torus ist. Dieser erste Schritt beseitigt zwei Ränder. Der zweite Schritt beseitigt auch noch die beiden anderen Ränder, indem er den Zylinder in einen Ring verformt - so wie ein Rettungsring oder ein Fahrrad-Schlauch. Dies ist die Form, die Mathematiker als Torus bezeichnen, und sie unterscheidet sich von einem Zylinder in andere Hinsicht - für das Damen-Problem aber sind Zylinder und Torus äquivalent.
Die zweite Möglichkeit, sich das Damen-Torus-Problem zu veranschaulichen, ist die folgende: denken Sie sich eine randlose, unendlich große (Schachbrett-)Ebene (oder auch ein großes "Kästchen-Papier"); auf dieser stehen unendlich viele Damen in periodischem Abstand. Das "n" verändert seine Bedeutung: von der Größe des (Schach-)Brettes wird es zur periodischen Distanz der Damen. Eine Lösung des Problems bedeutet dann, dass sich in jedem n mal n Quadrat auf dieser Ebene genau n Damen befinden, und dass alle Damen in der ganzen Ebene immer nur ihre "periodischen Schwestern" erreichen können.
Weitere Informationen
Prof.Kosters in Leiden (Niederlande) betreut eine Bibliografie, die schon im Jahr 2000, bevor das Internet so verbreitet war, gut 80 Artikel zum Damen-Problem enthielt. Inzwischen sind es über 330 Artikel und Links.
Zwei bunte Bilder zu Torus, n= 13
Hier noch zwei bunte Bilder mit mehreren Torus-Lösungen auf einem 13 × 13 Feld, zufällig ausgewählt. Damen zu verschiedenen Lösungen haben verschiedene Farben.
Für ein genaueres Verständnis von T13 können Sie bei Torus-Bilder für n=13 nachsehen.