# Damenproblem

Das Damenproblem ist eine schachmathematische Aufgabe. Es sollen jeweils acht Damen auf einem Schachbrett so aufgestellt werden, dass keine zwei Damen einander gemäß ihren in den Schachregeln definierten Zugmöglichkeiten schlagen können. Die Figurenfarbe wird dabei ignoriert, und es wird angenommen, dass jede Figur jede andere angreifen könnte. Solcherart auf dem Schachbrett angeordnete Figuren werden auch als „unabhängig“ bezeichnet. Für Damen heißt dies konkret und anders ausgedrückt: Es dürfen keine zwei Damen auf derselben Reihe, Linie oder Diagonale stehen.
Im Mittelpunkt steht beim Damenproblem die Frage nach der Anzahl der möglichen Lösungen. Im Falle des klassischen 
  
    
      
        8
        ×
        8
      
    
    {\displaystyle 8\times 8}
  
-Schachbretts gibt es 
  
    
      
        92
      
    
    {\displaystyle 92}
  
 verschiedene Möglichkeiten, die Damen entsprechend aufzustellen. Betrachtet man Lösungen als gleich, die sich durch Spiegelung oder Drehung des Brettes auseinander ergeben, verbleiben noch 
  
    
      
        12
      
    
    {\displaystyle 12}
  
 Basis-Lösungen.
Das Problem kann auf quadratische Schachbretter beliebiger Größe verallgemeinert werden: Dann gilt es, 
  
    
      
        n
      
    
    {\displaystyle n}
  
 unabhängige Damen auf einem Brett von 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 Feldern zu positionieren (mit 
  
    
      
        n
      
    
    {\displaystyle n}
  
 als Parameter aus den natürlichen Zahlen).


## Geschichte
Erstmals formuliert wurde das Damenproblem von dem bayerischen Schachmeister Max Bezzel. In der Berliner Schachzeitung fragte er 1848 nach der Anzahl der möglichen Lösungen. Als erster nannte 1850 der Zahnarzt Franz Nauck in der Leipziger Illustrirten Zeitung die korrekte Zahl 
  
    
      
        92
      
    
    {\displaystyle 92}
  
. 1874 bewies der englische Mathematiker James Whitbread Lee Glaisher, dass es nicht mehr Lösungen geben kann. Damit war das ursprüngliche Problem vollständig gelöst. Auch Carl Friedrich Gauß zeigte Interesse an dem Problem, weshalb es irrtümlich häufig auf ihn zurückgeführt wird; er hatte indessen nur 
  
    
      
        72
      
    
    {\displaystyle 72}
  
 der Lösungen gefunden.
Nauck verallgemeinerte die Problemstellung und fragte, auf wie viele verschiedene Arten 
  
    
      
        n
      
    
    {\displaystyle n}
  
 Damen auf einem 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
-Schachbrett aufgestellt werden können.

Im Jahre 1992 fanden Demirörs, Rafraf und Tanik eine Äquivalenz zwischen magischen Quadraten und Damenproblemen.
Das Damenproblem tauchte auch in den Computerspielen The 7th Guest und The Whispered World auf. Im Nintendo DS Titel Professor Layton und das geheimnisvolle Dorf muss es vom Spieler in unterschiedlicher Form sogar mehrfach gelöst werden.


## Anzahl der Lösungen im klassischen Damenproblem
Das klassische Problem mit acht Damen auf einem 
  
    
      
        8
        ×
        8
      
    
    {\displaystyle 8\times 8}
  
