150多年前的一局棋谜，几乎被破解了
150多年前的一局棋谜，几乎被破解了Original Takeko
原理 2022-01-30 20:30
https://mmbiz.qpic.cn/sz_mmbiz_jpg/tqOuxs8dsHOhrRpeda6Nuib350c2H7V008OW8nXic3Lb1Qp0nkicoQjK0WxymdGoGMfNkj50AkKzVROicOWZIAZ0NA/640?wx_fmt=jpeg
在国际象棋中，皇后可以说是棋盘上最强大的棋子之一。与其他任何棋子都不同，皇后可以任意在横、直、斜方向上移动，且格数不限。
https://mmbiz.qpic.cn/sz_mmbiz_gif/tqOuxs8dsHOhrRpeda6Nuib350c2H7V00dU140llI4ekFuc7RtiakFbNLnqreydKLVneVpib7MciaW6ELJzDE1EXGA/640?wx_fmt=gif国际象棋中皇后有很灵活的走法。| 图片来源：Alma Cebrian via Wiki under CC BY-SA
现在你可以想想这样一个问题：如果让你把8个皇后放在一个8×8格的标准棋盘上，有多少种排列方式，能让它们都无法在一招内攻击对方？
这也常被称为经典的八皇后问题。它于1848年最早出现在一本德国国际象棋杂志上。几年之后，人们找到了它的答案，是92种。
https://mmbiz.qpic.cn/sz_mmbiz_jpg/tqOuxs8dsHOhrRpeda6Nuib350c2H7V00fZCPicLLCEicQkRibDMwPPSbzy1Hp7JKf1H3VibjbcPaHiaanYIclg5AsEg/640?wx_fmt=jpeg八皇后问题的一种解法。| 图片设计：MJJ
1869年，八皇后问题的一个更广泛版本出现了。人们开始思考，如果是在一个更大的棋盘上放更多皇后的情况呢，比如，要想在一个1000×1000格的棋盘上放1000个皇后，甚至在一个100万×100万格的超大棋盘上放100万个皇后呢？
拓展后的n皇后问题可以被概括成，如果你想在一个n×n格的棋盘上放n个皇后，有多少种排列能让它们彼此之间无法在一招里攻击对方？
直到去年年底，一位数学家提供了一个几乎确定的答案。哈佛大学数学家迈克尔·西姆金（Michael Simkin）计算出，有大约(0.143n)ⁿ种方法放置皇后，能让它们在n×n格的棋盘上无法互相攻击。
n皇后问题的“问题”
在之前试图解决n皇后问题的尝试中，许多采用了计算机模拟来“猜”到答案。而西姆金希望回归数学去证明它。
解决n皇后问题的一大障碍是，没有一种显而易见的简化方式。即使在一个相对有限的棋盘、棋子数量较少（也就是n较小）的情况下，皇后的潜在排列方法的数量也很大，更不用说一张巨大的棋盘了。
在这种情况下，数学家往往希望找到一些潜在的模式或结构，把计算分解成更容易处理的小块。
但对n皇后问题而言，似乎并不存在任何结构。这是因为，棋盘上并非所有空间都是同等的。
想要直观理解这一点，我们可以再回头看一眼八皇后问题。如果你把第一个皇后放在了中心附近的位置，它可以攻击所在行、列或者两条很长的两条对角线的空间，也就是说，你的下一个皇后有了27格空间的禁区。
https://mmbiz.qpic.cn/sz_mmbiz_jpg/tqOuxs8dsHOhrRpeda6Nuib350c2H7V00xwCxll9BhIZn42KUWo0ibaZ0yA2UuIXWUW1nY88hXxVPe6x2SxJZabg/640?wx_fmt=jpeg将第一个皇后（图中红色）放在棋盘靠近中间位置时，会给下一个皇后带来27个位置禁区（图中绿色）。| 图片设计：MJJ
但是如果你把你的第一个皇后放在棋盘的边缘，它只会威胁到21格空间。
https://mmbiz.qpic.cn/sz_mmbiz_jpg/tqOuxs8dsHOhrRpeda6Nuib350c2H7V00jHtV8gibcgNBAGunOdV2Gb9mgOzUBenoOKia4AlGtUWQnoO5RmdVow6Q/640?wx_fmt=jpeg将第一个皇后（图中红色）放在棋盘旁边位置时，下一个皇后的禁区只有21格（图中绿色）。| 图片设计：MJJ
换句话说，中间和边缘的位置并不是同等的，棋盘因此少了一种能让问题变得简单的对称结构。
几年前，西姆金访问了苏黎世联邦理工学院的数学家和国际象棋奇才祖尔·卢里亚（Zur Luria）。他们决定首先开始研究一种更简单的对称超环面n皇后问题，在这个简化版本中，棋盘像一个环面一样在边缘“卷起来”。可以这么理解，如果你从右侧掉出了棋盘，实际上是掉到了左侧。
他们两人合作并开发了新的技术，尽管最后没有得到确切的答案，但西姆金从中获得了一定累积。
随后，他继续回归经典版本的问题中。他的最终方程并没有提供准确的答案，而是简单地说，这个数字是你目前能得到的最接近实际数字的一个。0.143代表了变量可能结果的平均不确定性水平，它乘以n，然后提高到n的幂次，就得到了答案。这一计算其实非常惊人，可以简单试一试，如果n是100万，结果的数字将包含500万位。
他能通过理解大量皇后在这些巨大的棋盘上如何分布的基本模式，比如它们是集中在中间，还是在边缘，然后应用众所周知的数学技术和算法来得到了这个解。从形式上来说，他将问题简化成了一个优化问题。
通过关注那些更有可能被占据的位置，西姆金算出了在棋盘的每个部分会有多少个皇后，并想出了一个公式来获得有效的配置数量。计算的结果就是所谓的下界，即可能配置的最小数量。有了这个数字之后，他用一种被称为熵方法的策略来寻找上界，也就是可能配置的最大数量。
最后发现，下界的答案几乎与上界答案完全吻合。简单地说，它表明，确切答案应该是夹在两个界限之间的一个相对较小的数学空间里的，也就是大约(0.143n)ⁿ种方法。
耐心和毅力的考验
西姆金对n皇后问题的研究已经差不多有5年时间，他表示，这是一项耐心和毅力的考验。
但他之所以对这个问题非常感兴趣，是因为它可以在被称为组合学的数学领域发挥应用，组合学这一领域着重在计数以及选择和排列问题上。
西姆金曾表示，他本人是一位非常糟糕的棋手。他说：“我还是非常喜欢下棋的挑战，但我想数学似乎更‘宽容’。”
#创作团队：
撰文：Takeko排版：雯雯
#参考来源：
https://news.harvard.edu/gazette/story/2022/01/harvard-mathematician-answers-150-year-old-chess-problem/https://www.quantamagazine.org/mathematician-answers-chess-problem-about-attacking-queens-20210921/http://www.math.utah.edu/~alfeld/queens/queens.html#图片来源：
封面图：Pixabay首图：Pixabay
页:
[1]