数学研发论坛

 找回密码
 欢迎注册
查看: 659|回复: 3

[分享] n皇后问题几乎被完全解决了

[复制链接]
发表于 2021-9-23 15:55:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
哈佛大学数学科学与应用中心的博士后Michael Simkin,在7月发表的论文中几乎完全解决了n皇后问题。他借助熵法,得到了非常接近的上下限,进而得到最好的用n表示的估算公式。未来或许可以在他的表达式后面加个高阶余项,让表达式更精确点,但基本上都是同一层面的东西了。除非未来找到了用n表述的分析解,才能算是更进一步的突破,但这个直觉上应不存在。

另外,他的方法相当于把随机贪婪算法拓展到不对称的应用场景,或许可以给其它组合计算问题带来启发。

https://arxiv.org/pdf/2107.13460.pdf
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-9-23 18:16:34 | 显示全部楼层
那麼結論是甚麼?比如五個皇后,怎麼擺可以保證先手必勝?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-3-22 21:48:36 | 显示全部楼层
ejsoon 发表于 2021-9-23 18:16
那麼結論是甚麼?比如五個皇后,怎麼擺可以保證先手必勝?

两码事儿。 论文讲的是一个经典组合问题,n*n棋盘上如何放n个皇后使其两两之间不能被攻击到。n=8时,一共92种放法。论文里给出了一般的n放法数的渐进公式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-3-25 11:49:32 | 显示全部楼层
高中时候摆出了第一个63724815,然后编程找出全部92个,但是算上旋转翻转,其实只有23种
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-5-19 21:05 , Processed in 0.072571 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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