解决N皇后控制拼图的算法
我已经解决了更通用的N皇后问题，但现在我正在寻找一种算法来解决N皇后控制问题。
“给定一个n×n棋盘，找到控制号码，这是攻击或占据每个方块所需的皇后（或其他棋子）的最小数量。对于8×8棋盘，皇后的统治数字是5。 - 维基百科
我已经广泛搜索，除了关于这个问题的学术论文外什么都找不到，没有什么可以远程理解的。
我的第一个想法是只放置一个女王，然后将下一个女王放置在可以攻击大多数其他广场的地方，等等。 然而，虽然这可能会产生一个解决方案，但我无法想出一种方法来保证该解决方案是最小的解决方案。
任何帮助将不胜感激，谢谢。
使用你的算法，你可以产生所有可能的组合，并从中取得最小值。 提示：为此使用递归并且不处理类似的条件（或缓存它），如对称布局，相同的顺序等等。
本着作为一个家庭作业问题的精神，我不会提供解决方案，而是提供一系列解决方案的问题。 以下是回答“你可以用n女王主宰董事会吗？”的方式。 然后，您可以通过测试n = 1，n = 2，...来找到控制号码。
1）通过将女王放置在位置1 *，您是否可以通过将（n-1）女王位置放置在从（2,3，...）中选择的（n-1）个位置来控制女王1未达到的所有剩余位置？
2）如果没有，你可以将女王放置在位置2，然后通过将（n-1）女王位置放置在（n-1）位置（3,4，...）中来控制女王1未达到的所有剩余位置。 ）？
3）等等......即将第一个女王放置在位置3，然后位置4等等。
请注意，此解决方案是递归的 - 在每次递归时，“剩余位置添加皇后”和“任何皇后不可达的位置”作为参数传递。 当“任何皇后不能到达的位置”为空时，您已找到解决方案。
*以某种方式排列所有董事会职位，例如从左到右，从上到下。 因此，8x8板上的64个位置可以仅由一个索引（1..64）来引用。
以下效率不高，但它会起作用。
将该问题重新编译为整数编程问题。 棋盘上的每个方格都是0或1.对于任何方格而言，其本身和所有进攻方格的总和应该恰好为1.并且要使总和最小化。
链接地址: http://www.djcxy.com/p/57379.html