algorithm - N+1皇后算法

Question

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

我想先放一个兵和4个皇后在兵的每一边，但我不确定这样会提高计算速度。

Answer 1

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