4 个皇后和 1 个骑士攻击 8*8 棋盘上的所有方块
4 Queens and 1 Knight to attack all blocks on a 8*8 board
我手头有一个问题，它是 N-Queen 的变体-Problem.The 问题是：想办法在 8*8 的棋盘上放置 4 个皇后和 1 个骑士，这样所有的方块可以被这些攻击 pieces.It 棋子可以互相攻击。
我了解如何使用回溯法解决原始 N 皇后问题。但是，我想不出如何减少这个新问题中的搜索次数。希望有人能给我一个hint.Thank你
谢谢大家。@vish4071 @Karoly Horvath @M Oehm 我会考虑使用蛮力，看看我能得到什么。
我认为朴素的算法不需要任何类型的优化，因为它可能会很快...但是，这里是：
您始终可以将第一步限制在其中一个区域（例如：左上角），因为其余的解决方案都可以通过镜像或旋转从中生成。
你可以计算覆盖的地方，并且有一个可以覆盖多少的限制（女王 22 个，国王 9 个），所以你可以以此作为提前终止无望分支的规则。
注意：由于您只有 4 个皇后，将 2 个放在同一行或同一列可能不是一个好主意。您可以尝试将其作为限制条件。
使用蛮力。应该会在短时间内给你答复。
你有 64 个方块要考虑，还有 5 个要放。只需 select 5 个方格并放 5 个棋子，看看这个场景是否涵盖所有方格。这可以通过 C(64,5) * 5 方式完成，即 ~3.8e7，如今在标准机器上很容易在不到 1 秒的时间内计算出来。
此外，如果将 4 个皇后放在 64 个方格中的 select 4 个中，然后将马放置在仅覆盖剩余的方格中，则可以减少一些计算量。这将需要大约 C(64,4) * k 次计算，即 ~1e6.
我手头有一个问题，它是 N-Queen 的变体-Problem.The 问题是：想办法在 8*8 的棋盘上放置 4 个皇后和 1 个骑士，这样所有的方块可以被这些攻击 pieces.It 棋子可以互相攻击。
我了解如何使用回溯法解决原始 N 皇后问题。但是，我想不出如何减少这个新问题中的搜索次数。希望有人能给我一个hint.Thank你
谢谢大家。@vish4071 @Karoly Horvath @M Oehm 我会考虑使用蛮力，看看我能得到什么。
我认为朴素的算法不需要任何类型的优化，因为它可能会很快...但是，这里是：
您始终可以将第一步限制在其中一个区域（例如：左上角），因为其余的解决方案都可以通过镜像或旋转从中生成。
你可以计算覆盖的地方，并且有一个可以覆盖多少的限制（女王 22 个，国王 9 个），所以你可以以此作为提前终止无望分支的规则。
注意：由于您只有 4 个皇后，将 2 个放在同一行或同一列可能不是一个好主意。您可以尝试将其作为限制条件。
使用蛮力。应该会在短时间内给你答复。
你有 64 个方块要考虑，还有 5 个要放。只需 select 5 个方格并放 5 个棋子，看看这个场景是否涵盖所有方格。这可以通过 C(64,5) * 5 方式完成，即 ~3.8e7，如今在标准机器上很容易在不到 1 秒的时间内计算出来。
此外，如果将 4 个皇后放在 64 个方格中的 select 4 个中，然后将马放置在仅覆盖剩余的方格中，则可以减少一些计算量。这将需要大约 C(64,4) * k 次计算，即 ~1e6.