这是一道来自《编程面试要点》的变形题,无解答。
你如何计算最少需要放置多少个皇后才能攻击所有未被覆盖的方格?
这是一道来自《编程面试要点》的变形题,无解答。
你如何计算最少需要放置多少个皇后才能攻击所有未被覆盖的方格?
作为面试问题,我认为可以回答一个回溯算法。您可以添加一些小改进,例如如果您已经在棋盘上放置了(n-2)个皇后,则始终停止搜索。
有关算法的更多信息和伪代码以及更复杂的算法,建议阅读:
Fernau,H.(2010)。Queens的最小占主集:一个微不足道的编程练习?Discrete Applied Mathematics,158(4),308-318。 http://www.sciencedirect.com/science/article/pii/S0166218X09003722
最简单的方法可能是用1、2、3...皇后进行穷举搜索,直到找到一个解决方案。如果考虑到棋盘的对称性,你只需要大约10^6次搜索来确认4个皇后是不够的(在那时,你可以使用相同的搜索直到找到5个皇后的解决方案,或者使用贪婪算法更快地找到一个解决方案)。