nqueen沒有回溯

Question

n女王問題可以解決沒有回溯？

我遇到了n女王問題的許多類型的答案，但他們都需要回溯。有沒有解決它的方法沒有回溯？

Answer 1

是的。你可以通過生成所有可能的板子來強制它，然後測試每個板子。

這種辦法不能很好地擴展，雖然;）

也請注意，wikipedia article列出了一些解決方案，其中包括「反覆修」。

Answer 2

遺傳算法，進化最好的解決辦法並不需要回溯，但這是接近這個問題不是一個算法遍歷狀態空間圖，您的問題似乎暗示

Answer 3

有不同的方式。維基百科提到了一些，包括一個基於行列式（我現在很好奇，但沒有追蹤）。讓我複製粘貼一個verbatim：

上面的例子可以用下面的公式獲得。令（i，j）爲第n列棋盤上第i列和第j列棋盤上的正方形，k爲整數。

1. 如果n是偶數且n≠6K + 2，然後將皇后位於（i，2I）和（n/2 + I，2I - 1）對於i = 1,2，.. ...，N/2。如果n是偶數並且n≠6k，則將皇后置於（i，1 +（2i + n/2 -3（mod n）））和（n + 1 -i，n-（2i + n/2 - 3（mod n）））對於i = 1,2，...，n/2。
2. 如果n是奇數，那麼使用上面的模式之一（n - 1）並在（n，n）處添加一個皇后。