majer 发表于 2021-9-23 15:55:16

n皇后问题几乎被完全解决了

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

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

https://arxiv.org/pdf/2107.13460.pdf

ejsoon 发表于 2021-9-23 18:16:34

那麼結論是甚麼？比如五個皇后，怎麼擺可以保證先手必勝？

xiaoshuchong 发表于 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种
页: [1]
查看完整版本: n皇后问题几乎被完全解决了