设为首页收藏本站

弧论坛

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1143|回复: 0

150多年前的一局棋谜,几乎被破解了

[复制链接]

5904

主题

6599

帖子

7159

积分

坛主

Rank: 10Rank: 10Rank: 10

积分
7159
发表于 2022-1-31 02:31 | 显示全部楼层 |阅读模式
150多年前的一局棋谜,几乎被破解了[color=rgba(0, 0, 0, 0.3)]

[color=rgba(0, 0, 0, 0.3)]Original [color=rgba(0, 0, 0, 0.3)]Takeko
原理 [color=rgba(0, 0, 0, 0.3)]2022-01-30 20:30
[color=rgba(0, 0, 0, 0.3)]


                               
登录/注册后可看大图


在国际象棋中,皇后可以说是棋盘上最强大的棋子之一。与其他任何棋子都不同,皇后可以任意在横、直、斜方向上移动,且格数不限


                               
登录/注册后可看大图
国际象棋中皇后有很灵活的走法。| 图片来源:Alma Cebrian via Wiki under CC BY-SA

现在你可以想想这样一个问题:如果让你把8个皇后放在一个8×8格的标准棋盘上,有多少种排列方式,能让它们都无法在一招内攻击对方?

这也常被称为经典的八皇后问。它于1848年最早出现在一本德国国际象棋杂志上。几年之后,人们找到了它的答案,是92种


                               
登录/注册后可看大图
八皇后问题的一种解法。| 图片设计:MJJ

1869年,八皇后问题的一个更广泛版本出现了。人们开始思考,如果是在一个更大的棋盘上放更多皇后的情况呢,比如,要想在一个1000×1000格的棋盘上放1000个皇后,甚至在一个100万×100万格的超大棋盘上放100万个皇后呢?

拓展后的n皇后问题可以被概括成,如果你想在一个n×n格的棋盘上放n个皇后,有多少种排列能让它们彼此之间无法在一招里攻击对方?

直到去年年底,一位数学家提供了一个几乎确定的答案。哈佛大学数学家迈克尔·西姆金(Michael Simkin)计算出,有大约(0.143n)ⁿ种方法放置皇后,能让它们在n×n格的棋盘上无法互相攻击。


  n皇后问题的“问题”  

在之前试图解决n皇后问题的尝试中,许多采用了计算机模拟来“猜”到答案。而西姆金希望回归数学去证明它。

解决n皇后问题的一大障碍是,没有一种显而易见的简化方式。即使在一个相对有限的棋盘、棋子数量较少(也就是n较小)的情况下,皇后的潜在排列方法的数量也很大,更不用说一张巨大的棋盘了。

在这种情况下,数学家往往希望找到一些潜在的模式或结构,把计算分解成更容易处理的小块。

但对n皇后问题而言,似乎并不存在任何结构。这是因为,棋盘上并非所有空间都是同等的。

想要直观理解这一点,我们可以再回头看一眼八皇后问题。如果你把第一个皇后放在了中心附近的位置,它可以攻击所在行、列或者两条很长的两条对角线的空间,也就是说,你的下一个皇后有了27格空间的禁区


                               
登录/注册后可看大图
将第一个皇后(图中红色)放在棋盘靠近中间位置时,会给下一个皇后带来27个位置禁区(图中绿色)。| 图片设计:MJJ

但是如果你把你的第一个皇后放在棋盘的边缘,它只会威胁到21格空间


                               
登录/注册后可看大图
将第一个皇后(图中红色)放在棋盘旁边位置时,下一个皇后的禁区只有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


大道至简 万物于弧
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|Archiver|小黑屋|国际弧学研究会    

GMT-7, 2024-3-28 09:43 , Processed in 0.995368 second(s), 23 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表