数学家基本上解决了N皇后问题

你听说过古老而又著名的8皇后(8-queens)问题吗？

它已有150多年的历史。它的进阶版本就是所谓的n-queens问题。现在，哈佛大学数学科学与应用中心的博士后Michael Simkin，在7月发表的论文中几乎完全解决了后一问题。

8皇后问题，就是在国际象棋棋盘上，摆放8个皇后，保证她们无法攻击到彼此，问有多少种摆放方法？如果你想知道答案的话，我悄悄告诉你：92种。

所谓的n皇后问题，就是在n×n的棋盘上摆放n个皇后，用n表示出可能的摆法数目。

Simkin证明，对于巨大的棋盘，大约有(0.143n)^n种配置。因此，在一个百万×百万的棋盘上，安排100万个皇后的方法估计数目是，前面一个1，后面跟500万个零。

著名的8皇后问题最早出现在1848年的一份德国国际象棋杂志上。到1869年，n-queens问题也随之出现。从那时起，数学家们在n-queens问题上产生了一系列的结果。尽管之前的研究人员用计算机数值模拟出Simkin的结果，但他是第一个真正证明它的人。

解决n-queens问题的一个障碍是，没有明显的方法来简化它。即使在一个相对较小的棋盘上，皇后的潜在排列数量也是巨大的。在一个更大的棋盘上，所涉及的计算量是惊人的。在这种情况下，数学家往往希望找到一些潜在的模式或结构，让他们把计算分解成更容易处理的小块。但是n-queens问题似乎没有任何模式。

这源于如下事实：棋盘上的所有位置并非都是平等的。

比如说，棋盘中间的皇后，可以把更多位置置于自己的攻击范围内。而角落里的皇后则威慑力减半。

这一事实导致四年前Simkin访问瑞士联邦理工学院苏黎世分校的数学家Zur Luria，合作研究该问题时，决定在更加对称的 "环形棋盘" 上探索答案。

他们的策略被称为随机贪婪算法，它已被用于解决组合学领域的许多其他问题。

环形棋盘的对称性给了Simkin他们一个立足点。但环形棋盘以自由换取对称性，最终也使他们遭遇瓶颈。

现实里的国际象棋棋盘的角落原来真的很有价值

Simkin和Luria在环形问题上最终停滞不前，因为他们无法为特定配置中的最后几个皇后找到空间。碰壁之后，他们转而研究其他项目。但最终，Simkin认识到，在环形棋盘上失败的方法实际上很适合 普通棋盘。

"在我们放弃它的两、三年后，我突然意识到，对于经典问题，反而要容易得多。"辛金说。

他们经过逐步调整，使皇后的数量达到上限。

莫纳什大学的Nick Wormald解释说："你可以随便移动几个皇后，把两个新皇后塞进去，然后把一个旧皇后拿出来。”

但是，经典问题中缺乏对称性，确实让研究人员吃了大亏。随机贪婪算法对棋盘上的每一个空间都一视同仁，最适合于高度对称的问题。当皇后被随机放置在标准棋盘上时，该算法并不区分中心和边角。

由于这一限制，Simkin和Luria最终只改进了问题的已知下限。他们在去年5月公布了他们的结果。

但Simkin之后一直在思考这个问题，甚至在去年秋天他在耶路撒冷希伯来大学完成博士学业后从以色列搬到波士顿。最终，他突然意识到，他可以将随机贪婪算法改造成适应于标准n乘n棋盘的不对称环境。他的关键思想是，在N个皇后的配置中，皇后占据某些方格的可能性远远大于其他方格，因此，Simkin和Luria曾经的策略，即以相同的可能性选择每一个空间，是没有意义的。

"我意识到你实际上可以利用不对称性来发挥你的优势。”

因为棋盘中间的皇后攻击的空间最多，所以大多数配置的棋盘边上的皇后比靠近中心的多。一旦棋盘每边有甚至100个左右的空间，辛金发现这些效应开始压倒其他可能性。几乎所有的配置都以一种特定的方式分布皇后，靠近棋盘中央的皇后较少，而沿边的皇后较多。Simkin只需要弄清楚在随机分配皇后时给每个方块分配的确切权重。

为了大致了解皇后的排列方式，Simkin将N乘N的棋盘分成若干部分，每个部分由数千个方块组成。然后，他不再明确具体哪些地方有皇后，而是着眼于大局。每个部分可有多少个皇后？

一旦他想出了如何按区域分配皇后，他就回到了之前使用过的技术。只是这一次他可以更精确地应用它们。他不是完全随机地放下棋子，而是选择棋子较多的地方。这使他能够确定一个有效配置的下限。

最后，他通过使用被称为熵法的策略，证明这个公式不仅仅是一个最小值——它几乎就是精确值。

想象一下，你有一个有效的n-queens配置，而你想与别人分享它。如果对方大致知道一个配置是什么样子的，你还需要分享多少信息，他们才能精确地重建它？

Simkin又计算出一个上限。这个最大值与最小值几乎完全吻合，使Simkin得出结论，他几乎准确地确定了n皇后的答案。他的证明为这一经典问题带来了长期追求的清晰性。

论文中的技术可能对其他问题也有用。事实上，上周牛津大学的Candida Bowtell和Peter Keevash用类似的想法找到了环形n-queens问题的类似解决方案。后一论文新鲜出炉，还没有被完全审查。而且在组合学中还有许多其他的开放性问题可以从辛金的想法中受益。

"有趣的是方法，我们一直在寻找使工具更强大的手段。我希望我已经成功地做到了这一点。"

https://www.quantamagazine.org/mathematician-answers-chess-problem-about-attacking-queens-20210921/

https://arxiv.org/pdf/2107.13460.pdf