Das acht Königin-Rätsel ist das Problem, acht Schachköniginnen auf 8×8 Schachbrett zu legen, so dass keine zwei Königinnen einander angreifen. So verlangt eine Lösung, dass keine zwei Königinnen dieselbe Reihe, Säule oder Diagonale teilen. Das acht Königin-Rätsel ist ein Beispiel des allgemeineren N-Königin-Problems', n Königinnen auf einem n×n Schachbrett zu legen, wo Lösungen für alle natürlichen Zahlen n mit Ausnahme von 2 und 3 bestehen.

Geschichte

Das Rätsel wurde 1848 vom Schachspieler Max Bezzel, und im Laufe der Jahre ursprünglich vorgeschlagen, viele Mathematiker, einschließlich Gauss, haben an diesem Rätsel und seinem verallgemeinerten N-Königin-Problem gearbeitet. Die ersten Lösungen wurden von Franz Nauck 1850 zur Verfügung gestellt. Nauck hat auch das Rätsel zum N-Königin-Problem (auf einem n×n Ausschuss — ein Schachbrett der willkürlichen Größe) erweitert. 1874 hat S. Günther eine Methode vorgeschlagen, Lösungen zu finden, indem er Determinanten verwendet hat, und J.W.L. Glaisher hat diese Annäherung raffiniert.

Edsger Dijkstra hat dieses Problem 1972 verwendet, um die Macht dessen zu illustrieren, was er strukturierte Programmierung genannt hat. Er hat eine hoch detaillierte Beschreibung der Entwicklung einer Tiefe veröffentlicht, die zuerst Algorithmus denselben Weg zurückverfolgt.

Das Konstruieren einer Lösung

Das Problem kann ganz rechenbetont teuer sein, wie es 4,426,165,368 gibt (d. h., 64 wählen 8) mögliche Maßnahmen von acht Königinnen auf 8×8 Ausschuss, aber nur 92 Lösungen. Es ist möglich, Abkürzungen zu verwenden, die rechenbetonte Voraussetzungen oder Faustregeln reduzieren, der rohe Gewalt rechenbetonte Techniken vermeidet. Zum Beispiel, gerade durch die Verwendung einer einfachen Regel, die jede Königin zu einer Einzelspalte (oder Reihe) zwingt, obwohl noch überlegte rohe Gewalt, es möglich ist, die Anzahl von Möglichkeiten zu gerade 16,777,216 zu vermindern (d. h. 8) mögliche Kombinationen. Das Erzeugen der Versetzungen, die Lösungen des acht Saatkrähe-Rätsels sind und dann für diagonale Angriffe weiter überprüfend, reduziert die Möglichkeiten auf gerade 40,320 (d. h. 8!). Der folgende Pythonschlange-Code verwendet diese Technik, um die 92 Lösungen zu berechnen:

von itertools importieren Versetzungen

n = 8

Gebirgspässe = Reihe (n)

für vec in Versetzungen (Gebirgspässe):

wenn (n == len (Satz (vec [ich] + ich weil ich in Gebirgspässen))

== len (Satz (vec [ich] - ich weil ich in Gebirgspässen))):

drucken Sie vec </Quelle>

Diese Algorithmen der rohen Gewalt sind für n = 8 rechenbetont lenksam, aber würden für Probleme von n  20, als 20 unnachgiebig sein! = 2.433 * 10. Förderungen dafür und andere Spielzeugprobleme sind die Entwicklung und Anwendung der Heuristik (Faustregeln), dass Ertrag-Lösungen der n Königinnen an einem kleinen Bruchteil der rechenbetonten Voraussetzungen verwirrt sind.

Das heuristisch löst N Königinnen für jeden N  4. Es bildet die Liste von Zahlen für vertikale Positionen (Reihen) von Königinnen mit der horizontalen Position (Säule), die einfach zunimmt. N ist 8 für acht Königin-Rätsel.

