Acht Queens Puzzle

a b c d e f g h
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
 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 für das acht Queens -Puzzle (bis zu Rotation und Reflexion)

Das Acht Queens Puzzle ist das Problem, acht zu platzieren Schach Königinnen auf einem 8 × 8 Schachbrett so dass sich keine zwei Königinnen drohen; Eine Lösung erfordert daher, dass keine zwei Königinnen dieselbe Zeile, Spalte oder Diagonale teilen. Es gibt 92 Lösungen. Das Problem wurde erstmals Mitte des 19. Jahrhunderts dargestellt. In der modernen Zeit wird es oft als Beispielproblem für verschiedene verwendet Computerprogrammierung Techniken.

Das acht Queens -Puzzle ist ein Sonderfall des allgemeinen Falles n Queens Problem von Platzierung n nicht angreifende Königinnen auf einem n×n Schachbrett. Lösungen existieren für alle natürliche Zahlen n mit Ausnahme von n = 2 und n = 3. Obwohl die genaue Anzahl der Lösungen nur für bekannt ist n ≤ 27, die Asymptotische Wachstumsrate der Anzahl der Lösungen ist (0,143 n)n.

Geschichte

Schachkomponist Max Bezzel veröffentlichte 1848 das Puzzle mit acht Queens. Franz Nauck veröffentlichte 1850 die ersten Lösungen.[1] Nauck erweiterte das Rätsel auch auf die n Queens Problem mit n Königinnen auf einem Schachbrett von n×n Quadrate.

Seitdem viele Mathematiker, einschließlich Carl Friedrich Gauß, haben sowohl an dem acht Queens -Puzzle als auch verallgemeinert gearbeitet n-Quens Version. Im Jahr 1874 schlug S. Gunther eine Methode mit Verwendung vor Determinanten Lösungen finden.[1] J.W.L. Glaisher raffinierter Gunthers Ansatz.

1972,, Edsger Dijkstra benutzte dieses Problem, um die Kraft dessen zu veranschaulichen, was er nannte Strukturierte Programmierung. Er veröffentlichte eine sehr detaillierte Beschreibung von a Tiefe-First Backtracking -Algorithmus.[2]

Lösungen aufbauen und zählen, wenn n = 8

Das Problem, alle Lösungen für das 8-Queens-Problem zu finden, kann ziemlich rechnerisch teuer sein, da es 4.426.165.368 mögliche Arrangements von acht Königinnen auf einem 8 × 8-Board gibt.[a] aber nur 92 Lösungen. Es ist möglich, Verknüpfungen zu verwenden, die die Rechenanforderungen oder Faustregeln reduzieren, die vermieden werden Brute-Force-Computertechniken. Wenn Sie beispielsweise eine einfache Regel anwenden, die eine Königin aus jeder Spalte auswählt, ist es möglich, die Anzahl der Möglichkeiten auf 16.777.216 zu reduzieren (dh 88) mögliche Kombinationen. Erstellen Permutationen reduziert die Möglichkeiten weiter auf nur 40.320 (dh,, 8!), die dann auf diagonale Angriffe überprüft werden kann.

Das acht Queens -Puzzle hat 92 unterschiedliche Lösungen. Wenn Lösungen, die sich nur durch die unterscheiden Symmetrie Der Betrieb der Rotation und Reflexion des Boards wird als eins gezählt, das Puzzle hat 12 Lösungen. Diese nennt man grundlegend Lösungen; Vertreter von jedem sind unten gezeigt.

Eine grundlegende Lösung hat normalerweise acht Varianten (einschließlich ihrer ursprünglichen Form), die durch Drehen von 90, 180 oder 270 ° erhalten wurden und dann jede der vier Rotationsvarianten in einem Spiegel in einer festen Position reflektiert werden. Eine der 12 grundlegenden Lösungen (Lösung 12 unten) ist jedoch identisch mit ihrer eigenen 180 ° -Wrehung, so dass nur vier Varianten (sich selbst und ihre Reflexion, seine 90 ° -Drotation und die Reflexion davon).[b] Solche Lösungen haben nur zwei Varianten (selbst und ihre Reflexion). Somit beträgt die Gesamtzahl der unterschiedlichen Lösungen 11 × 8 + 1 × 4 = 92.

Alle grundlegenden Lösungen werden nachstehend dargestellt:

Lösung 10 hat die zusätzliche Eigenschaft, die Keine drei Königinnen sind in einer geraden Linie. Die Lösungen 1 und 8 haben eine 4-Queen-Linie.

