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皇后難題的最佳複雜性是什麼？

回答

相關問題