1. Wenn der Rest davon, N durch 6 zu teilen, nicht 2 oder 3 dann ist, ist die Liste einfach alle geraden Zahlen, die von allen ungeraden Zahlen  N gefolgt sind
2. Schreiben Sie sonst getrennte Listen von geraden und ungeraden Zahlen (d. h. 2,4,6,8 - 1,3,5,7)
3. Wenn der Rest 2, Tausch 1 und 3 in der sonderbaren Liste und Bewegung 5 zum Ende (d. h. 3,1,7,5) ist
4. Wenn der Rest 3 ist, bewegen Sie sich 2 zum Ende sogar der Liste und 1,3 zum Ende der sonderbaren Liste (d. h. 4,6,8,2 - 5,7,9,1,3)
5. Hängen Sie sonderbare Liste an sogar Liste an und legen Sie Königinnen in die Reihen, die durch diese Zahlen, vom linken bis Recht (d. h. a2, b4, c6, d8, e3, f1, g7, h5) gegeben sind

Für N = 8 läuft das auf die Lösung hinaus, die oben gezeigt ist. Noch einige Beispiele folgen.

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

Lösungen des acht Königin-Rätsels

Das acht Königin-Rätsel hat 92 verschiedene Lösungen. Wenn Lösungen, die sich nur durch Symmetrie-Operationen (Folgen und Nachdenken) des Ausschusses unterscheiden, als ein aufgezählt werden, hat das Rätsel 12 einzigartige (oder grundsätzlich) Lösungen.

Eine grundsätzliche Lösung hat gewöhnlich acht Varianten (einschließlich seiner ursprünglichen Form) erhalten durch das Drehen 90, 180, oder 270 Grade und dann das Reflektieren von jeder der vier Rotationsvarianten in einem Spiegel in einer festen Position. Jedoch soll eine Lösung, zu seiner eigenen 90 Grad-Folge gleichwertig sein (wie es mit einer Lösung mit fünf Königinnen auf 5x5 Ausschuss geschieht), dass grundsätzliche Lösung nur zwei Varianten haben wird. Wenn eine Lösung zu seiner eigenen 180 Grad-Folge gleichwertig ist, wird sie vier Varianten haben. Der 12 grundsätzlichen Lösungen des Problems mit acht Königinnen auf 8x8 Ausschuss genau ist man seiner eigenen 180 Grad-Folge gleich, und niemand ist ihrer 90 Grad-Folge gleich. So ist die Zahl von verschiedenen Lösungen 11*8 + 1*4 = 92.

Die einzigartigen Lösungen werden unten präsentiert:

</td>

</td></td></td>

</tr>

</td></td></td></td></tr></td></td></td></td></tr>

</Tisch>

Ausführliche Lösungen

Ausführliche Lösungen bestehen, um n Königinnen auf einem n × n Ausschuss zu legen, keine kombinatorische Suche überhaupt verlangend.

Die ausführlichen Lösungen stellen Stufe-gegangene Muster, als in den folgenden Beispielen für n = 8, 9 und 10 aus:

</td></td></td></tr></Tisch>

Das Aufzählen von Lösungen

Der folgende Tisch gibt die Zahl von Lösungen, um n Königinnen auf einem n × n Ausschuss, sowohl einzigartig als auch verschieden, für n=1-14, 24-26 zu legen.

Bemerken Sie, dass die sechs Königinnen verwirrt sind, hat weniger Lösungen als das fünf Königin-Rätsel.

Es gibt zurzeit keine bekannte Formel für die genaue Zahl von Lösungen.

Zusammenhängende Probleme

Das Verwenden von Stücken außer Königinnen

:On 8×8 wohnen man kann 32 Ritter, oder 14 Bischöfe, 16 Könige oder acht Saatkrähen legen, so dass keine zwei Stücke einander angreifen. Gegen feenhafte Schachfiguren ist auch Königinnen ausgewechselt worden. Im Fall von Rittern ist eine leichte Lösung, ein auf jedem Quadrat einer gegebenen Farbe zu legen, da sie sich nur zur entgegengesetzten Farbe bewegen.

