世界上最诡异的象棋绝杀(一位哈佛数学家基本解决了一个有150年历史的国际象棋难题)

在某种程度上,国际象棋看起来像是一种简单的游戏:64个独立的黑白方块,每边16个棋子,两名竞争对手努力争取征服对方。

世界上最诡异的象棋绝杀(一位哈佛数学家基本解决了一个有150年历史的国际象棋难题)(1)

再深入一点,就会发现这个游戏提供了非常复杂的可能性,给国际象棋理论家和数学家带来了几十年甚至几百年都无法解决的挑战。

2021年7月,一个这样的挑战终于得到了解决 —— 至少在某种程度上是这样。来自马萨诸塞州哈佛大学的数学家迈克尔·西姆金(Michael Simkin)把注意力放在了“n个皇后”问题上,这个问题自19世纪40年代首次提出以来就一直困扰着专家。

如果你懂象棋,你就会知道皇后是棋盘上最强大的棋子,能够向任何方向移动任意数量的方块。n个皇后问题是这样问的:在n×n格的国际象棋上摆放n个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

对于标准的8 x 8棋盘上的8个皇后,答案是92,尽管其中大多数只是 12 个基本解的旋转或反映变体。

但是,如果在一个1000x1000的方块上有1000个皇后呢?那一百万个皇后呢?数学家迈克尔·西姆金对这个问题的近似解是(0.143n)n,即皇后的数量乘以0.143的n次方。

你得到的不是精确的答案,但它是目前可能得到的最接近的答案。如果有一百万个皇后,这个数字就会变成一个后面有五百万位数的数字,所以我们在这里就不复制了。

数学家迈克尔·西姆金花了将近5年的时间才提出了这个等式,使用了各种方法和技术,但在解决问题的过程中遇到了一些障碍。最终,这位数学家能够用不同的方法计算出可能解的下界和上界,发现它们几乎是一致的。

迈克尔·西姆金表示:“如果你告诉我,我想让你以这样或那样的方式把你的皇后放在棋盘上,那么我就能分析算法,告诉你有多少解决方案符合这个约束条件。在形式上,它将问题简化为优化问题。”

早些时候,西姆金和他的同事苏黎世联邦理工学院的祖尔·卢里亚合作研究了n-皇后问题的一种变体,称为环面问题或模块问题。称为环状问题或模数问题。例如,在这张图中,对角线环绕着棋盘,这样女王就可以从棋盘的右边缘沿对角线移动,重新出现在棋盘的左边。

这赋予了每个皇后对称的攻击,但这不是普通棋盘的工作方式:棋盘角落的皇后没有中心的皇后有那么多的攻角。

最终,他们在环面问题上的工作停滞了(尽管他们发表了一些结果),但西姆金最终将他们的一些成果应用到他的最终解决方案中。

随着棋盘变大,皇后的数量增加,研究表明,在大多数允许的配置中,皇后倾向于聚集在棋盘的两边,中间的皇后较少,在那里他们将暴露于攻击。这些知识使我们能够采取更有权威性的方法。

理论上,对于“n个皇后”这个谜题应该有一个更精确的答案 —— 但西姆金让我们比以往任何时候都更接近答案,他很乐意把这个挑战交给其他人进一步研究。

迈克尔·西姆金说道:“我认为我个人可能会在一段时间内完成 n个皇后问题,不是因为没有更多的事情要做,而是因为我一直梦想着下国际象棋,并且我已经准备好继续我的生活。”


如果朋友们喜欢,敬请关注“知新了了”!

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页