-Brett hat 
  
    
      
        92
      
    
    {\displaystyle 92}
  
 verschiedene Lösungen. Wenn man solche, die durch Drehen oder Spiegeln des Brettes aufeinander abgebildet werden, nur einfach zählt, bleiben 
  
    
      
        12
      
    
    {\displaystyle 12}
  
 eindeutige Lösungen übrig (die unterschiedlichen Farben der Felder werden nicht beachtet). Da es für jede dieser reduzierten Lösungen vier Spiegelungen (an Diagonalen, Horizontale und Vertikale durch die Brettmitte) und drei Rotationen ( 
  
    
      
        
          90
          
            ∘
          
        
      
    
    {\displaystyle 90^{\circ }}
  
,
  
    
      
        
          180
          
            ∘
          
        
      
    
    {\displaystyle 180^{\circ }}
  
,
  
    
      
        
          270
          
            ∘
          
        
      
    
    {\displaystyle 270^{\circ }}
  
) gibt, könnte man eine Gesamtzahl von 
  
    
      
        8
        ×
        12
        =
        96
      
    
    {\displaystyle 8\times 12=96}
  
 Lösungen vermuten. Da aber eine der Lösungen (siehe Diagramm) bei einer Drehung um 
  
    
      
        
          180
          
            ∘
          
        
      
    
    {\displaystyle 180^{\circ }}
  
 in sich selbst übergeht, und die Spiegelung an der Horizontalen dasselbe ergibt wie die Spiegelung an der Vertikalen und die Drehung um 
  
    
      
        
          90
          
            ∘
          
        
      
    
    {\displaystyle 90^{\circ }}
  
 dasselbe ergibt, wie die Drehung um 
  
    
      
        
          270
          
            ∘
          
        
      
    
    {\displaystyle 270^{\circ }}
  
 und die Spiegelung an der einen Diagonalen dasselbe ergibt, wie die Spiegelung an der anderen Diagonalen, lassen sich aus dieser nicht 7 neue Lösungen konstruieren, sondern nur 3; also 4 weniger. Es ergeben sich insgesamt 
  
    
      
        92
      
    
    {\displaystyle 92}
  
 Lösungen.


## Anzahl der Lösungen im verallgemeinerten Damenproblem
Das verallgemeinerte Damenproblem verlangt, 
  
    
      
        n
      
    
    {\displaystyle n}
  
 Damen auf einem Brett von 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 Feldern so zu positionieren, dass sie einander nicht diagonal, senkrecht und waagerecht gegenüber stehen.


### Anzahl der Lösungen bis zur Brettgröße 27 × 27
Die folgende Tabelle führt die Anzahl der eindeutigen Lösungen und die der gesamten Lösungen bis zur Brettgröße 
  
    
      
        27
        ×
        27
      
    
    {\displaystyle 27\times 27}
  
 auf:

Die zuvor bekannte, aber nicht überprüfte Lösungszahl für 
  
    
      
        n
        =
        12
      
    
    {\displaystyle n=12}
  
 wurde 1969 unabhängig voneinander von Torbjörn Lindelöf und Bernd Schwarzkopf per Computeranalysen bestätigt. Lindelöf errechnete dabei auch die Größen von 
  
    
      
        n
        =
        13
      
    
    {\displaystyle n=13}
  
 und 
  
    
      
        n
        =
        14
      
    
    {\displaystyle n=14}
  
. 1970 errechnete Lindelöf die Zahl für 
  
    
      
        n
        =
        15
      
    
    {\displaystyle n=15}
  
 mit der Bemerkung, dass Computer die 50- bis 100-fache der zu dieser Zeit üblichen Rechenkapazität für größere Schachbretter benötigen.
Die Lösungszahl für 
  
    
      
        n
        =
        26
      
    
    {\displaystyle n=26}
  
 wurde am 11. Juli 2009 vom Queens@TUD-Projekt mit FPGA-Lösern bestimmt und am 30. August 2009 vom MC#-Projekt auf zwei russischen Superrechnern der damals aktuellen TOP500-Liste bestätigt. Nach mehr als 7 Jahren folgte am 19. September 2016 die Lösungszahl für 
  
    
      
        n
        =
        27
      
    
    {\displaystyle n=27}
  