Existenz von Lösungen

Brute-Force n= 8, wäre aber für Probleme von unerbittlich n≥ 20wie 20! = 2,433 × 1018. Wenn das Ziel darin besteht, eine einzige Lösung zu finden, kann man Lösungen für alle zeigen n ≥ 4 ohne jegliche Suche.[3][4] Diese Lösungen weisen wie in den folgenden Beispielen für Treppen- n = 8, 9 und 10:

Die obigen Beispiele können mit den folgenden Formeln erhalten werden.[3] Lassen (i, j) Sei das Quadrat in der Säule i und Reihe j auf der n × n Schachbrett, k eine Ganzzahl.

Ein Konzept[3] ist

  1. Wenn der Rest vom Teilen n Mit 6 ist nicht 2 oder 3, dann ist die Liste einfach alle gleichmäßigen Zahlen, gefolgt von allen ungeraden Zahlen, die nicht größer als n.
  2. Ansonsten schreiben Sie separate Listen mit geraden und ungeraden Zahlen (2, 4, 6, 8 - 1, 3, 5, 7).
  3. Wenn der Rest 2 ist, tauschen Sie 1 und 3 in eine ungerade Liste aus und verschieben Sie sich 5 bis zum Ende (3, 1, 7,, 5).
  4. Wenn der Rest 3 ist, bewegen Sie sich 2 auf die gleiche Liste und 1,3 bis zum Ende der ungeraden Liste (4, 6, 8, 2 - 5, 7, 1, 3).
  5. Gehen Sie die ungerade Liste an die gerade Liste an und platzieren Sie Queens in die von diesen Zahlen angegebenen Zeilen von links nach rechts (A2, B4, C6, D8, E3, F1, G7, H5).

Zum n= 8 Dies führt zu einer grundlegenden Lösung 1 oben. Es folgen ein paar weitere Beispiele.

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

Lösungen für andere Größen zählen n

Exakte Aufzählung

Es ist keine Formel für die genaue Anzahl von Lösungen für das Platzieren bekannt n Königinnen auf einem n × n Board d. H. Die Anzahl der Anzahl von unabhängige Sets von Größe n in einem (n n × n Grafik der Königin. Das 27 × 27-Board ist das Board mit höchster Ordnung, das vollständig aufgezählt wurde.[5] Die folgenden Tabellen geben die Anzahl der Lösungen an die n Queens Problem, beide grundlegend (Sequenz A002562 in dem Oeis) und alles (Sequenz A000170 in dem Oeis) für alle bekannten Fälle.

n grundlegend alle
1 1 1
2 0 0
3 0 0
4 1 2
5 2 10
6 1 4
7 6 40
8 12 92
9 46 352
10 92 724
11 341 2.680
12 1.787 14.200
13 9.233 73.712
14 45.752 365.596
15 285.053 2.279.184
16 1.846.955 14.772.512
17 11.977.939 95.815,104
18 83,263,591 666.090.624
19 621.012.754 4,968.057.848
20 4,878.666.808 39.029.188.884
21 39.333.324.973 314.666.222.712
22 336.376.244.042 2.691,008.701.644
23 3.029.242.658.210 24.233.937.684.440
24 28.439.272.956.934 227.514.171.973.736
25 275.986.683.743.434 2,207,893.435.808.352
26 2.789.712.466.510.289 22.317.699.616.364.044
27 29.363.495.934.315.694 234.907.967.154.122.528

Asymptotische Aufzählung

Im Jahr 2021 hat Michael Simkin das für große Zahlen bewiesen ndie Anzahl der Lösungen der n Das Queens -Problem ist ungefähr .[6] Genauer gesagt die Zahl von Lösungen hat Asymptotisches Wachstum

wo ist eine Konstante, die zwischen 1,939 und 1,945 liegt.[7] (Hier o(1) repräsentiert Little O Notation.))

Wenn man stattdessen a betrachtet Toroidal Schachbrett (wo Diagonale von der Oberkante nach unten und von der linken Kante nach rechts "umwickeln") ist es nur möglich, platziert zu werden n Königinnen auf einem Vorstand, wenn In diesem Fall ist die asymptotische Anzahl von Lösungen[8][9]

Verwandte Probleme

