Acht-Damen-Puzzle

	A	B	C	D	e	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	e	F	G	H

Die einzige symmetrische Lösung des Acht-Damen-Problems ( bis auf Drehung und Spiegelung )

Das Acht-Damen-Problem besteht darin, acht Schachdamen so auf einem 8×8-Schachbrett zu platzieren , dass keine zwei Damen einander bedrohen. Eine Lösung erfordert also, dass keine zwei Damen in derselben Zeile, Spalte oder Diagonale stehen. Es gibt 92 Lösungen. Das Problem wurde erstmals Mitte des 19. Jahrhunderts formuliert. In der heutigen Zeit dient es häufig als Beispielproblem für verschiedene Programmiertechniken .

Das Acht-Damen-Problem ist ein Spezialfall des allgemeineren n- Damen-Problems , bei dem n nicht angreifende Damen auf einem n × n- Schachbrett platziert werden müssen . Lösungen existieren für alle natürlichen Zahlen n außer n = 2 und n = 3. Obwohl die genaue Anzahl der Lösungen nur für n ≤ 27 bekannt ist , beträgt die asymptotische Wachstumsrate der Lösungsanzahl ungefähr . ${\displaystyle (0.143n)^{n}}$

Der Schachkomponist Max Bezzel veröffentlichte das Acht-Damen-Puzzle im Jahr 1848. Franz Nauck veröffentlichte die ersten Lösungen im Jahr 1850. ^{[ 1 ]} Nauck erweiterte das Puzzle auch zum n- Damen-Problem, bei dem sich n Damen auf einem Schachbrett mit n × n Feldern befinden.

Seitdem haben sich viele Mathematiker , darunter Carl Friedrich Gauß , sowohl mit dem Acht-Damen-Problem als auch mit seiner verallgemeinerten n -Damen-Variante beschäftigt . 1874 schlug S. Günther eine Methode zur Lösung mithilfe von Determinanten vor. ^{[ 1 ]} J. W. L. Glaisher verfeinerte Günthers Ansatz.

1972 nutzte Edsger Dijkstra dieses Problem, um die Leistungsfähigkeit dessen zu veranschaulichen, was er strukturierte Programmierung nannte . Er veröffentlichte eine sehr detaillierte Beschreibung eines Tiefensuche- Backtracking-Algorithmus . ^{[ 2 ]}

Die Suche nach allen Lösungen des Acht-Damen-Problems kann sehr rechenaufwändig sein, da es 4.426.165.368 mögliche Anordnungen von acht Damen auf einem 8×8-Brett gibt, ^{[ a ]} aber nur 92 Lösungen. Es ist möglich, Abkürzungen zu verwenden, die den Rechenaufwand reduzieren, oder Faustregeln, die Brute-Force-Verfahren vermeiden . Beispielsweise kann man durch die einfache Regel, aus jeder Spalte eine Dame auszuwählen, die Anzahl der Möglichkeiten auf 16.777.216 (8 × ⁸ ) mögliche Kombinationen reduzieren. Durch die Generierung von Permutationen reduziert sich die Anzahl der Möglichkeiten weiter auf nur noch 40.320 ( 8! ), die dann auf diagonale Angriffe überprüft werden können.

Das Acht-Damen-Puzzle hat 92 verschiedene Lösungen. Zählt man Lösungen, die sich nur durch die Symmetrieoperationen Drehung und Spiegelung des Bretts unterscheiden, als eine, so bleiben 12 Lösungen übrig. Diese werden als Fundamentallösungen bezeichnet ; Beispiele für jede Lösung sind unten aufgeführt.

Eine Fundamentallösung besitzt üblicherweise acht Varianten (einschließlich ihrer ursprünglichen Form), die durch Drehung um 90°, 180° oder 270° und anschließende Spiegelung jeder der vier Rotationsvarianten an einem Spiegel in fester Position gewonnen werden. Eine der zwölf Fundamentallösungen (Lösung 12 unten) ist jedoch identisch mit ihrer eigenen 180°-Drehung und besitzt daher nur vier Varianten (die Lösung selbst und ihre Spiegelung, ihre 90°-Drehung und deren Spiegelung). ^{[ b ]} Somit beträgt die Gesamtzahl der verschiedenen Lösungen 11 × 8 + 1 × 4 = 92.

