可以使用哪些策略来保持最大数量的非攻击棋子（除典当之外的所有棋子）木板？它就像一个- 皇后问题，但这里不仅仅是皇后，其他作品也出现了。就像我有一个骑士、女王、国王、主教、骑士一样，让他们保持领先的最佳策略是什么？板使得非棋子相互攻击？
补充一点，我会以随机的方式一个接一个地得到碎片，所以基本上我无法控制出现的碎片的顺序和数量。比如 1. 皇后 2. 主教 3. 皇后 4. 奈特和我必须让他们保持板使得没有棋子相互攻击。
可以使用什么策略来保持最大数量的非攻击棋子n × nn×n棋盘？
计算科学
组合学
启发式
2021-12-13 19:07:53
1个回答
虽然这不是一个完整的算法，但我想我可以为您指出一个目标。每一块都有特定数量的空间，它可以在更大的 15x15 网格中移动，其自身位于中心。每当您将一块棋子放在棋盘上时，它可以移动的空间就会变得“不安全”。您的总体目标是尽可能长时间地保留安全空间，以便您可以继续放置更多部件。
由于您事先不知道棋子的顺序和类型，所以我只能建议贪心算法。当你得到下一个棋子时，循环遍历所有“安全”空间，看看它们中的任何一个是否由于新棋子能够从该位置攻击另一个棋子而无效。一旦你有一组有效的“安全”空间，选择一个使新的“不安全”空间数量最少的一个。换句话说，您试图将尽可能多的新棋子的可移动空间放在棋盘边缘之外，或者放在预先存在的“不安全”空间之上。
如果你事先知道你会得到什么，你可以想出更复杂的东西。