N皇后难题的最佳复杂性是什么？

N皇后难题在理论上可以用多项式时间求解吗？如果是这样，它最好的复杂程度是什么？我发现了很多算法，但是我还没有发现时间复杂度。是否有任何文件或文件给出其确切的复杂性？N皇后难题的最佳复杂性是什么？

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

来源

2012-10-28 Rosetta

你的意思是找到一个解决方案或所有的解决方案？根据维基百科的说法，如果你只想找到一个解决方案，这可以轻松完成。

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

来源

2012-10-28 14:05:39 Antimony

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

你能找到明确的解决方案吗？我尝试失败了。源代码WP的参考资料仅为现金，但我确实在互联网上看到了明确的解决方案。 –

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

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

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

n为偶数，但不是形式的（N模6 = 2）。对于m = 1,2，...，在方块（m，2m）和（n/2 + m，2m-1）上放置皇后。。。中，n/2

n为偶数但不是形式（N模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

n很奇怪。在n-1上使用（1）或（2）（以适当的为准），并在（n，n）处使用女王后缀。

注意，枚举所有的解决方案将需要更长的时间。解决方案数量随着电路板尺寸（http://oeis.org/A000170）成倍增长，因此即使在2^O(x)时间内也无法枚举（但只需要O(n)空间）。

来源

2012-10-28 14:17:07

N皇后难题的最佳复杂性是什么？

回答

相关问题