. Diese konnte in einem Nachfolgeprojekt unter Ausnutzung weiterer Problemsymmetrien und der gesteigerten technischen Leistungsfähigkeit wieder mit Hilfe von FPGA-Lösern berechnet werden. Die Bestätigung dieser Zahl durch ein zweites unabhängiges Projekt steht noch aus.
Allgemein lässt sich feststellen, dass die Anzahl der Lösungen etwas schneller als exponentiell mit der Brettgröße anwächst.
Interessanterweise gibt es auf dem 
  
    
      
        2
        ×
        2
      
    
    {\displaystyle 2\times 2}
  
-Brett sowie auf dem 
  
    
      
        6
        ×
        6
      
    
    {\displaystyle 6\times 6}
  
-Brett weniger Lösungen als auf dem jeweils kleineren Brett.


### Anzahl der Lösungen für große n
Eine obere Schranke für die Lösungsanzahl 
  
    
      
        D
        (
        n
        )
      
    
    {\displaystyle D(n)}
  
 des Damenproblems auf einem 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
-Brett ist 
  
    
      
        n
        !
      
    
    {\displaystyle n!}
  
 . Dies ist die Anzahl von Lösungen für 
  
    
      
        n
      
    
    {\displaystyle n}
  
 einander nicht bedrohende Türme. Die Aufstellungen voneinander nicht bedrohenden Damen (für 
  
    
      
        n
        >
        1
      
    
    {\displaystyle n>1}
  
) sind eine echte Teilmenge hiervon.
Die asymptotische Form von 
  
    
      
        D
        (
        n
        )
      
    
    {\displaystyle D(n)}
  
 ist nicht bekannt. Rivin u. a. stellen die Vermutung auf, dass

  
    
      
        
          lim
          
            n
            →
            ∞
          
        
        
          
            
              log
              ⁡
              
                D
                (
                n
                )
              
            
            
              n
              log
              ⁡
              
                n
              
            
          
        
        =
        β
        >
        0
      
    
    {\displaystyle \lim _{n\to \infty }{\frac {\log {D(n)}}{n\log {n}}}=\beta >0}
  
 ist.
Aus den bekannten Gliedern der Folge lässt sich für große 
  
    
      
        n
      
    
    {\displaystyle n}
  
 folgende Näherungsformel abschätzen:

  
    
      
        D
        (
        n
        )
        
        ≈
        
        
          c
          
            n
            −
            1
          
        
        ×
        n
        !
      
    
    {\displaystyle D(n)\,\approx \,c^{n-1}\times n!}
  
  mit  
  
    
      
        c
        =
        
          
            243
            625
          
        
        ≈
        0,388
        8
      
    
    {\displaystyle c={\frac {243}{625}}\approx 0{,}3888}
  
 .


## Algorithmen zur Lösungssuche
Das Damenproblem ist ein gutes Beispiel für ein einfach zu formulierendes Problem mit nicht-trivialen Lösungen. Eine Reihe von Programmiertechniken ist geeignet, alle Lösungen zu erzeugen. Klassisch ist rekursives Backtracking; dieses ist besonders einfach zu realisieren mit logischer Programmierung. Eine weitere Möglichkeit sind genetische Algorithmen.
Derartige Ansätze sind wesentlich effizienter als ein naiver Brute-Force-Algorithmus, der (im 
  
    
      
        8
        ×
        8
      
    
    {\displaystyle 8\times 8}
  
-Fall) alle 
  
    
      
        64
        ×
        63
        ×
        62
        ×
        61
        ×
        60
        ×
        59
        ×
        58
        ×
        57
      
    
    {\displaystyle 64\times 63\times 62\times 61\times 60\times 59\times 58\times 57}
  
 (
  
    
      
        <
        
          64
          
            8
          
        
        =
        
          2
          
            48
          
        
      
    
    {\displaystyle <64^{8}=2^{48}}
  
) möglichen Positionierungen der acht Damen durchprobiert und dabei alle Stellungen ausfiltert, in denen jeweils zwei Damen einander schlagen könnten. Dieser Algorithmus erzeugt mehrfach die gleichen Lösungen, wenn Permutationen der Damen gleiche Felder besetzen.
Ein etwas effizienterer Brute-Force-Algorithmus platziert nacheinander in jeder Reihe nur eine Dame und reduziert dadurch die Komplexität auf 
  
    
      
        
          8
          
            8
          
        
        =
        
          2
          
            24
          
        
      
    
    {\displaystyle 8^{8}=2^{24}}
  
 mögliche Stellungen.