Alle fundamentalen Lösungen werden im Folgenden dargestellt:

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 1

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 2

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 3

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 4

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 5

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 6

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 7

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 8

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 9

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 10

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 11

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Lösung 12

Lösung 10 hat die zusätzliche Eigenschaft, dass keine drei Damen in einer geraden Linie stehen .

Brute-Force-Algorithmen zur Bestimmung der Anzahl der Lösungen sind für Probleme der Größenordnung 20! rechentechnisch machbar , wären aber für Probleme der Größenordnung 20! = 2,433 × 10¹⁸ nicht durchführbar ^. Wenn das Ziel darin besteht, eine einzige Lösung zu finden, lässt sich zeigen, dass für alle n ≥ 4 Lösungen ohne jegliche Suche existieren. ^{[ 3 ] [ 4 ]} Diese Lösungen weisen treppenförmige Muster auf, wie in den folgenden Beispielen für n = 8, 9 und 10: ${\displaystyle n=8}$${\displaystyle n\geq 20}$

A B C D e F G H 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H Treppenlösung für 8 Queensize-Betten

A B C D e F G H ich 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H ich Treppenlösung für 9 Queensize-Betten

A B C D e F G H ich J 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D e F G H ich J Treppenlösung für 10 Queensize-Betten

Die obigen Beispiele lassen sich mit den folgenden Formeln herleiten. ^{[ 3 ]} Sei ( i , j ) das Quadrat in Spalte i und Zeile j auf dem n × n Schachbrett, k eine ganze Zahl.

Ein Ansatz ^{[ 3 ]} ist

1. Wenn der Rest bei der Division von n durch 6 nicht 2 oder 3 ist, dann besteht die Liste einfach aus allen geraden Zahlen, gefolgt von allen ungeraden Zahlen, die nicht größer als n sind .
2. Andernfalls schreibe separate Listen für gerade und ungerade Zahlen (2, 4, 6, 8 – 1, 3, 5, 7).
3. Ist der Rest 2, vertausche 1 und 3 in der ungeraden Liste und verschiebe 5 ans Ende ( 3, 1 , 7, 5 ).
4. Ist der Rest 3, verschiebe 2 an das Ende der geraden Liste und 1,3 an das Ende der ungeraden Liste (4, 6, 8, 2 – 5, 7, 9, 1, 3 ).
5. Füge die ungerade Liste der geraden Liste hinzu und platziere die Damen in den durch diese Zahlen angegebenen Reihen von links nach rechts (a2, b4, c6, d8, e3, f1, g7, h5).

Für n  = 8 ergibt sich daraus die oben genannte Fundamentallösung 1. Es folgen einige weitere Beispiele.