Reihe von Costas

:In-Mathematik, eine Reihe von Costas kann geometrisch als eine Reihe von N-Punkten betrachtet werden, die auf den Quadraten eines nxn Schachbrettes, solch liegt, dass jede Reihe oder Säule nur einen Punkt enthalten, und dass alle n (n  1)/2 Versetzungsvektoren zwischen jedem Paar von Punkten verschieden sind. So ist eine Ordnung-n Reihe von Costas eine Lösung eines N-Saatkrähe-Rätsels.

Sonderausschüsse

:P ólya hat das n Königin-Problem auf einem toroidal Ausschuss ("in der Form von des Berliners") studiert und hat gezeigt, dass es eine Lösung auf einem n×n Ausschuss gibt, wenn, und nur wenn n durch 2 oder 3 nicht teilbar ist. 2009 haben Pearson und Pearson algorithmisch dreidimensionale Ausschüsse (n×n×n) mit n Königinnen bevölkert und haben vorgeschlagen, dass Vielfachen von diesen Lösungen für eine vierdimensionale Version des Rätsels nachgeben können.

Überlegenheit

:Given ein n×n Ausschuss, die Überlegenheitszahl ist die minimale Zahl von Königinnen (oder andere Stücke) musste angreifen oder jedes Quadrat besetzen. Für n=8 ist die Überlegenheitszahl der Königin 5.

Neun Königin-Problem

:Place neun Königinnen und ein Pfand auf 8×8 Ausschuss auf solche Art und Weise, dass Königinnen einander nicht angreifen. Die weitere Generalisation des Problems (ist vollständige Lösung zurzeit unbekannt): In Anbetracht eines n×n Schachbrettes und m> n Königinnen, finden Sie die minimale Zahl von Pfändern, so dass die M Königinnen und die Pfänder auf dem Ausschuss auf solche Art und Weise aufgestellt werden kann, dass keine zwei Königinnen einander angreifen.

Königinnen und Ritter-Problem

:Place-M Königinnen und M Ritter auf einem n×n Ausschuss, so dass kein Stück einen anderen angreift.

Magische Quadrate

: 1992 haben Demirörs, Rafraf und Tanik eine Methode veröffentlicht, um einige magische Quadrate in n Königin-Lösungen, und umgekehrt umzuwandeln.

Lateinische Quadrate

: In einer n×n Matrix, legen Sie jede Ziffer 1 durch n in n Positionen in der Matrix, so dass keine zwei Beispiele derselben Ziffer in derselben Reihe oder Säule sind.

Genauer Deckel

: Denken Sie eine Matrix mit einer primärer Säule für jede der n Reihen des Ausschusses, einer primärer Säule für jede der n Dateien und einer sekundärer Säule für jede der 4n-6 nichttrivialen Diagonalen des Ausschusses. Die Matrix hat n Reihen: Ein für jedes mögliche Königin-Stellen und jede Reihe hat 1 in den Säulen entsprechend der Reihe dieses Quadrats, Datei, und Diagonalen und 0 in allen anderen Säulen. Dann ist das n Königin-Problem zur Auswahl einer Teilmenge der Reihen dieser solcher Matrix gleichwertig, dass jede primäre Säule 1 in genau einer der gewählten Reihen hat und jede sekundäre Säule 1 in am grössten Teil von einen der gewählten Reihen hat; das ist ein Beispiel eines verallgemeinerten genauen Deckel-Problems, dessen sudoku ein anderes Beispiel ist.

Die acht Königinnen sind als eine Übung im Algorithmus-Design verwirrt