Höhere Dimensionen
Finden Sie die Anzahl der nicht angreifenden Königinnen, die in a platziert werden können d-Dimensionales Schach Platz von Größe n. Mehr als n Königinnen können in einigen höheren Abmessungen platziert werden (das kleinste Beispiel sind vier nicht angreifende Königinnen in einem 3 × 3 × 3-Schachraum), und es ist tatsächlich bekannt, dass für jeden kEs gibt höhere Dimensionen, wo nk Königinnen reichen nicht aus, um alle Räume anzugreifen.[10][11]
Verwenden anderer Stücke als Königinnen
Auf einem 8 × 8 -Board kann man 32 platzieren Ritter, oder 14 Bischöfe, 16 Könige oder acht Trümmer, so dass sich keine zwei Teile angreifen. Märchenschachstücke wurden auch für Königinnen ersetzt. Bei Rittern besteht eine einfache Lösung darin, eine auf jedes Quadrat einer bestimmten Farbe zu platzieren, da sie sich nur in die entgegengesetzte Farbe bewegen. Die Lösung ist auch für Rooks und Könige einfach. Acht Rooks können entlang einer langen Diagonale (unter Tausenden anderer Lösungen) platziert werden, und 16 Könige werden auf der Tafel platziert, indem sie in 2 mal 2 Quadrate unterteilt und die Könige auf den gleichwertigen Punkten auf jedem Platz platziert werden.
Schachvariationen
Verwandte Probleme können gefragt werden Schachvariationen wie zum Beispiel Shogi. Zum Beispiel die n+k Dragon Kings Problem bittet sich zu platzieren k Shogi Bauern und n+k gegenseitig nicht angegriffen Drachenkönige auf an n×n Shogi -Vorstand.[12]
Permutationsmatrix
In der Mathematik kann eine Permutationsmatrix geometrisch als Satz von angesehen werden n Punkte, die auf den Quadraten von a liegen n×n Schachbrett, so dass jede Zeile oder Spalte nur einen Punkt enthält. So eine Bestellung-n Permutationsmatrix ist eine Lösung für eine n-Rooks Puzzle.
Nicht standardmäßige Boards
Pólya studierte die n Queens Problem auf a Toroidal ("Donut-förmiges") Board und zeigte, dass es eine Lösung auf einem gibt n×n Board, wenn und nur wenn n ist nicht durch 2 oder 3 teilbar.[13] 2009 pearson und pearson algorithmisch besiedelte dreidimensionale Boards (n×n×n) mit n2 Queens und schlugen vor, dass Multiples davon Lösungen für eine vierdimensionale Version des Puzzles ergeben können.[14]
Herrschaft
Gegeben an n×n Vorstand, die Herrschaftsnummer Ist die Mindestanzahl von Königinnen (oder anderen Teilen), die für jeden Quadrat angreifen oder besetzt werden müssen. Zum n = 8 Die Herrschaftsnummer der Königin beträgt 5.[15][16]
Königinnen und andere Stücke
Zu den Varianten gehören das Mischen von Queens mit anderen Teilen; Zum Beispiel platzieren m Königinnen und m Ritter auf einem n×n Board, damit kein Stück einen anderen angreift[17] Oder platzieren Sie Queens und Bauern, damit sich keine zwei Königinnen angreifen.[18]
Magische Quadrate
Im Jahr 1992 veröffentlichten Demirörs, Rafraf und Tanik eine Methode, um einige magische Quadrate in die Konvertierung zu n-Quens Lösungen und umgekehrt.[19]
Lateinische Quadrate
In einem (n n×n Matrix, jede Ziffer 1 durchsetzen n in n Stellen in der Matrix so, dass sich keine zwei Instanzen derselben Ziffer in derselben Zeile oder Spalte befinden.
Genaue Abdeckung
Betrachten Sie eine Matrix mit einer primären Spalte für jedes der der n Ränge der Platine, eine primäre Spalte für jedes der der n Dateien und eine sekundäre Spalte für jedes der 4n - 6 Nichttriviale Diagonale des Boards. Die Matrix hat n2 Zeilen: Eine für jede mögliche Platzierung der Königin, und jede Zeile hat eine 1 in den Spalten, die dem Rang, der Datei und der Diagonalen dieses Quadrats entsprechen, und in allen anderen Spalten eine 0. Dann ist die n Das Problem mit Queens entspricht der Auswahl einer Teilmenge der Zeilen dieser Matrix, so dass jede Primärspalte eine 1 in genau einer der ausgewählten Zeilen hat und jede sekundäre Spalte eine 1 in höchstens einer der ausgewählten Reihen hat; Dies ist ein Beispiel für ein verallgemeinertes genaue Abdeckung Problem, von denen Sudoku ist ein weiteres Beispiel.
n-Quens Abschluss
Eine Zeitung von 2017[20] untersuchte das Problem "angesichts einer n×n Schachbrett, auf der einige Königinnen bereits platziert sind, können Sie eine Königin in jeder verbleibenden Reihe platzieren, damit sich keine zwei Königinnen angreifen? "Und mehrere verwandte Probleme. Die Autoren behaupteten, dass diese Probleme seien NP-Complete[21] und #P-Complete.

Übung im Algorithmus -Design

Es ist ein gutes Beispiel für ein einfaches, aber nicht triviales Problem, alle Lösungen für das acht Queens -Puzzle zu finden. Aus diesem Grund wird es häufig als Beispielproblem für verschiedene Programmierungstechniken verwendet, einschließlich nicht -traditioneller Ansätze wie z. Einschränkungsprogrammierung, Logikprogrammierung oder genetische Algorythmen. Meistens wird es als Beispiel für ein Problem verwendet, das mit a gelöst werden kann rekursiv Algorithmusdurch Formulierung der n Queens Problem induktiv im Hinblick auf das Hinzufügen einer einzelnen Königin zu einer Lösung für das Problem der Platzierung n–1 Queens auf einem n×n Schachbrett. Das Induktion Beilagen mit der Lösung für das 'Problem', 0 Queens auf das Schachbrett zu platzieren, das leere Schachbrett.

Diese Technik kann so eingesetzt werden, dass es viel effizienter ist als die Naive Brute-Force-Suche Algorithmus, der alle 64 berücksichtigt8= 248= 281.474.976.710.656 mögliche blinde Platzierungen von acht Queens und filtern diese dann, um alle Platzierungen zu entfernen, die zwei Queens entweder auf demselben Platz (nur 64!/56! Dieser sehr schlechte Algorithmus wird unter anderem in all den verschiedenen immer wieder die gleichen Ergebnisse erzielen Permutationen von den Zuordnungen der acht Königinnen sowie wiederholten die gleichen Berechnungen immer wieder für die verschiedenen Untersätze jeder Lösung. Ein besserer Brute-Force-Algorithmus platziert eine einzelne Königin in jeder Reihe, was zu nur 8 führt8= 224= 16.777.216 Blindplatzierungen.

Es ist möglich, viel besser zu machen. Ein Algorithmus löst die acht Trümmer Rätsel durch Erzeugung der Permutationen der Zahlen 1 bis 8 (von denen es 8! = 40.320 gibt) und verwendet die Elemente jeder Permutation als Indizes, um eine Königin in jeder Reihe zu platzieren. Dann lehnt es diese Boards mit diagonalen Angriffspositionen ab.

Diese Animation zeigt Backtracking um das Problem zu lösen. Eine Königin wird in eine Säule platziert, von der bekannt ist, dass sie keinen Konflikt verursacht. Wenn eine Spalte nicht gefunden wird, kehrt das Programm in den letzten guten Zustand zurück und versucht dann eine andere Spalte.

Das Backtracking Tiefe-First-Suche Programm, eine leichte Verbesserung der Permutationsmethode, konstruiert die Suchbaum Durch die Berücksichtigung einer Reihe des Boards gleichzeitig die meisten Nichtlösungspositionen in einem sehr frühen Stadium ihrer Bauarbeiten. Da es auch in unvollständigen Boards Rook- und diagonale Angriffe ablehnt, untersucht es nur 15.720 mögliche Platzierungen für Königin. Eine weitere Verbesserung, die nur 5.508 mögliche Platzierungen für Königin untersucht, besteht darin, die permutationsbasierte Methode mit der frühen Beschneidungsmethode zu kombinieren: Die Permutationen werden Tiefe erzeugt und der Suchraum wird beschnitten, wenn der teilweise Permutation erzeugt einen diagonalen Angriff.Einschränkungsprogrammierung kann auch bei diesem Problem sehr effektiv sein.

Min-Konflikte Lösung für 8 Königinnen

Eine Alternative zur erschöpfenden Suche ist ein "iterativer Reparaturalgorithmus", der normalerweise mit allen Queens auf dem Brett beginnt, beispielsweise mit einer Königin pro Spalte.[22] Anschließend zählt die Anzahl der Konflikte (Angriffe) und verwendet eine Heuristik, um zu bestimmen, wie die Platzierung der Königinnen verbessert werden kann. Das 'Minimumkonflikte' Heuristik - Das Stück mit der größten Anzahl von Konflikten auf dem Platz in derselben Spalte zu bewegen, in der die Anzahl der Konflikte kleinsten ist - ist besonders effektiv: Es findet eine Lösung für das 1000.000 -Königin -Problem in weniger als 50 Schritten im Durchschnitt. Dies setzt voraus, dass die anfängliche Konfiguration "einigermaßen gut" ist - wenn eine Million Königinnen in derselben Zeile beginnen, dauert sie mindestens 999.999 Schritte, um sie zu beheben. Ein "einigermaßen guter" Ausgangspunkt kann zum Beispiel gefunden werden, indem jede Königin in ihre eigene Reihe und Spalte steckt, so dass er mit der kleinsten Anzahl von Königinnen in Konflikt steht.

Im Gegensatz zur oben beschriebenen Backtracking -Suche garantiert die iterative Reparatur keine Lösung: Wie alle gierig Verfahren, es kann auf einem lokalen Optimum hängen bleiben. (In einem solchen Fall kann der Algorithmus mit einer anderen anfänglichen Konfiguration neu gestartet werden.) Andererseits kann er Problemgrößen lösen, die mehrere Größenordnungen über den Umfang einer Tiefen-First-Suche liegen.

Als Alternative zum Backtracking können Lösungen durch rekursives Aufzählen von gültigen Teillösungen und einer Zeile nacheinander gezählt werden. Anstatt ganze Boardpositionen zu konstruieren, werden blockierte Diagonalen und Säulen mit bitgewieller Operationen verfolgt. Dies erlaubt nicht die Wiederherstellung einzelner Lösungen.[23][24]

Beispielprogramm

Das folgende Programm ist eine Übersetzung von Niklaus WirthLösung in die Python Programmiersprache, aber ohne die Indexarithmetik im Original gefunden und verwendet stattdessen Listen um den Programmcode so einfach wie möglich zu halten. Durch Verwendung a Coroutine in Form von a GeneratorfunktionBeide Versionen des Originals können einheitlich sein, um entweder eine oder alle Lösungen zu berechnen. Es werden nur 15.720 mögliche Platzierungen der Königin untersucht.[25][26] 

def Königinnen(n, i, a, b, c):  wenn i < n:  zum j in Angebot(n):  wenn j nicht in a und i+j nicht in b und i-j nicht in c:  Ausbeute von Königinnen(n, i+1, a+[j], b+[i+j], c+[i-j]))  anders:  Ertrag a zum Lösung in Königinnen(8, 0, [],, [],, []):  drucken(Lösung)

In der Populärkultur

Siehe auch

Anmerkungen

  1. ^ Die Anzahl der Kombinationen von 8 Quadraten von 64 ist das Binomialkoeffizient 64C8.
  2. ^ Andere Symmetrien sind für andere Werte von möglich n. Zum Beispiel gibt es eine Platzierung von fünf nicht angegriffenen Königinnen auf einer 5 × 5 -Platine, die mit seiner eigenen 90 ° -Drotation identisch ist. Wenn n > 1, es ist nicht möglich, dass eine Lösung gleich ihrer eigenen Reflexion ist, da zwei Königinnen sich gegenseitig gegenübersehen müssen.

Verweise

  1. ^ a b W. W. Rouse Ball (1960) "The acht Queens Problem", in Mathematische Erholungen und Essays, Macmillan, New York, S. 165–171.
  2. ^ O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Strukturierte Programmierung, Academic Press, London, 1972 ISBN0-12-200550-3, S. 72–82.
  3. ^ a b c Bo Bernhardsson (1991). "Explizite Lösungen für das N-Queens-Problem für alle n". Sigart Bull. 2 (2): 7. doi:10.1145/122319.122322. S2CID 10644706.
  4. ^ E. J. Hoffman et al., "Konstruktion für die Lösungen des Problems des M Queens". Mathematikmagazin, Vol. XX (1969), S. 66–72. [1]
  5. ^ Das Q27 -Projekt
  6. ^ Sloman, Leila (21. September 2021). "Mathematiker beantwortet Schachprobleme über das Angriff von Queens". Quantenmagazin. Abgerufen 22. September 2021.
  7. ^ Simkin, Michael (28. Juli 2021). "Die Anzahl der $ n $ -Quens-Konfigurationen". Arxiv:2107.13460v2 [math.co].
  8. ^ Luria, Zur (15. Mai 2017). "Neue Grenzen für die Anzahl der N-Queens-Konfigurationen". Arxiv:1705.05225v2 [math.co].
  9. ^ Bowtell, Candida; Keevash, Peter (16. September 2021). "Das $ n $ -Quens-Problem". Arxiv:2109.08083v1 [math.co].
  10. ^ J. Barr und S. Rao (2006), Das N-Queens-Problem in höheren Dimensionen, Elemente der Mathematik, Band 61 (4), S. 133–137.
  11. ^ Martin S. Pearson. "Königinnen auf einem Schachbrett - jenseits der 2. Dimension" (PHP). Abgerufen 27. Januar 2020.
  12. ^ Chatham, Doug (1. Dezember 2018). "Reflexionen über das Problem der N +K Dragon Kings". Mathematikmagazin für Freizeitmathematik. 5 (10): 39–55. doi:10.2478/rmm-2018-0007.
  13. ^ G. Pólya, Uber Die "Doppelt-periodische" Losungen des N-Damen-Problems, George Pólya: Sammelte Papiere Vol. IV, G-C. Rota, Hrsg., MIT Press, Cambridge, London, 1984, S. 237–247
  14. ^ "Königinnen auf einem Schachbrett - jenseits der 2. Dimension".
  15. ^ Burger, A. P.; Cockayne, E. J.; Mynhardt, C. M. (1997), "Herrschaft und Irredundanz in der Grafik der Queens", Diskrete Mathematik, 163 (1–3): 47–66, doi:10.1016/0012-365X (95) 00327-s, HDL:1828/2670, HERR 1428557
  16. ^ Weakley, William D. (2018), "Queens auf der ganzen Welt in fünfundzwanzig Jahren", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (Hrsg.), Graphentheorie: Lieblingsprobleme und offene Probleme - 2, Problembücher in Mathematik, Cham: Springer, S. 43–54, doi:10.1007/978-3-319-97686-0_5, HERR 3889146
  17. ^ "Problem mit Königinnen und Rittern". Archiviert von das Original am 16. Oktober 2005. Abgerufen 20. September 2005.
  18. ^ Neun Queens Problem
  19. ^ O. Demirörs, N. Rafraf und M.M. Tanik. Erhalten von N-Queens-Lösungen aus magischen Quadraten und Konstruktion von magischen Quadräten aus N-Queens-Lösungen. Journal of Recreational Mathematics, 24: 272–280, 1992
  20. ^ Gent, Ian P.; Jefferson, Christopher; Nightingale, Peter (August 2017). "Komplexität von n-Quens Abschluss ". Journal of Artificial Intelligence Research. 59: 815–848. doi:10.1613/jair.5512. ISSN 1076-9757. Abgerufen 7. September 2017.
  21. ^ "Das 8-Queens-Puzzle". www.claymath.org. Clay Mathematics Institute. 2. September 2017.
  22. ^ Ein Polynomzeitalgorithmus für das N-Queen-Problem Von Rok Sosic und Jun Gu, 1990. beschreibt die Laufzeit für bis zu 500.000 Queens, was die maximale Ausführung von Speicherbeschränkungen war.
  23. ^ Qiu, Zongyan (Februar 2002). "Bit-Vektor-Codierung von N-Queen-Problem". ACM Sigplan nennt. 37 (2): 68–70. doi:10.1145/568600.568613.
  24. ^ Richards, Martin (1997). Backtracking -Algorithmen in MCPL unter Verwendung von Bitmustern und Rekursion (PDF) (Technischer Bericht). Computerlabor der Universität von Cambridge. UCAM-CL-TR-433.
  25. ^ Wirth, Niklaus (1976). Algorithmen + Datenstrukturen = Programme. Prentice-Hall-Serie in automatischer Berechnung. Prentice-Hall. Bibcode:1976Adsp.book ..... w. ISBN 978-0-13-022418-7. p. 145
  26. ^ Wirth, Niklaus (2012) [Orig. 2004]. "Das acht Queens -Problem". Algorithmen und Datenstrukturen (PDF). Oberon -Version mit Korrekturen und autorisierten Modifikationen. S. 114–118.
  27. ^ DeMaria, Rusel (15. November 1993). Der 7. Gast: Der offizielle Strategieführer (PDF). Prima -Spiele. ISBN 978-1-5595-8468-5. Abgerufen 22. April 2021.
  28. ^ "ナゾ 130 クイーン の 問題 5". ゲーム の 匠 (auf Japanisch). Abgerufen 17. September 2021.

Weitere Lektüre

Externe Links