Lösung des N-Damen-Problem... Wie weit können wir gehen?

kurze Lösung vorgelegt von raymond hettinger auf pycon: einfach die ki 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

computing alle Permutationen ist nicht skalierbar, obwohl (O(n!))

Loren Pechtel sagte: "Jetzt für einige echte Wahnsinn: 29 dauerte 9 Sekunden.
30 dauerte fast 6 Minuten!"

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 -

• Für N=35 mein Programm 'platziert' 24 Millionen Königinnen pro Sekunde und dauerte nur 6 Minuten, um die erste Lösung.
• Für N=47 mein Programm 'platziert' 20,5 Millionen Königinnen pro Sekunde und nahm 199 Tage.

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!

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 von [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]

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!

Wenn Sie möchten, dass nur 1 Lösung, dann kann es gefunden werden gierig in linearer Zeit O(N). 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 das drucken dauert O(N^2) Zeit und auch python wird ein langsamer Sprache, die jeder kann versuchen, es umzusetzen in anderen Sprachen wie C/C++ oder Java. Aber auch mit python wird es die erste Lösung für n=1000 in 1 oder 2 Sekunden.