我不知道这个问题有没有研究过，只是在尝试一般的N-Queens问题时想到的。给定一个N*N棋盘，所需的最小皇后数是多少，当策略性地放置时，至少有一个皇后会攻击所有单元格。
我用笔和纸试了N= 3,4,5，我得到了2,3,4。答案总是如此N-1吗？有证据吗？其次，如果是这样，如何打印出该配置（如果可能有超过 1 个配置，则将它们全部打印出来）？
问问题
1340 次
2 回答
3
这个问题已经过研究，k皇后覆盖nxn网格的最小数量称为支配数。
第k一个n是
1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9
由OEIS给出。这意味着对于 8x8 棋盘，5 个皇后就足够了。
据推测，对于所有满足n=4m+1（例如 5,9,13...）的 n，2m+1皇后就足够了。Matthew D. Kearse 和 Peter B. Gibbons，“棋盘问题的计算方法和新结果”中介绍了这个和更多高级算法
于 2012-11-01T09:54:02.897 回答
2
好吧，它不是 N-2，因为 11x11 网格最多需要 8 个皇后（可能更少——这只是我手工找到的一个例子）：
于 2012-11-01T09:40:46.633 回答