### Rekursives Backtracking
Das Damenproblem kann durch einen rekursiven Algorithmus effizient gelöst werden, indem das Problem mit 
  
    
      
        n
      
    
    {\displaystyle n}
  
 Damen so aufgefasst wird, dass es gilt, zu jeder Lösung mit 
  
    
      
        n
        −
        1
      
    
    {\displaystyle n-1}
  
 Damen eine weitere Dame hinzuzufügen. Letztendlich lässt sich jedes Damenproblem damit auf ein Problem mit 
  
    
      
        0
      
    
    {\displaystyle 0}
  
 Damen zurückführen, was nichts anderes als ein leeres Schachbrett ist.
Das folgende Python-Programm findet alle Lösungen des 
  
    
      
        n
      
    
    {\displaystyle n}
  
-Damen-Problems mit Hilfe eines rekursiven Algorithmus. Ein 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
-Brett wird dabei rekursiv auf kleinere Bretter mit geringerer Anzahl an Reihen, 
  
    
      
        n
        ×
        (
        n
        −
        1
        )
        ,
        n
        ×
        (
        n
        −
        2
        )
        ,
        …
      
    
    {\displaystyle n\times (n-1),n\times (n-2),\dots }
  
 reduziert.
Das Programm nutzt direkt aus, dass keine zwei Damen in der gleichen Reihe stehen.
Außerdem wird benutzt, dass eine Lösung mit 
  
    
      
        n
        −
        1
      
    
    {\displaystyle n-1}
  
 Damen auf einem 
  
    
      
        n
        ×
        (
        n
        −
        1
        )
      
    
    {\displaystyle n\times (n-1)}
  
-Brett auf jeden Fall eine Lösung mit 
  
    
      
        n
        −
        2
      
    
    {\displaystyle n-2}
  
 Damen auf einem 
  
    
      
        n
        ×
        (
        n
        −
        2
        )
      
    
    {\displaystyle n\times (n-2)}
  
-Brett enthalten muss.
In anderen Worten, wenn man die untere (oder obere) Reihe der Teillösung eines 
  
    
      
        n
        ×
        (
        n
        −
        1
        )
      
    
    {\displaystyle n\times (n-1)}
  
-Bretts entfernt, bleiben 
  
    
      
        n
        −
        2
      
    
    {\displaystyle n-2}
  
 Damen auf einem 
  
    
      
        n
        ×
        (
        n
        −
        2
        )
      
    
    {\displaystyle n\times (n-2)}
  
-Brett übrig, die wiederum eine Teillösung auf dem 
  
    
      
        n
        ×
        (
        n
        −
        2
        )
      
    
    {\displaystyle n\times (n-2)}
  
-Brett darstellen.
Der Algorithmus konstruiert also alle Lösungen aus den Lösungen eines jeweils kleineren Brettes.
Da sichergestellt wird, dass die Teillösungen auf den kleinen Brettern konfliktfrei sind, spart dieser Algorithmus das Überprüfen vieler Stellungen. Insgesamt werden für das 
  
    
      
        8
        ×
        8
      
    
    {\displaystyle 8\times 8}
  
-Brett nur 
  
    
      
        15.720
      
    
    {\displaystyle 15.720}
  
 Stellungen überprüft.

Durch die Verwendung einer Koroutine kann der Algorithmus etwas vereinfacht werden. Das folgende Programm ist eine Übersetzung der Lösung von Niklaus Wirth in die Programmiersprache Python, verzichtet jedoch auf die im Original verwendete Indexarithmetik und verwendet stattdessen einfache Listen. An die Stelle der Prozedur tritt hier ein Generator: eine spezielle Form einer Koroutine, durch die ein Iterator erzeugt wird. Dadurch werden beide Fassungen des Originals zur Berechnung einer Lösung bzw. aller Lösungen zusammengefasst.


