<分区>
这是 Elements of Programming Interviews 的变体问题，没有解决方案。
您如何计算可以放置的最少数量的皇后来攻击每个未覆盖的方 block ？
<分区>
这是 Elements of Programming Interviews 的变体问题，没有解决方案。
您如何计算可以放置的最少数量的皇后来攻击每个未覆盖的方 block ？
最佳答案
问题是关于在图中找到最小支配集(在你的例子中是皇后图 http://mathworld.wolfram.com/QueenGraph.html )，这个更普遍的问题是 NP-Hard。即使这种减少(在这种特定类型的图上)不太可能是 NP-Hard，您可能会期望找不到任何有效的(多项式)算法，实际上直到今天还没有人找到。
作为面试问题，我认为可以接受的答案是回溯算法。如果您已经将 (n-2) 个皇后放在棋盘上，您可以添加一些小的改进，比如总是停止搜索。
有关算法的更多信息和伪代码以及更复杂的算法，我建议阅读:
Fernau, H. (2010)。最小支配皇后集:一个简单的编程练习？。离散应用数学，158(4)，308-318。 http://www.sciencedirect.com/science/article/pii/S0166218X09003722
关于algorithm - 您如何计算可以放置的最小数量的皇后来攻击每个未覆盖的方格？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39196741/