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）处添加一个皇后。