• 14 Damen (Rest 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
• 15 Damen (Rest 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
• 20 Damen (Rest 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

Es gibt keine bekannte Formel für die genaue Anzahl der Lösungen zur Platzierung von n Damen auf einem n × n- Brett, d. h. für die Anzahl der unabhängigen Mengen der Größe n in einem n × n -Damengraphen . Das 27 × 27-Brett ist das Brett höchster Ordnung, dessen Lösungen vollständig erfasst wurden. ^{[ 5 ]} Die folgenden Tabellen geben die Anzahl der Lösungen des n -Damen-Problems an , sowohl die fundamentalen (Folge A002562 in der OEIS ) als auch alle (Folge A000170 in der OEIS ), für alle bekannten Fälle.

Die Anzahl der Stellungen, bei denen zudem keine drei Damen auf einer geraden Linie liegen, ist bekannt für (Folge A365437 in der OEIS ). ${\displaystyle n\leq 25}$

Im Jahr 2021 bewies Michael Simkin, dass für große Zahlen n die Anzahl der Lösungen des n- Damen-Problems ungefähr gleich ist . ^{[ 6 ]} Genauer gesagt, wächst die Anzahl der Lösungen asymptotisch mit , wobei eine Konstante zwischen 1,939 und 1,945 ist. ^{[ 7 ]} (Hierbei steht o (1) für die Notation „kleines o“ .) ${\displaystyle (0.143n)^{n}}$${\displaystyle {\mathcal {Q}}(n)}$$${\displaystyle {\mathcal {Q}}(n)=((1\pm o(1))ne^{-\alpha })^{n}}$$${\displaystyle \alpha }$

Betrachtet man stattdessen ein toroidales Schachbrett (bei dem die Diagonalen von der oberen Kante zur unteren und von der linken Kante zur rechten verlaufen), so ist es nur dann möglich, n Damen auf einem Brett zu platzieren, wenn … In diesem Fall beträgt die asymptotische Anzahl der Lösungen ^{[ 8 ] [ 9 ].}${\displaystyle n\times n}$${\displaystyle n\equiv 1,5\mod 6.}$$${\displaystyle T(n)=((1+o(1))ne^{-3})^{n}.}$$

Höhere Dimensionen

Bestimmen Sie die Anzahl der nicht angreifenden Damen, die in einem d- dimensionalen Schachfeld der Größe n platziert werden können . In einigen höheren Dimensionen können mehr als n Damen platziert werden (das kleinste Beispiel sind vier nicht angreifende Damen in einem 3×3×3-Schachfeld), und es ist bekannt, dass es für jedes k höhere Dimensionen gibt, in denen n^{^k} Damen nicht ausreichen, um alle Felder anzugreifen. ^{[ 10 ] [ 11 ]}

Verwendung anderer Figuren als Damen

Auf einem 8×8-Brett lassen sich 32 Springer , 14 Läufer , 16 Könige oder 8 Türme so platzieren, dass keine zwei Figuren einander angreifen. Bei den Springern bietet es sich an, auf jedem Feld einer Farbe einen Springer zu platzieren, da diese nur auf Felder der anderen Farbe ziehen. Die Lösung ist für Türme und Könige ebenfalls einfach. Sechzehn Könige können auf dem Brett platziert werden, indem man es in 2×2-Felder unterteilt und die Könige auf jedem Feld an gleichwertigen Positionen platziert. Die Platzierung von n Türmen auf einem n × n- Brett entspricht direkt Permutationsmatrizen der Ordnung n .

Schachvarianten

Ähnliche Probleme lassen sich auch für Schachvarianten wie Shogi stellen . Beispielsweise geht es beim n + k Drachenkönige-Problem darum, k Shogi-Bauern und n + k sich gegenseitig nicht angreifende Drachenkönige auf einem n × n Shogi-Brett zu platzieren. ^{[ 12 ]}

Nicht standardmäßige Platinen

Pólya untersuchte das n -Damen-Problem auf einem toroidförmigen („donutförmigen“) Brett und zeigte, dass es genau dann eine Lösung auf einem n × n Brett gibt, wenn n nicht durch 2 oder 3 teilbar ist. ^{[ 13 ]}

Herrschaft

Bei einem n × n- Brett ist die Dominanzzahl die minimale Anzahl an Damen (oder anderen Figuren), die benötigt werden, um jedes Feld anzugreifen oder zu besetzen. Für n = 8 beträgt die Dominanzzahl der Dame 5. ^{[ 14 ] [ 15 ]}

Königinnen und andere Stücke

Varianten umfassen das Mischen von Damen mit anderen Figuren; beispielsweise das Platzieren von m Damen und m Springern auf einem n × n- Brett, sodass keine Figur eine andere angreift ^{[ 16 ]} , oder das Platzieren von Damen und Bauern, sodass keine zwei Damen einander angreifen. ^{[ 17 ]}

Magische Quadrate

1992 veröffentlichten Demirörs, Rafraf und Tanik eine Methode zur Umwandlung einiger magischer Quadrate in n -Damen-Lösungen und umgekehrt. ^{[ 18 ]}

Lateinische Quadrate

Bei einer n × n Matrix werden die Ziffern 1 bis n an n Positionen in der Matrix so platziert, dass keine zwei Vorkommen derselben Ziffer in derselben Zeile oder Spalte stehen.

Exakte Abdeckung

Betrachten wir eine Matrix mit einer Hauptspalte für jeden der n Ränge des Schachbretts, einer Hauptspalte für jede der n Linien und einer Nebenspalte für jede der 4n − 6 nichttrivialen Diagonalen. Die Matrix hat n² ^Zeilen : eine für jede mögliche Position einer Dame. Jede Zeile enthält in den Spalten, die dem Rang, der Linie und den Diagonalen des jeweiligen Feldes entsprechen, eine 1 und in allen anderen Spalten eine 0. Das n- Damen-Problem ist dann äquivalent zur Auswahl einer Teilmenge der Zeilen dieser Matrix, sodass jede Hauptspalte in genau einer der ausgewählten Zeilen eine 1 enthält und jede Nebenspalte in höchstens einer der ausgewählten Zeilen eine 1 enthält. Dies ist ein Beispiel für ein verallgemeinertes exaktes Überdeckungsproblem , zu dem auch Sudoku gehört.

n -Damen-Vervollständigung

Das Vervollständigungsproblem fragt, ob es auf einem n × n- Schachbrett, auf dem bereits einige Damen platziert sind, möglich ist, in jeder verbleibenden Reihe eine Dame so zu platzieren, dass keine zwei Damen einander angreifen. Dieses und verwandte Probleme sind NP-vollständig und #P-vollständig . ^{[ 19 ]} Jede Platzierung von höchstens n /60 Damen kann vervollständigt werden, während es Teilkonfigurationen von etwa n /4 Damen gibt, die nicht vervollständigt werden können. ^{[ 20 ]}

Costas-Arrays

Ein Costas-Array ohne angreifende Damen (NAQCA) ist ein Costas-Array, das gleichzeitig eine Lösung des n- Damen-Problems darstellt. Das einzige bekannte NAQCA ist der triviale 1×1-Fall, und es wird vermutet, dass keine weiteren existieren. ^{[ 21 ]}

Die Lösung des Acht-Damen-Problems ist ein gutes Beispiel für ein einfaches, aber dennoch anspruchsvolles Problem. Daher dient es häufig als Beispielproblem für verschiedene Programmiertechniken, darunter auch unkonventionelle Ansätze wie Constraint-Programmierung , logische Programmierung oder genetische Algorithmen . Meistens wird es als Beispiel für ein Problem verwendet, das sich mit einem rekursiven Algorithmus lösen lässt , indem man das n- Damen-Problem induktiv so formuliert, dass man zu jeder Lösung des Problems, n − 1 Damen auf einem n × n- Schachbrett zu platzieren, eine einzelne Dame hinzufügt. Die Induktion endet mit der Lösung des „Problems“, 0 Damen auf dem Schachbrett zu platzieren – also dem leeren Schachbrett. Dieser Prozess lässt sich effizienter gestalten, indem man die Beobachtung nutzt, dass jede Spalte des Schachbretts genau eine Dame enthalten muss, und die Positionen, an denen der Algorithmus versucht, die i -te Dame in die i -te Zeile des Schachbretts einzufügen, auf Spalten beschränkt, die noch nicht von anderen Damen besetzt sind. Diese Entscheidungen reduzieren die Anzahl der zu testenden Platzierungen erheblich, sodass der Algorithmus alle Lösungen auf einem Schachbrett in so kurzer Zeit finden kann, dass es fast wie eine Momentaufnahme erscheint. ^{[ 22 ]}${\displaystyle 8\times 8}$

Eine Alternative zur vollständigen Suche ist der iterative Reparaturalgorithmus, der typischerweise mit allen Damen auf dem Brett beginnt, beispielsweise mit einer Dame pro Spalte. ^{[ 23 ]} Anschließend zählt er die Anzahl der Konflikte (Angriffe) und verwendet eine Heuristik, um die Platzierung der Damen zu optimieren. Die Heuristik der minimalen Konflikte – die Figur mit den meisten Konflikten auf das Feld in derselben Spalte zu bewegen, in der die Anzahl der Konflikte am geringsten ist – ist besonders effektiv: Sie findet selbst für das Problem mit 1.000.000 Damen problemlos eine Lösung. ^{[ 24 ] [ 25 ]}

Anders als die oben beschriebene Backtracking-Suche garantiert die iterative Reparatur keine Lösung: Wie alle Greedy -Verfahren kann sie in einem lokalen Optimum stecken bleiben. (In diesem Fall kann der Algorithmus mit einer anderen Anfangskonfiguration neu gestartet werden.) Andererseits kann sie Problemgrößen lösen, die um mehrere Größenordnungen über den Rahmen einer Tiefensuche hinausgehen.

Alternativ zum Backtracking können Lösungen durch rekursives Aufzählen gültiger Teillösungen, Zeile für Zeile, gezählt werden. Anstatt ganze Spielfeldpositionen zu konstruieren, werden blockierte Diagonalen und Spalten mithilfe bitweiser Operationen verfolgt. Dies erlaubt keine Wiederherstellung einzelner Lösungen. ^{[ 26 ] [ 27 ]}

Das folgende Programm ist eine Übersetzung von Niklaus Wirths Lösung in die Programmiersprache Python . Es verzichtet jedoch auf die Indexarithmetik des Originals und verwendet stattdessen Listen , um den Programmcode so einfach wie möglich zu halten. Mithilfe einer Koroutine in Form einer Generatorfunktion lassen sich beide Versionen des Originals vereinheitlichen, um entweder eine oder alle Lösungen zu berechnen. Es werden lediglich 15.720 mögliche Damenplatzierungen untersucht. ^{[ 28 ] [ 29 ]}

def queens ( n : int , i : int , a : list , b : list , c : list ): if i < n : for j in range ( n ): if j not in a and i + j not in b and i - j not in c : yield from queens ( n , i + 1 , a + [ j ], b + [ i + j ], c + [ i - j ]) else : yield afor solution in queens ( 8 , 0 , [], [], []): print ( solution )

Das folgende Programm ist eine Implementierung von Donald Knuths informeller Beschreibung der Lösung auf Seite 31, Abschnitt 7.2.2 Backtrack-Programmierung aus The Art of Computer Programming , Band 4B, in die Programmiersprache Python. ^{[ 30 ]}

def property ( perm : list ) -> bool : for k in range ( 0 , len ( perm )): for j in range ( 0 , len ( perm )): if j < k : if perm [ k ] == perm [ j ]: return False elif abs ( perm [ k ] - perm [ j ]) == k - j : return False return Truedef extend ( perm : list , n : int ): new_perm = [ ] for p in perm : for i in range ( 0 , n ): new_perm.append ( p + [ i ] ) return new_permdef n_queens ( n : int ) -> int : domain = list ( range ( 0 , n )) perm = [[]] for i in range ( n ): new_perm = list ( filter ( property , extend ( perm , n ))) perm = new_perm return len ( perm )

• Im Spiel „Der 7. Gast “ ist das achte Rätsel, „Das Dilemma der Königin“, im Spielzimmer der Villa Stauf das eigentliche Acht-Damen-Rätsel. ^{[ 31 ] : 48–49, 289–290}
• Im Spiel Professor Layton und das geheimnisvolle Dorf ist das 130. Rätsel: „Too Many Queens 5“ (クイーンの問題 5 ) ein Rätsel mit acht Königinnen. ^{[ 32 ]}

• Costas-Array
• Mathematisches Spiel
• Mathematisches Rätsel
• Kein Problem mit drei in einer Reihe
• Turmpolynom

• Bell, Jordan; Stevens, Brett (2009). „Ein Überblick über bekannte Ergebnisse und Forschungsgebiete für n -Damen“ . Discrete Mathematics . 309 (1): 1–31 . doi : 10.1016/j.disc.2007.12.043 .
• Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems . Princeton: Princeton University Press. ISBN 978-0-691-11503-0Die
• Allison, L.; Yee, CN; McGaughey, M. (1988). „Dreidimensionale NxN-Damenprobleme“ . Fachbereich Informatik, Monash University, Australien.
• Nudelman, S. (1995). „Das modulare N-Damen-Problem in höheren Dimensionen“ . Discrete Mathematics . 146 ( 1–3 ): 159–167 . doi : 10.1016/0012-365X(94)00161-5 .
• Engelhardt, M. (August 2010). „Der Stammbaum der Lösungen des Damenproblems“ . Spektrum der Wissenschaft : 68–71 .
• On The Modular N-Queen Problem in Higher Dimensions , Ricardo Gomez, Juan Jose Montellano und Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexiko.
• Budd, Timothy (2002). „Eine Fallstudie: Das Acht-Damen-Rätsel“ (PDF) . Einführung in die objektorientierte Programmierung (3. Aufl.). Addison Wesley Longman. S.  125–145 . ISBN 0-201-76031-2Die
• Wirth, Niklaus (2004) [aktualisiert 2012]. „Das Acht-Damen-Problem“. Algorithmen und Datenstrukturen (PDF) . Oberon-Version mit Korrekturen und autorisierten Änderungen. S.  114–118 .

• Weisstein, Eric W. „Das Damenproblem“ . MathWorld .
• queens-cpm auf GitHub: Acht-Damen-Puzzle in Turbo Pascal für CP/M
• eight-queens.py auf GitHub: Lösung des Acht-Damen-Rätsels in einer Zeile in Python
• Lösungen in mehr als 100 verschiedenen Programmiersprachen (auf Rosetta Code )