Die Entdeckung aller Lösungen des acht Königin-Rätsels ist ein gutes Beispiel eines einfachen, aber nichttrivialen Problems. Deshalb wird es häufig als ein Beispiel-Problem für verschiedene Programmiertechniken, einschließlich nicht traditioneller Annäherungen wie Einschränkungsprogrammierung, Logikprogrammierung oder genetische Algorithmen verwendet. Meistenteils wird es als ein Beispiel eines Problems verwendet, das mit einem rekursiven Algorithmus, durch die Phrasierung des n Königin-Problems induktiv gelöst werden kann, in Bezug auf eine einzelne Königin zu jeder Lösung des Problems hinzuzufügen, n&minus;1 Königinnen auf einem n-by-n Schachbrett zu legen. Die Induktion hat mit der Lösung des 'Problems' die Talsohle durchschritten, 0 Königinnen auf 0 durch 0 Schachbrett zu legen, das das leere Schachbrett ist.

Diese Technik ist viel effizienter als der naive Suchalgorithmus der rohen Gewalt, der alle 64 = 2 = 281,474,976,710,656 mögliche blinde Stellen von acht Königinnen denkt, und dann diese filtert, um alle Stellen zu entfernen, die zwei Königinnen irgendein auf demselben Quadrat legen (das Verlassen von nur 64!/56! = 178,462,987,637,760 mögliche Stellen) oder im gegenseitigen Angreifen von Positionen. Dieser sehr schlechte Algorithmus wird unter anderem dieselben Ergebnisse immer wieder in allen verschiedenen Versetzungen der Anweisungen der acht Königinnen, sowie dem Wiederholen derselben Berechnung immer wieder für die verschiedenen Teilmengen jeder Lösung erzeugen. Ein besserer Algorithmus der rohen Gewalt legt eine einzelne Königin auf jeder Reihe, zu nur 8 = 2 = 16,777,216 blinde Stellen führend.

Es ist möglich, viel besser zu tun, als das.

Ein Algorithmus löst das acht Saatkrähe-Rätsel durch das Erzeugen der Versetzungen der Nummern 1 bis 8 (von denen es 8 gibt! = 40,320), und Gebrauch die Elemente jeder Versetzung als Indizes, um eine Königin auf jeder Reihe zu legen.

Dann weist es jene Ausschüsse mit diagonalen Angreifen-Positionen zurück.

Das denselben Weg zurückverfolgende Tiefensuche-Programm, eine geringe Verbesserung auf der Versetzungsmethode, baut den Suchbaum durch das Betrachten einer Reihe des Ausschusses auf einmal, das Beseitigen der meisten Nichtlösungsvorstandspositionen in einer sehr frühen Bühne in ihrem Aufbau.

Weil es Saatkrähe und diagonale Angriffe sogar auf unvollständige Ausschüsse zurückweist, untersucht es nur 15,720 mögliche Königin-Stellen.

Eine weitere Verbesserung, die nur 5,508 mögliche Königin untersucht

Stellen sollen sich verbinden die Versetzung hat Methode mit dem frühen gestützt

Beschneidung der Methode: Die Versetzungen sind erzeugte Tiefe zuerst und

der Suchraum wird beschnitten, wenn die teilweise Versetzung einen erzeugt

diagonaler Angriff.

Einschränkungsprogrammierung kann auch auf diesem Problem sehr wirksam sein.

Eine Alternative zur erschöpfenden Suche ist eine 'wiederholende Reparatur' Algorithmus, der normalerweise mit allen Königinnen auf dem Ausschuss zum Beispiel mit einer Königin pro Säule anfängt. Es zählt dann die Zahl von Konflikten (Angriffe) auf, und verwendet einen heuristischen, um zu bestimmen, wie man das Stellen der Königinnen verbessert. Die 'minimalen Konflikte' heuristisch - das Bewegen des Stückes mit der größten Zahl von Konflikten zum Quadrat in derselben Säule, wo die Zahl von Konflikten am kleinsten ist - sind besonders wirksam: Es findet eine Lösung des 1,000,000 Königin-Problems in weniger als 50 Schritten durchschnittlich. Das nimmt an, dass die anfängliche Konfiguration 'vernünftig gut' ist - wenn eine Million Königinnen der ganze Anfang in derselben Reihe, sie offensichtlich mindestens 999,999 Schritte machen wird, um es zu befestigen. Ein 'vernünftig guter' Startpunkt kann zum Beispiel durch das Stellen jeder Königin in seiner eigenen Reihe und Säule gefunden werden, so dass es die kleinste Zahl von Königinnen bereits auf dem Ausschuss kollidiert.

