algorithm - N+1皇后算法

Question

我希望提高算法的速度，以计​​算 N+1 皇后问题的解决方案数量（将N+1皇后放在NxN棋盘上，有 1 个棋子）。我基本上使用蛮力与回溯相结合，我首先将棋子放在棋盘上的随机位置（没有没有边缘的正方形的边缘和角落），然后我才开始使用回溯放置皇后。这种方法很容易，但也很慢。什么算法会更快？

我正在考虑首先在棋子的每一侧放置一个棋子和 4 个皇后，但我不确定这会提高计算速度。

Answer 1

当您要计算问题的所有解决方案时，将棋子首先放在随机位置是行不通的。您必须将棋子放在每个位置。我相信这里最好的算法是回溯，但你仍然可以做一些优化。在 n-queen 问题中，一个重要的一点是利用解的对称性，所以我想你也可以在这里做到这一点。有一个解决方案，它的所有 4 个旋转和它们的镜像也是解决方案。

Answer 2

您自己的建议听起来是正确的，因为它从任何解决方案都需要满足的基本约束开始，而不是事后验证每个候选解决方案。

对于穷举搜索问题，最大的加速通常出现在您实施提前退出规则时：一旦一个皇后攻击另一个皇后，您就不再放置任何皇后，并为最后一个皇后进入一个新的方格。与仅在所有棋子都放在棋盘上时才检查相互攻击的详尽搜索相比，这将大大减少搜索空间。

棋盘上的棋子位置NxN可以减少到内部(N-2)x(N-2)子板上，您可以使用 8 倍旋转/镜像对称将其进一步减少到该内部正方形的八分圆之一。