我希望提高算法的速度,以计算 N+1 皇后问题的解决方案数量(将N+1
皇后放在NxN
棋盘上,有 1 个棋子)。我基本上使用蛮力与回溯相结合,我首先将棋子放在棋盘上的随机位置(没有没有边缘的正方形的边缘和角落),然后我才开始使用回溯放置皇后。这种方法很容易,但也很慢。什么算法会更快?
我正在考虑首先在棋子的每一侧放置一个棋子和 4 个皇后,但我不确定这会提高计算速度。
我希望提高算法的速度,以计算 N+1 皇后问题的解决方案数量(将N+1
皇后放在NxN
棋盘上,有 1 个棋子)。我基本上使用蛮力与回溯相结合,我首先将棋子放在棋盘上的随机位置(没有没有边缘的正方形的边缘和角落),然后我才开始使用回溯放置皇后。这种方法很容易,但也很慢。什么算法会更快?
我正在考虑首先在棋子的每一侧放置一个棋子和 4 个皇后,但我不确定这会提高计算速度。
当您要计算问题的所有解决方案时,将棋子首先放在随机位置是行不通的。您必须将棋子放在每个位置。我相信这里最好的算法是回溯,但你仍然可以做一些优化。在 n-queen 问题中,一个重要的一点是利用解的对称性,所以我想你也可以在这里做到这一点。有一个解决方案,它的所有 4 个旋转和它们的镜像也是解决方案。
您自己的建议听起来是正确的,因为它从任何解决方案都需要满足的基本约束开始,而不是事后验证每个候选解决方案。
对于穷举搜索问题,最大的加速通常出现在您实施提前退出规则时:一旦一个皇后攻击另一个皇后,您就不再放置任何皇后,并为最后一个皇后进入一个新的方格。与仅在所有棋子都放在棋盘上时才检查相互攻击的详尽搜索相比,这将大大减少搜索空间。
棋盘上的棋子位置NxN
可以减少到内部(N-2)x(N-2)
子板上,您可以使用 8 倍旋转/镜像对称将其进一步减少到该内部正方形的八分圆之一。