解决N皇后控制难题的算法

Question

我已经解决了更通用的N Queens问题,但现在我正在寻找一种算法来解决N Queens Domination问题.

"给定n×n板,找到控制号码,这是攻击或占据每个方格所需的最小皇后(或其他部分).对于8×8板,女王的统治号码是5". - 维基百科

我已经进行了广泛的搜索,除了关于这个问题的学术论文之外什么都找不到,没有什么是可以理解的.

我的第一个想法是放下一个女王,然后将下一个女王放在可以攻击大多数其他方块的地方,依此类推.然而,虽然这可能会产生一个解决方案,但我无法找到一种方法来保证该解决方案是最小的解决方案.

任何帮助将不胜感激,谢谢.

Answer 1

使用您的算法，您可以生成所有可能的组合并从中获取最小值。提示：为此使用递归，并且不要处理类似的条件（或缓存它），例如对称放置、相同顺序等。