11

N皇后谜题理论上可以在多项式时间内解决吗？如果是这样，它的最佳复杂性是什么？我找到了很多算法，但我还没有找到时间复杂度到底是多少。是否有任何文件或文件给出了其复杂性的确切数字？

（PS 显式解法很有意思，但我忘了说，我希望找到所有的解法。）

4

2 回答 2

7

该链接引用了一个“众所周知的”显式解决方案。它可以在线性时间内计算：

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)需要空间）。

于 2012-10-28T14:17:07.883 回答
1

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

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

于 2012-10-28T14:05:39.887 回答