N皇后问题的最佳复杂度是什么？

Question

理论上，N皇后问题能否在多项式时间内解决？如果可以，它的最佳复杂度是什么？我找到了许多算法，但我没有找到确切的时间复杂度。是否有任何论文或文档提供其复杂度的确切数字？

（附言：显式解非常有趣，但我忘记说了，我希望找到所有解决方案。）

- Rosetta

Answer 1

这个链接引用了一个“众所周知”的显式解法。它可以在线性时间内计算出来：

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 为偶数且不满足 (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 为奇数时，使用 (1) 或 (2) 中适合的方法在 n-1 上放置皇后，然后在 (n,n) 上扩展一个皇后。

请注意，列举所有解决方案需要更长的时间。随着棋盘大小的增加，解决方案的数量呈超指数增长（http://oeis.org/A000170），因此即使使用2^O(x)时间也无法枚举它们（但只需要O(n)空间）。

- John Dvorak

Answer 2

您是指寻找一个解决方案还是所有解决方案？如果您只想找到一个解决方案，这可以很轻松地完成，根据维基百科的说法。

对于在n×n棋盘上放置n个皇后的问题，存在明确的解决方案，不需要进行任何组合搜索。

- Antimony

---

省略的维基链接：http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions - biziclop

你能找到显式解吗？我尝试过但失败了。WP引用的来源只接受现金，但我在互联网上看到了一个显式解。 - John Dvorak

对不起，我的意思是找到所有的解决方案。 - Rosetta