如何计算最小数量的皇后，以攻击每个未覆盖的方格？

Question

这是一道来自《编程面试要点》的变形题，无解答。

你如何计算最少需要放置多少个皇后才能攻击所有未被覆盖的方格？

- Sadeer Nasser

---

棋盘是空的吗？它的大小是多少？ - templatetypedef

是的，棋盘是空的，棋盘大小为n x n，其中n可以是任何值。 - Sadeer Nasser

nxn棋盘的上限是n。 - tejasvi88

Answer 1

这个问题涉及到在图形中寻找最小支配集（在这种情况下是王后图http://mathworld.wolfram.com/QueenGraph.html），这个更普遍的问题是NP-Hard。即使在这种特殊类型的图形上进行缩减不太可能是NP-Hard，你也许无法找到任何高效（多项式）算法，事实上至今没有人发现过。

作为面试问题，我认为可以回答一个回溯算法。您可以添加一些小改进，例如如果您已经在棋盘上放置了(n-2)个皇后，则始终停止搜索。

有关算法的更多信息和伪代码以及更复杂的算法，建议阅读：

Fernau，H.（2010）。Queens的最小占主集：一个微不足道的编程练习？Discrete Applied Mathematics，158（4），308-318。 http://www.sciencedirect.com/science/article/pii/S0166218X09003722

- user1470500

---

有趣的是，我把问题看作一个集合覆盖问题（每个皇后覆盖一组位置），而不是一个支配集问题，但我真的很喜欢这种设置和方法！ - templatetypedef

如果n是二进制的，那么我不知道任何论据表明问题应该在DSPACE(O(2^(input_length)))中。如果n是一元，那么该问题存在一个FP/poly算法（只需硬编码解决方案），因此该问题不太可能是NP难的。 - user380772

经过更深入的思考，我同意你在这个特定问题上的一元 n 问题不太可能是 NP-Hard。我会编辑答案以反映这一点。 - user1470500

Answer 2

最简单的方法可能是用1、2、3...皇后进行穷举搜索，直到找到一个解决方案。如果考虑到棋盘的对称性，你只需要大约10^6次搜索来确认4个皇后是不够的（在那时，你可以使用相同的搜索直到找到5个皇后的解决方案，或者使用贪婪算法更快地找到一个解决方案）。

- Penguino