backtracking - N-Queens 谜题，但包含所有棋子

Question

我想解决类似于 N-Queens 的问题，但是：

• 所有棋子都可用
• 用户输入要放置多少件（例如 3 个车、4 个骑士、1 个主教）

我现在在地板上躺了一段时间，但想不出如何为此目的调整回溯算法。我将非常感谢任何形式的帮助。

Answer 1

原则上，与经典 N-Queen 问题相同的方法应该有效：

1. 找到一个空的、没有被攻击的方格，你可以在其中放置下一个棋子
2. 递归搜索新位置（或者如果您已经放置了所有部件，则输出解决方案）
3. 取回最后放置的一块并重复（转到步骤 1），直到您尝试了所有可以放置下一块的方块

与经典 N-Queens 问题的唯一区别是不同的部分具有不同的攻击模式。一些常见的优化可能不再起作用。例如，如果你有棋子，它会破坏对称性，因为它们只会攻击它们前面的方格。（尽管即使有棋子，您仍然有一个对称轴。）

如果您首先放置覆盖最多方格的棋子，我希望回溯算法更有效：首先是皇后，然后是车和象，然后是骑士和国王，最后是棋子。