哈佛数学家解决了一个具有150年历史的史诗般的国际象棋问题

好蛋

哈佛数学家解决了一个具有150年历史的史诗般的国际象棋问题
来源：科技领航人
发布时间: 2022-01-27 14:13

　　在一个层面上，国际象棋似乎是一个简单的游戏：64个单独的黑色或白色方块，每边 16 个棋子，两个竞争者为征服而奋斗。
　　不过，再深入一点，这款游戏提供了极其复杂的可能性，对国际象棋理论家和数学家提出了几十年甚至几个世纪都无法解决的挑战。
　　2021年7月，一个这样的挑战终于得到了解决——至少在一定程度上是这样。来自马萨诸塞州哈佛大学的数学家迈克尔·西姆金 (Michael Simkin) 将注意力放在了自 19世纪40年代首次出现以来一直困扰专家的 n-皇后（n-queen）问题上。
　　如果你了解国际象棋，你就会知道皇后是棋盘上最强大的棋子，能够在任何方向移动任意数量的方格。n-皇后问题是这样问的：在一定数量的皇后 (n) 的情况下，如果皇后之间的距离足够远，以至于它们中的任何一个都不能接受其他任何一个，那么有多少种安排是可能的？
　　对于标准 8 x 8 棋盘上的8个皇后，答案是92，尽管其中大多数只是12个基本解的旋转或反映变体。
　　但是1,000 x 1,000方格的棋盘上有1,000个皇后呢？一百万皇后呢？西姆金对该问题的近似解是 (0.143n)n——皇后的数量乘以 0.143，提高到 n 次方。
　　你剩下的不是准确的答案，但它现在尽可能接近。有一百万个皇后，这个数字是一个后面有500万个数字的数字——所以我们不会在这里为你复制它。
　　西姆金花了将近5年的时间才提出这个方程式，使用了各种方法和技术，并且在解决问题的过程中遇到了一些障碍。最终，数学家能够使用不同的方法计算可能解的下限和上限，发现它们几乎匹配。
　　“如果你告诉我我希望你以这样那样的方式将你的皇后放在棋盘上，那么我将能够分析算法并告诉你有多少解决方案符合这个约束，”西姆金说，“在形式上，它将问题简化为优化问题。”
　　早期，苏黎世瑞士联邦理工学院的西姆金和同事祖鲁里亚（Zur Luria）合作研究了一种称为环面或模数问题的n皇后问题的变体。例如，在这幅图中，对角线环绕着棋盘，因此皇后可以从棋盘的右边缘对角移动并重新出现在左边。
　　这赋予了每个皇后的攻击对称性，但这不是普通棋盘的工作方式：棋盘角落的皇后没有中央的攻角那么多。
　　最终，两人在环形问题上的工作停滞不前（尽管他们发表了一些结果），但 Simkin 最终将这项工作的一些成果应用到了他的最终解决方案中。
　　随着棋盘变大和皇后数量的增加，研究表明，在大多数允许的配置中，皇后倾向于聚集在棋盘的两侧，中间的皇后数量较少，它们容易受到攻击。这种知识可以实现更加权的方法。
　　从理论上讲，n-皇后谜题的更精确答案应该是可能的——但西姆金比以往任何时候都更接近我们，他很高兴将挑战传递给其他人以进一步研究。
　　“我认为我个人可能会在一段时间内完成n-皇后问题，不是因为没有更多的事情要做，而是因为我一直梦想着国际象棋，我已经准备好继续前进了我的生活，”西姆金说。
　　西姆金关于解决方案的论文可在预印本服务器 arXiv 上找到。