Was ist die beste Komplexität von N-Queens Puzzle?

Question

Kann das N-Queens-Rätsel theoretisch in polynomieller Zeit gelöst werden? Wenn ja, was ist die größte Komplexität? Ich habe viele Algorithmen gefunden, aber ich habe nicht gefunden, was genau die zeitliche Komplexität ist. Gibt es Papiere oder Dokumente, die eine genaue Anzahl ihrer Komplexität angeben?

(P. S. Die explizite Lösung ist sehr interessant, aber ich vergaß zu sagen, ich wünsche alle Lösungen zu finden.)

Answer 1

Haben Sie meine Suche nach einer Lösung oder alle Lösungen? Will man nur eine Lösung finden, kann dies laut Wikipedia Wikipedia trivial erfolgen.

Explicit Lösungen existieren für n Königinnen auf einer n × n Platine platzieren, keinerlei kombinatorische Suche erfordern.

Answer 2

Dieser Link zitiert eine "bekannte" explizite Lösung. Es kann in linearer Zeit berechnet werden:

http://www.chegg.com/homework-help/questions-and-answers/poor-man-s-n-queens-problemn-queens-arranged-n-x-n-chessboard-way-queen-checks-queen-queen-q1009394

1. n gerade ist, aber nicht von der Form (n mod 6 = 2). Setzen Sie Königinnen auf die Quadrate (m, 2m) und (n/2 + m, 2m-1) für m = 1, 2,. . . , N/2

2. n selbst, aber nicht von der Form (n mod 6 = 0) und Platz Königinnen auf den Plätzen (m, 1 + (2 (m-1) + n/2 - 1) mod n) und (n + 1-m, n- (2 (m-1) + n/2 -1) mod n) für m = 1,2, ..., n/2

3. n ist ungerade. Verwenden Sie (1) oder (2), je nachdem, was angebracht ist, auf n - 1 und verlängern Sie mit einer Königin auf (n, n).

Beachten Sie, dass alle Lösungen Aufzählen viel länger dauern würde. Die Anzahl der Lösungen wächst superexponential mit der Größe der Platine (http://oeis.org/A000170), so dass sie nicht einmal mit 2^O(x) Zeit (aber nur O(n) Platz wird benötigt) aufgezählt werden.