algorithm - 4 个皇后和 1 个骑士攻击 8*8 棋盘上的所有方 block

Question

我手头有一个问题，它是 N-Queen-Problem 的一个变体。问题是:找到一种方法在 8*8 的棋盘上放置 4 个皇后和 1 个骑士，这样所有的方 block 都可以被攻击这些棋子。棋子互相攻击是可以的。

我了解如何使用回溯法解决原始 N 皇后问题。但是，我想不出如何减少这个新问题中的搜索次数。我希望有人能给我提示。谢谢。

---

谢谢大家。@vish4071 @Karoly Horvath @M Oehm 我会考虑使用蛮力，看看我能得到什么。

Answer 1

使用蛮力。它应该会在短时间内给您答复。

您有 64 个正方形要考虑，还有 5 个要放。只需选择 5 个方格并放置 5 个棋子，看看这个场景是否涵盖所有方格。这可以通过 C(64,5) * 5 方式完成，即 ~3.8e7，现在在标准机器上很容易在不到 1 秒的时间内计算出来.

此外，如果将 4 个皇后放在 64 个方格中的 4 个中，然后将马放置在仅覆盖剩余的方格中，则可以减少一些计算量。这将进行 C(64,4) * k 计算，即 ~1e6。