Bemerken Sie, dass 'wiederholende Reparatur', verschieden von der 'denselben Weg zurückverfolgenden' Suche, die oben entworfen ist, keine Lösung versichert: Wie das ganze Hügelbergsteigen (d. h., gierig) Verfahren, kann es auf einem lokalen Optimum stecken bleiben (in welchem Fall der Algorithmus mit einer verschiedenen anfänglichen Konfiguration wiederangefangen werden kann). Andererseits kann es Problem-Größen lösen, die mehrere Größenordnungen außer dem Spielraum einer Tiefensuche sind.

Eine belebte Version der rekursiven Lösung

Dieser Zeichentrickfilm Gebrauch, der denselben Weg zurückverfolgt, um das Problem zu beheben. Eine Königin wird in eine Säule gelegt, die, wie man bekannt, Konflikt nicht verursacht. Wenn eine Säule nicht gefunden wird, dass das Programm zum letzten guten Staat zurückkehrt und dann eine verschiedene Säule versucht.

Beispielprogramm

Der folgende ist ein Programm von Pascal durch Niklaus Wirth. Es findet eine Lösung des acht Königin-Problems.

var i: ganze Zahl; q: boolean;

a: Reihe [1.. 8] boolean;

b: Reihe [2.. 16] boolean;

c: Reihe [-7.. 7] boolean;

x: Reihe [1.. 8] der ganzen Zahl;

Verfahren-Versuch (ich: ganze Zahl; var q: boolean);

var j: ganze Zahl;

beginnen Sie j: = 0;

wiederholen Sie j: = j + 1; q: = falsch;

wenn [j] und b [ich + j] und c [ich - j] dann

beginnen Sie x [ich]: = j;

[j]: = falsch; b [ich + j]: = falsch; c [ich - j]: = falsch;

wenn ich

Siehe auch

• Mathematisches Spiel
• Mathematisches Rätsel
• Keine drei im Linienproblem
• Saatkrähe-Polynom
• Glocke, der Jordan und Stevens, Brett, Ein Überblick über bekannte Ergebnisse und Forschungsgebiete für N-Königinnen, Getrennte Mathematik, Vol. 309, Ausgabe 1, am 6. Januar 2009, 1-31.
• Watkins, John J. (2004). Durch die Bank: Die Mathematik von Schachproblemen. Princeton: Universität von Princeton Presse. Internationale Standardbuchnummer 0-691-11503-6.
• O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Strukturierte Programmierung, Akademische Presse, London, 1972 internationale Standardbuchnummer 0-12-200550-3 sehen Seiten 72-82 für die Lösung von Dijkstra des 8 Königin-Problems.
• Dreidimensionale NxN-Königin-Probleme, L.Allison, C.N.Yee, & M.McGaughey (1988), Abteilung der Informatik, Monash Universität, Australien.
• S. Nudelman, Das ModulN-Königin-Problem in Höheren Dimensionen, Getrennter Mathematik, vol 146, iss. 1-3, am 15. November 1995, Seiten 159-167.
• Auf Dem ModulN-Königin-Problem in Höheren Dimensionen, Ricardo Gomez, Juan Jose Montellano und Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Äußeres, Ciudad Universitaria, Mexiko.
• J. Barr und S. Rao, Das N-Königin-Problem in Höheren Dimensionen, Elemente der Mathematik, vol 61 (2006), Seiten 133-137.

