Lösen von N-Queens Problem ... Wie weit können wir gehen?
https://stackoverflow.com/questions/1863531
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Das N-Queens Problem:
Dieses Problem stellt fest, dass durch N ein Schachbrett der Größe N gegeben, die verschiedenen Permutationen finden, in denen N Damen auf dem Brett platziert werden können, ohne eine einander bedrohen.
Meine Frage ist:
Was ist der maximale Wert von N für die ein Programm der Antwort in angemessener Zeit berechnen kann? Oder was ist die größte N 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 ganz gut, aber die Zeit hält sie mit N. auf die Erhöhung nimmt Hier ist ein Beispiel der Ausführung:
?- queens(4,L).
L = [2, 4, 1, 3] ;
L = [3, 1, 4, 2] ;
No
Das heißt, Sie die 4 Königinnen in Zeile 2 in Column1 platzieren, Zeile 4 in Spalte 2, Reihe 1 in 3 und Zeile 3 in 4 (in einem 4 x 4 Schachbrett)
Jetzt können sehen, wie dieses Programm führt (Zeit genommen in der ersten Permutation Berechnung):
Für N = 4,5 ..... 10 berechnet innerhalb einer Sekunde
Für N = 11-30 dauert zwischen -1-3 Sekunden
Für N = 40..50 berechnet Noch innerhalb einer Minute
Bei N 60 = Es geht aus dem globalen Stack (Search Raum ist enorm).
Dies war eine Vergangenheit HFG Problem. (Das ursprüngliche Problem war nur, Code N-Queens)
Ich interessiere mich auch für andere Sprachen alternative Implementierungen zu sehen (was als meine Implementierung besser abschneidet) oder wenn es Raum für Verbesserungen in meinem Algorithmus / Programm
Lösung
eine kurze Lösung von Raymond Hettinger bei PyCon präsentiert: einfach ai in Python
#!/usr/bin/env python
from itertools import permutations
n = 12
cols = range(n)
for vec in permutations(cols):
if (n == len(set(vec[i] + i for i in cols))
== len(set(vec[i] - i for i in cols))):
print vec
alle Permutationen der Berechnung ist nicht skalierbar, obwohl (O(n!))
Andere Tipps
Diese Diskussion verschmilzt drei verschiedene Rechenprobleme: (1) Die Suche nach einer Lösung für das Problem Königinnen N, (2) Eine Auflistung aller Lösungen für einige festen N, und (3) alle Lösungen für einige festen N. Des Zählen zuerst Problem sieht auf den ersten für eine Größe der Platte, wie beispielsweise N = 8 heikel. Doch wie Wikipedia schon sagt, in einigen wichtigen Möglichkeiten, es ist einfach, wenn N groß ist. Die Königinnen auf einem großen Brett kommunizieren nicht allzu viel. Mit Ausnahme von Speicherbeschränkungen, hat ein heuristischer Reparaturalgorithmus einen einfachen und leichten Job als N erhöht.
jede Lösung Listing ist eine andere Sache. Das kann wohl mit einem guten dynamischen Programmiercode bis zu einer Größe durchgeführt werden, die groß genug ist, dass es keinen Sinn, die Ausgabe beim Lesen.
Die interessanteste Version der Frage ist es, die Lösungen zu zählen. Der Stand der Technik ist in einer fabulous Referenz bekannt als die Encyclopedia of Integer Sequences zusammengefasst . Es wurde bis zu N = 26 berechnet. Ich würde vermuten, dass diese verwenden auch die dynamische Programmierung, aber im Gegensatz zu dem Fall jede Lösung Listing, das algorithmische Problem ist viel tiefer und offen für weitere Fortschritte.
Loren Pechtel sagte: „Jetzt für einigen echten Wahnsinn: 29 9 Sekunden gedauert. 30 nahm fast 6 Minuten! "
Dieser faszinierende Mangel an Vorhersehbarkeit in Backtrack-Komplexität für unterschiedliche Plattengrößen war der Teil des Puzzles, das am meisten interessiert mich. Seit Jahren eine Liste der ‚zählt‘ von Algorithmusschritten Aufbau benötigt, um die erste Lösung für jede Plattengröße zu finden Ich habe - mit dem einfachen und bekannten depth-first-Algorithmus in einem rekursiven C ++ Funktion.
Hier ist eine Liste all jene 'zählt' für Platten bis zu N = 49 ... minus N = 46 und N = 48, die noch arbeiten-in-progress :
http://queens.cspea.co.uk/csp-q- allplaced.html
(Ich habe das in der Enzyklopädie der Zahlenfolgen (OEIS) als aufgeführt bekam A140450 )
Diese Seite enthält einen Link zu einer Liste der passenden ersten Lösungen.
(Meine Liste Erste Lösungen ist OEIS Sequenznummer A141843 )
Ich zeichne nicht in erster Linie, wie viel Verarbeitungszeit jeder Lösung verlangt, sondern zeichne ich, wie viele gescheiterte Königin-Platzierungen benötigt wurden vor der Entdeckung der einzelnen Board algorithmisch erste Lösung. Natürlich ist die Rate der Königin Platzierungen auf CPU-Leistung abhängig ist, aber ein schnellen Testlauf auf einer bestimmten CPU und eine bestimmte Größe der Leiterplatte gegeben, dann ist es eine einfache Sache, zu berechnen, wie lange es eines dieser ‚gefunden‘ Lösungen zu lösen hat.
Zum Beispiel auf einem Intel Pentium D 3,4 GHz CPU, einen einzelnen CPU-Thread mit -
- Für N = 35 mein Programm ‚placed‘ 24 Millionen Königinnen pro Sekunde und nahm nur 6 Minuten, um die erste Lösung zu finden.
- Für N = 47 mein Programm 'placed' 20500000 Königinnen pro Sekunde und nahm 199 Tage.
Mein aktueller 2.8GHz i7-860 wird Dreschen um etwa 28,6 Mio. Königinnen pro Sekunde, die erste Lösung für N = 48 zu finden versuchen. Bisher hat es 550 Tage übernommen (theoretisch, wenn es nie unterbrochen gewesen war) zu Erfolglos 1.369.331.731.000.000 zu platzieren (und schnell klettern) Königinnen.
Meine Website ist (noch) nicht zeigen, jeden C ++ Code, aber ich habe einen Link auf dieser Web-Seite zu meiner einfachen Darstellung eines jeder der 15 Algorithmusschritte gibt notwendig, um die N = 5 Board zu lösen.
Es ist ein köstlich-Puzzle in der Tat!
Welche Prolog-System verwenden Sie? Zum Beispiel mit dem aktuellen Versionen von SWI-Prolog, können Sie leicht finden Lösungen für N = 80 und N = 100 innerhalb von Bruchteilen einer Sekunde ursprünglichen Code. Viele andere Prolog Systeme werden viel schneller als das.
Das N-Damen-Problem auch in einen der Online-Beispiele für SWI-Prolog, als CLP (FD) Königinnen in SWISH.
Beispiel mit 100 Königinnen :
?- time((n_queens(100, Qs), labeling([ff], Qs))). Qs = [1, 3, 5, 57, 59 | ...] . 2,984,158 inferences, 0.299 CPU in 0.299 seconds (100% CPU, 9964202 Lips)
SWISH zeigen Ihnen auch nices Bild von Lösungen.
Hier ist eine animierte GIF die kompletten Lösungsverfahren für zeigt N = 40 Königinnen mit SWI-Prolog:
Wie zu dem, was von Computern die größte N gelöst ist, gibt es Hinweise in der Literatur, in der eine Lösung für N um 3 * 10 ^ 6 hat einen Konflikt Reparatur-Algorithmus (das heißt die lokale Suche) gefunden. Siehe zum Beispiel das klassische Papier von [ Sosic und Gu ].
Was genau mit Rückzieher zu lösen, gibt es einige clevere Verzweigung Heuristik, die mit fast keinem Rückzieher richtige Konfigurationen erzielen. Diese Heuristiken können auch verwendet werden, die first-k Lösungen für das Problem zu finden: Nach einer anfänglichen korrekten Konfiguration zu finden, die Suche Backtracking andere gültige Konfigurationen in der Nähe zu finden.
Referenzen für diese fast perfekt Heuristiken sind [ Kale 90 ] und [ San Segundo 2011 ]
Was ist der maximale Wert von N für die ein Programm der Antwort in angemessener Zeit berechnen kann? Oder was ist die größte N wir bisher gesehen haben?
Es gibt keine Begrenzung. Das heißt, die Überprüfung für die Gültigkeit einer Lösung teurer ist als die Konstruktion eine Lösung plus sieben symmetrisch diejenigen.
Siehe Wikipedia: "Explicit Lösungen existieren für die Platzierung n Königinnen auf einem n × n Platine für alle n ≥ 4 und erfordert keine kombinatorische Suche auch immer. ".
schleppte ich ein altes Delphi-Programm aus, das die Anzahl von Lösungen für jede gegebene Plattengröße gezählt, hätte eine schnelle Änderung, um es nach einem Treffer zu stoppen und ich sehe ein seltsames Muster in den Daten:
Die erste Platte, die als 1 Sekunde dauerte zu lösen war n = 20. 21 in 62 Millisekunden gelöst, wenn. (. Hinweis: Diese basiert weg nun kein Hochpräzisionssystem) 22 dauerten 10 Sekunden nicht bis 28 wiederholt werden
.Ich weiß nicht, wie gut die Optimierung ist als dies ursprünglich war eine hoch optimierte Routine aus zurück, wenn die Regeln der Optimierung waren sehr unterschiedlich. Ich habe sehr eine Sache anders als die meisten Implementierungen, obwohl - es kein Bord hat. Vielmehr bin ich Tracking, welche Spalten und Diagonalen angegriffen werden und das Hinzufügen einer Königin pro Zeile. Dies bedeutet, 3-Array-Lookups pro Zelle getestet und keine Vermehrung überhaupt. (Wie gesagt, aus, wenn die Regeln waren sehr unterschiedlich.)
Jetzt für einigen echten Wahnsinn: 29 nahmen 9 Sekunden. 30 nahm fast 6 Minuten!
Eigentlich Irrfahrt (erzeugen und Test) begrenzt wie das, was bakore die Art und Weise umrissen ist zu gehen, wenn Sie nur eine Handvoll Lösungen benötigen, da diese schnell erzeugt werden kann. Ich tat dies für eine Klasse, als ich 20 oder 21 und veröffentlichte die Lösung im Journal of Pascal, Ada & Modula-2, März 1987 "The Queens Problem Revisited". Ich abgestaubt gerade heute den Code aus diesem Artikel aus (und das ist sehr ineffizient Code) und nach ein paar Probleme zu beheben sind N = 26 wurden Erzeugung ... N = 60 Lösungen.
Wenn Sie nur 1 Lösung wollen, dann können sie gierig in linearer Zeit O (N) gefunden werden. Mein Code in Python:
import numpy as np
n = int(raw_input("Enter n: "))
rs = np.zeros(n,dtype=np.int64)
board=np.zeros((n,n),dtype=np.int64)
k=0
if n%6==2 :
for i in range(2,n+1,2) :
#print i,
rs[k]=i-1
k+=1
rs[k]=3-1
k+=1
rs[k]=1-1
k+=1
for i in range(7,n+1,2) :
rs[k]=i-1
k+=1
rs[k]=5-1
elif n%6==3 :
rs[k]=4-1
k+=1
for i in range(6,n+1,2) :
rs[k]=i-1
k+=1
rs[k]=2-1
k+=1
for i in range(5,n+1,2) :
rs[k]=i-1
k+=1
rs[k]=1-1
k+=1
rs[k]=3-1
else :
for i in range(2,n+1,2) :
rs[k]=i-1
k+=1
for i in range(1,n+1,2) :
rs[k]=i-1
k+=1
for i in range(n) :
board[rs[i]][i]=1
print "\n"
for i in range(n) :
for j in range(n) :
print board[i][j],
print
Hier aber Druck nimmt O (N ^ 2) Zeit und auch Python eine langsame Sprache jemand zu sein versucht, kann es in anderen Sprachen wie C / C ++ oder Java implementiert. Aber auch mit Python wird es die erste Lösung für n = 1000 erhält innerhalb von 1 oder 2 Sekunden.