### Constraintprogrammierung
Die Constraintprogrammierung über endliche Bereiche kann eine Aufgabe wie das Damenproblem sehr kompakt formulieren.
Das folgende Prolog-Programm (in GNU Prolog) findet schnell eine Lösung auch für große Schachbretter.


### Explizite Lösung
Eine Konstruktionsvorschrift für eine spezielle Lösung mit beliebig großem n wurde erstmals 1874 von Emil Pauls angegeben. Hierdurch wurde also insbesondere bewiesen, dass das Damenproblem für beliebiges 
  
    
      
        n
        >
        3
      
    
    {\displaystyle n>3}
  
 mindestens eine Lösung besitzt.
Für gerade 
  
    
      
        n
      
    
    {\displaystyle n}
  
, die bei Division mit 
  
    
      
        6
      
    
    {\displaystyle 6}
  
 den Rest 
  
    
      
        0
      
    
    {\displaystyle 0}
  
 oder 
  
    
      
        4
      
    
    {\displaystyle 4}
  
 ergeben, starte man in der zweiten Spalte der obersten Zeile und platziere eine Dame. Platziere die folgenden Damen jeweils zwei Spalten rechts und eine Zeile unter der vorigen, bis 
  
    
      
        
          
            
              n
              2
            
          
        
      
    
    {\displaystyle \textstyle {\frac {n}{2}}}
  
 Zeilen gefüllt sind. Die Zeilen der unteren Bretthälfte erhält man aus der Spiegelung der oberen Damen am Mittelpunkt des Bretts.
Für gerade 
  
    
      
        n
      
    
    {\displaystyle n}
  
, die bei Division mit 
  
    
      
        6
      
    
    {\displaystyle 6}
  
 den Rest 
  
    
      
        2
      
    
    {\displaystyle 2}
  
 ergeben (darunter das normale Schachbrett mit 
  
    
      
        n
        =
        8
      
    
    {\displaystyle n=8}
  
) führt diese Vorschrift nicht zu einer gültigen Lösung. Für diesen Fall lässt sich eine alternative, etwas komplizierte Konstruktionsvorschrift angeben.


### Andere Methoden
Ein iterativer Reparaturalgorithmus beginnt mit einer beliebigen Stellung der Damen auf dem Brett. Es zählt dann die Anzahl der Konflikte, und versucht, durch Umpositionieren der Damen die Anzahl der Konflikte zu reduzieren. Effizient ist etwa, die Dame mit den meisten Konflikten senkrecht auf die Position zu verschieben, auf der die geringste Anzahl von Konflikten auftritt. Mit dieser Methode kann das 
  
    
      
        1.000.000
      
    
    {\displaystyle 1.000.000}
  
-Damen-Problem ausgehend von einer „vernünftigen“ Versuchsposition gelöst werden. Derart große Bretter lassen sich mit expliziten Konstruktionsalgorithmen nicht lösen (triviale Lösungen ausgenommen); allerdings kann ein solcher Iterationsalgorithmus nicht mit Sicherheit eine Lösung finden.


## Verwandte Problemstellungen
### Andere Figuren
Das Problem kann auch für andere Schachfiguren (König, Läufer, Springer, Turm) formuliert werden.
Eine weitere Verallgemeinerung des Problems stellt das 
  
    
      
        n
      
    
    {\displaystyle n}
  
-Superdamen-Problem dar. Superdamen dürfen wie Damen und Springer ziehen. Es ist nicht klar, wer Superdamen oder das 
  
    
      
        n
      
    
    {\displaystyle n}
  
