Aspekte des Damen-Problems
Gruppen-Wirkungen
Such-Algorithmus
Symmetrie nutzen, normales Damen-Problem
Stammbäume
Besonderheiten
Halsbänder
Konflikte
Konflikt-Tabellen
Minimal-Lösung und gierige Folge
Weltrekorde
Tabellen von Zähl-Ergebnissen
Bilder für n=8
Torus Bilder für n=13
Andere Seiten und Kommentare
Weitere Quellen
 
 
Andere Themen
Anzahl Primzahlen, die man als Summe von Faktoren erhält
Primzahl aus falscher binomischer Formel
Zahlen nach Primfaktor-Verteilung
 
 
 
Diese Seite in einer anderen Sprache
Englisch

Das Damen-Problem

Drei Lösungen für ein 13 x 13 Schachbrett, in verschiedenen Farben.

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.

Ausgehend von dieser Frage ergeben sich weitere Fragen:
  • 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.

  Seiten-Anfang
Erstellt von Matthias Engelhardt
Mail an Matthias Engelhardt
 
last change: 2014-02-05
Address of page: http://nqueens.de/index.de.html