N-Queens Problem .. Wie weit können wir gehen?
Des N-Damen-Problem:
Dieses problem besagt, dass, gegeben ein Schachbrett der Größe N durch N ist, finden die verschiedenen Permutationen, in der N Damen auf dem Brett platziert werden, ohne dass ein bedrohen sich gegenseitig.
Meine Frage ist:
Was ist der maximale Wert von N, für die ein Programm berechnen kann, die Antwort in angemessener Zeit? Oder was ist das größte N, die wir bisher gesehen haben?
Hier ist mein Programm in CLPFD(Prolog):
generate([],_).
generate([H|T],N) :-
H in 1..N ,
generate(T,N).
lenlist(L,N) :-
lenlist(L,0,N).
lenlist([],N,N).
lenlist([_|T],P,N) :-
P1 is P+1,
lenlist(T,P1,N).
queens(N,L) :-
generate(L,N),lenlist(L,N),
safe(L),
!,
labeling([ffc],L).
notattack(X,Xs) :-
notattack(X,Xs,1).
notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
X #\= Y,
X #\= Y - N,
X #\= Y + N,
N1 is N + 1,
notattack(X,Ys,N1).
safe([]).
safe([F|T]) :-
notattack(F,T),
safe(T).
Dieses Programm funktioniert genauso gut, aber die Zeit, die es dauert, nimmt mit N.
Hier ist eine Beispiel-Ausführung:
?- queens(4,L).
L = [2, 4, 1, 3] ;
L = [3, 1, 4, 2] ;
No
Bedeutet dies, dass Sie statt der 4 Königinnen, die in Zeile 2 in Spalte 1, Zeile 4 in Spalte 2, Zeile 1 in 3 und Zeile 3 in 4.(In 4 Von 4 Schachbrett)
Nun werden wir sehen, wie dieses Programm führt(Zeit genommen bei der Berechnung der ersten permutation):
Für N=4,5.....10 Berechnet, innerhalb von einer Sekunde
Für N=11-30 Dauert zwischen 1-3 Sekunden
Für N=40..50 Noch berechnet innerhalb einer minute
Bei N=60 Es geht aus dem Globalen stack(Suche Raum enorm).
War dies ein Hausaufgaben problem, das aufgrund der im letzten Monat. Also ich denke, Ihr Recht, über Sie zu diskutieren jetzt.(Das ursprüngliche problem war, nur um code-N-Queens)
Ich bin auch daran interessiert, dass Alternative Implementierungen in anderen Sprachen(die besser als meine Umsetzung) oder Wenn es gibt Raum für Verbesserungen in meinem Algorithmus/Programm
InformationsquelleAutor der Frage | 2009-12-07
Du musst angemeldet sein, um einen Kommentar abzugeben.
kurze Lösung vorgelegt von raymond hettinger auf pycon: einfach die ki in python
computing alle Permutationen ist nicht skalierbar, obwohl (
O(n!))InformationsquelleAutor der Antwort miku
Dieser Diskussion verbindet drei verschiedene rechnerische Probleme: (1) die Suche nach einer Lösung des N-Damen-problem, (2) Auflistung aller Lösungen für einige Feste N, und (3) zählen alle Lösungen, die für einige Feste N. das erste problem, Das schwierig aussieht zuerst für eine Größe von board, wie z.B. N=8. Aber wie Wikipedia schon sagt, in einigen Schlüssel Weise ist es einfach, wenn N groß ist. Die Damen auf ein großes Brett kommunizieren nicht so viel. Außer für den Speicher Einschränkungen, Heuristik Reparatur-Algorithmus ist ein einfacher job, als N erhöht.
Auflistung jede Lösung ist eine andere Frage. Das kann wohl sein, mit einem guten dynamischen Programmierung code bis zu einer Größe, die groß genug ist, dass es keinen Punkt gibt, in dem Lesen der Ausgabe.
Die interessanteste version der Frage ist, zählen die Lösungen. Der Stand der Technik zusammengefasst in eine fabelhafte Referenz bekannt als Die Encyclopedia of Integer Sequences. Es wurde berechnet, bis N=26. Ich würde vermuten, dass, verwendet auch die dynamische Programmierung, aber im Gegensatz zu den Fall der Aufnahme in die Liste jede Lösung, die Algorithmische problem ist viel tiefer und offen für weitere Entwicklungen.
InformationsquelleAutor der Antwort Greg Kuperberg
Diese faszinierende Unberechenbarkeit in backtrack-Komplexität für unterschiedliche board Größen war der Teil in diesem puzzle, dass die meisten interessiert mich auch. Ich habe jahrelang die Gebäude eine Liste der 'zählt' der Algorithmus Schritte zu finden, die erste Lösung für jede board-Größe - mit der einfachen und gut bekannten depth-first-Algorithmus in eine rekursive C++ - Funktion.
Hier ist eine Liste all jener 'zählt' für boards bis zu N=49 ... minus N=46 N=48, das sind noch work-in-progress:
http://queens.cspea.co.uk/csp-q-allplaced.html
(Habe ich aufgelistet in der Encyclopedia of Integer Sequences (OEIS) als A140450)
Diese Seite enthält einen link zu einer Liste mit den passenden erste-Lösungen.
(Meine Liste Erste Lösungen ist OEIS-Folge Nummer A141843)
Ich nicht in Erster Linie zu erfassen, wie viel Verarbeitungszeit jede Lösung verlangt, sondern ich aufzeichnen, wie viele gescheiterte Königin-Platzierungen nötig waren, vor der Entdeckung jedes board ist algorithmisch-erste Lösung. Natürlich ist die rate der Königin Praktika hängt von der CPU-Leistung, aber bei einem kurzen test-run auf eine bestimmte CPU und einer bestimmten board-Größe, ist es leicht zu berechnen, wie lange es dauerte, um zu lösen, eine dieser "gefundenen" Lösungen.
Beispielsweise auf einem Intel Pentium D 3,4 GHz CPU, mit einem einzigen CPU-thread -
Meinem jetzigen 2,8 GHz i7-860 ist Prügel durch über 28,6 Millionen Königinnen pro Sekunde, versuchen, die erste Lösung für N=48. So weit hat es gedauert, über 550 Tagen (theoretisch, wenn es noch nie ununterbrochen), um Erfolglos Ort 1,369,331,731,000,000 (und schnell klettern) Königinnen.
Meine web-site nicht (noch nicht) zeigen eine C++ - code, aber ich gebe einen link auf die web-Seite zu meine einfache Darstellung von jedem der 15 Algorithmus-Schritte zum lösen der N=5 board.
Es ist ein köstliches puzzle-in der Tat!
InformationsquelleAutor der Antwort CSPea
Dem Prolog-system verwenden Sie? Zum Beispiel, mit den letzten Versionen von SWI-Prolog, können Sie leicht finden, Lösungen für N=80 und N=100 innerhalb von Bruchteilen einer Sekunde, verwenden Sie Ihre original-code. Vielen anderen Prolog-Systemen werden viel schneller als die.
Des N-Damen-problem wird auch als Feature in einem der online-Beispiele von SWI-Prolog, als CLP(FD) - queens in SWISH.
Beispiel mit 100 queens:
SWISH zeigt Ihnen auch schönsten U Bild der Lösungen.
Hier ist eine animierte GIF-Datei zeigt die vollständige Lösung Prozess für N=40 queens mit SWI-Prolog:
InformationsquelleAutor der Antwort mat
Was ist das größte N mit Computern lösen gibt es Hinweise in der Literatur, in der eine Lösung für N etwa 3*10^6 ist gefunden worden, mit einem Konflikt Reparatur-Algorithmus (z.B. lokale Suche). Siehe zum Beispiel die klassischen Papier - [ Sosic und Gu ].
Als exakte Lösung mit backtracking,gibt es einige clevere branching-Heuristiken, die das erreichen richtigen Konfigurationen mit fast kein backtracking. Diese Heuristiken können auch verwendet werden, um zu finden, die ersten-k Lösungen für das problem: nach der Suche nach einem ersten richtigen Konfiguration der Suche backtracks, um andere gültige Konfigurationen in der Nähe.
Referenzen für diese fast perfekt Heuristiken sind [Grünkohl 90] und [San Segundo 2011]
InformationsquelleAutor der Antwort chesslover
Gibt es kein limit. Das heißt, die Prüfung für die Gültigkeit der Lösung ist teurer als der Aufbau eines solution plus sieben symmetrische lieben.
Siehe Wikipedia:
"Explizite Lösungen existieren für die überführung von n Damen auf einem n × n Brett für alle n ≥ 4, dass keine kombinatorische Suche zu löschen.".
InformationsquelleAutor der Antwort false
Schleppte ich aus einem alten Delphi-Programm, dass zählt die Anzahl der Lösungen für jede board-Größe, habe eine schnelle änderung zu machen, es zu stoppen, nachdem ein Treffer, und ich bin zu sehen eine ungerade Muster in den Daten:
Ersten Brett dauerte über 1 Sekunde zu lösen, wurde n = 20. 21, gelöst in 62 Millisekunden, obwohl. (Hinweis: Dies basiert off Nun, nicht jeder high precision system.) 22 dauerte 10 Sekunden, nicht wiederholt zu werden, bis 28.
Ich weiß nicht, wie gut die Optimierung ist als diese war ursprünglich eine hoch optimierte routine aus zurück, wenn die Regeln der Optimierung waren sehr unterschiedlich. Ich habe eine Sache, die sehr anders als die meisten Implementierungen, obwohl-es hat keinen Vorstand. Vielmehr bin ich-tracking, welche Spalten und diagonalen werden angegriffen und das hinzufügen einer Königin pro Zeile. Dies bedeutet, dass 3 array-lookups pro Zelle getestet und keine Vermehrung überhaupt. (Wie gesagt, aus, wenn die Regeln sehr unterschiedlich waren.)
Nun für einige echte Wahnsinn: 29 dauerte 9 Sekunden. 30 dauerte fast 6 Minuten!
InformationsquelleAutor der Antwort Loren Pechtel
Eigentlich constrained-random-walk (erstellen und testen) wie das, was bakore beschrieben ist der Weg zu gehen, wenn Sie nur eine Handvoll Lösungen, denn diese können schnell generiert. Ich Tat dies für eine Klasse, wenn ich war 20 oder 21 und veröffentlichte die Lösung, die im Journal of Pascal, Ada & Modula-2, März 1987, "Die Damen-Problem Revisited". Ich habe gerade abgestaubt, den code aus diesem Artikel heute (und das ist sehr ineffizient-code) und nach der Reparatur ein paar Probleme erzeugen, für N=26 ... N=60 Lösungen.
InformationsquelleAutor der Antwort Kirt Undercoffer