-Superdamen-Problem erfunden hat. In Mathematische Knobeleien (Vieweg-Verlag, 1973) erwähnt Martin Gardner eine Schachvariation, in der mit einer Superdame gespielt wird. Gardner nennt diese Figur dort Maharadscha. Andere kennen sie als Amazone.
Auch die Frage, auf wie viele Arten sich 
  
    
      
        n
      
    
    {\displaystyle n}
  
 Superdamen auf einem 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
-Schachbrett bedrohungsfrei platzieren lassen, wurde untersucht:

Seit 2001 existiert auch für das 
  
    
      
        n
      
    
    {\displaystyle n}
  
-Superdamen-Problem eine explizite Lösung von Frank Schwellinger.
Angemerkt sei, dass das Springerproblem nicht die analoge Aufgabe für Springer ist, sondern eine Springerwanderung über das ganze Schachbrett.


### Andere Brettgeometrie
George Pólya betrachtete das Damenproblem auf einem torusförmigen Brett. Er bewies, dass genau dann mindestens eine Lösung existiert, wenn 
  
    
      
        n
      
    
    {\displaystyle n}
  
 zu 
  
    
      
        6
      
    
    {\displaystyle 6}
  
 teilerfremd ist, also weder durch 
  
    
      
        2
      
    
    {\displaystyle 2}
  
 noch durch 
  
    
      
        3
      
    
    {\displaystyle 3}
  
 teilbar ist. Es gibt darüber hinaus auch Untersuchungen zu dreidimensionalen und vierdimensionalen Verallgemeinerungen sowie zu nicht-quadratischen Schachbrettern, wie sie beim Dreierschach, Sechseck-Schach oder Hex-Spiel verwendet werden.


### Andere Aufgabenstellungen
Für ein 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
-Schachbrett bestimme man die Dominanzzahl, das ist die Mindestzahl an Damen, die ausreicht, jedes Feld des Brettes zu beherrschen. Auf dem 
  
    
      
        8
        ×
        8
      
    
    {\displaystyle 8\times 8}
  
-Brett reichen fünf Damen aus. Dafür gibt es 
  
    
      
        4.860
      
    
    {\displaystyle 4.860}
  
 Lösungen (etwa b7, d5, e4, f3, h1).
Das Neun-Damen-Problem verlangt, auf einem 
  
    
      
        8
        ×
        8
      
    
    {\displaystyle 8\times 8}
  
-Brett neun Damen und einen Bauern derart unterzubringen, dass die Damen einander nicht beobachten können, also keine direkte waagerechte, senkrechte oder diagonale Sichtlinie zueinander haben. Dieses Problem kann wiederum auf beliebige Brettgröße und eine höhere Anzahl von Bauern verallgemeinert werden.
Das Problem 
  
    
      
        n
      
    
    {\displaystyle n}
  
-Damen-Vervollständigung fragt, ob es für ein 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
-Brett, auf dem schon einige Damen stehen möglich ist, das Damenproblem durch Hinzufügen von Damen zu lösen. Dieses Problem ist NP- und #P-vollständig.


## Siehe auch
Schachkomposition
Springerproblem


## Literatur
John J. Watkins: Across the Board: The Mathematics of Chess Problems. Princeton University Press, Princeton 2004, ISBN 0-691-11503-6.


## Weblinks
Eric W. Weisstein: Queens Problem. MathWorld (englisch)
Walter Kosters: n-Queens bibliography. Universität Leiden (Literaturliste, englisch)
Das 8-Damen-Problem. Berechnung der Lösungen für verschiedene Brettgrößen in JavaScript auf ArsTechnica.de
Problema de las 1000 reinas, solución particular: Método general 8, n reinas. Implementierung in Java (spanisch)
Jeff Somers N-Queen-Quellcode. (englisch; sehr gut beschrieben)
Takakens N-Queen-Quellcode. (englisch; ca. 4-mal schneller als Jeff Somers Code)
N-queens problem. Lösungen in mehr als 100 verschiedenen Programmiersprachen auf Rosetta Code (englisch)


## Einzelnachweise