Links

• "LEITEN SIE AB": Ein Zwei-Spieler-Spiel, das auf Acht Königin-Problem an "sadtoy.com" gestützt ist
• Eine Vergegenwärtigung von N-Königin-Lösungsalgorithmen durch Yuval Baror
• Ein Applet das Simulieren der zufällig-gierigen Lösung für das N-Königin-Problem
• Artikel MathWorld
• Lösungen des 8-Königinnen-Problems
• Die N-Königin-Seite von Walter Kosters
• Die N-Königin-Seite von Durango Bill
• Online-Handbuch zur Einschränkung, programmierend
• NQueen@home planen Boinc
• Ideen und Algorithmen für das N-Königin-Problem
• Queens@TUD Projekt (hat Gebrauch solvers FPGA-basiert)
• Acht Königin-Rätsel: Blitz-Spiel
• Acht Königin-Rätsel: iPhone kostenloses Spiel
• Fünf Königin-Rätsel: Kostenloses Spiel
• JQuery-Version von den Acht Königinnen Puzzle
• Acht Königin-Rätsel: Kostenloses Androide-Spiel

Verbindungen zu Lösungen

• Schema-Lösung, die im Schema mit dem amb Maschinenbediener geschrieben ist.
• Einfache Lösung und Lay-Out 8 Königin und für die Matrix von NxN
• Der N-Königin-Code von Takaken (ungefähr 4mal schneller als der Code von Jeff Somer wegen Symmetrie-Rücksichten)
• Die N-Königin von Jeff Somers codiert
• Algorithmen von Usefull, für das N-Königin-Problem zu beheben
• C ++ Durchführung des 8-Königinnen-Problems alle Versetzungen
• Finden Sie Ihre eigene Lösung
• Atari GRUNDLEGENDER
• Atari Handlung!
• Genetische Algorithmen
• Haskell/Java Hybride
• Java, Spiegel, löst durch das Zurückverfolgen, Code unter GPL.
• Pythonschlange
• Mit Versetzungen (Pythonschlange)
• Standard ML
• Folgen der ganzen Zahl

• Die 8 Königin-Lösung von Quirkasaurus
• LISPELN-Lösung für das N-Königin-Problem
• ANSI C (rekursive, NxN-Größe-Königinnen ohne Kongruenzen Problem solver mit der Konfliktheuristik)

• Javascript-Lösung für das 8-Königinnen-Problem
• Die Lösung der rohen Gewalt für acht Königinnen in einem Web hat interaktive klassische GRUNDLEGENDE Umgebung gestützt
• Lösung für acht Königinnen in C ++
• Die Konfliktheuristik-Lösung für die acht Königinnen in einem Web hat interaktive klassische GRUNDLEGENDE Umgebung gestützt
• Eine einfache PHP Lösung
• Ein Tisch der algorithmisch ersten N-Königin-Lösungen: für n=4 zu n=45, n=47 und n=49 (durch Pearson), und für n=46 (durch Engelhardt). Die algorithmisch erste Lösung für n=48 bleibt unbekannter
• Seheinleitung: N-Königin-Rätsel (wiki)
• Lösungen auf verschiedenen Sprachen auf dem Code von Rosetta
• N-Königinnen in X10
• Eine Übersicht von Miranda, einschließlich der 4-Linien-Lösung von Miranda (Benachrichtigungen von SigPlan, 21 (12):158-166, Dez 1986)
• Eine Fallstudie: Die Acht Königinnen Puzzle, einschließlich Lösungen auf vielfachen Sprachen
• ANS-hervor mit dem Zurückverfolgen Nichtrekursive Lösung (demonstriert, wie Hervor Funktionen variable Zahlen von Rahmen auf dem Stapel nehmen können). Außerdem hat eine Durchführung des heuristischen Algorithmus früher in diesem Artikel Wikipedia beschrieben (demonstriert verbundene Listen).
• N-Königinnen in Java