N-Queens拼图的最佳复杂性是什么？

Question

理论上,N-Queens难题可以在多项式时间内求解吗？如果是这样,它的最大复杂性是什么？我找到了很多算法,但我还没有找到时间复杂度究竟是什么.是否有任何文件或文件给出其复杂性的确切数量？

(PS显式解决方案非常有趣,但我忘了说,我希望找到所有的解决方案.)

Answer 1

这个链接引用了一个"众所周知的"显式解决方案.它可以在线性时间内计算:

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

1. n是偶数但不是形式(n mod 6 = 2).将女王放置在正方形(m,2m)和(n/2 + m,2m-1)上,m = 1,2,.... ..,n/2

2. n是偶数但不是形式(n mod 6 = 0)并且在正方形上放置皇后(m,1 +(2(m-1)+ n/2 - 1)mod n)和(n + 1-m) ,n-(2(m-1)+ n/2 -1)mod n)对于m = 1,2,...,n/2

3. n很奇怪.在n - 1上使用(1)或(2),以适当的为准,并在(n,n)处以女王的形式延伸.

请注意,枚举所有解决方案需要更长时间.解决方案的数量随着电路板的大小呈指数级增长(http://oeis.org/A000170),因此即使有2^O(x)时间也不可能枚举(但只O(n)需要空间).

Answer 2

你的意思是找到一种解决方案还是所有解决方案？根据维基百科，如果您只想找到一种解决方案，那么这可以轻松完成。

\n\n

\n

存在将 n 个皇后放置在 n \xc3\x97 n 板上的显式解决方案，\n 不需要任何组合搜索。

\n

\n