algorithm - 无回溯的皇后

Question

可以不回溯解决n皇后问题吗？

我遇到了许多关于n 皇后问题的答案，但它们都需要回溯。有没有不回溯的解决方法？

Answer 1

是的。您可以通过生成所有可能的板，然后测试每个板来强制它。

这种方法虽然不能很好地扩展；）

另请注意，维基百科文章列出了许多解决方案，包括“迭代修复”。

Answer 2

进化出最佳解决方案的遗传算法不需要回溯，但这是解决问题的另一种方法，而不是遍历您的问题似乎暗示的状态空间图的算法

Answer 3

是的。维基百科提到了一些，包括一个基于决定因素的（我现在很好奇，但还没有找到）。让我逐字复制粘贴：

上面的例子可以用下面的公式得到。令 (i, j) 为 n × n 棋盘上 i 列和 j 行的正方形，k 为整数。

1. 如果 n 是偶数且 n ≠ 6k + 2，则将皇后放置在 (i, 2i) 和 (n/2 + i, 2i - 1) 处，因为 i = 1,2,...,n/2。
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。
3. 如果 n 是奇数，则对 (n - 1) 使用上述模式之一，并在 (n, n) 处添加一个皇后。