恢复任意一个魔方的最少步数最多为多少？ - ClefRybak 的回答

数学, 计算机科学, 魔方, 组合数学（Combinatorics）, 数学难题, ClefRybak​

上帝之数：20

魔方在国际上开始销售是1980年的事，之后数学家就开始寻找这个所谓的上帝之数，不断压低上帝之数的上限。

15年后，在1995年，Michael Reid发现一类特殊的位置，即8个角全部正确，12个边位置全部正确但方向翻转的情况下，最少需要20步才能还原，因此确立了上帝之数的下限为20。他也在同时将上帝之数的上限下降到了29。

又过去15年，2010年，在Tomas Rokicki和其他研究者合作下将上帝之数的上限最终降到了20，从而彻底解决了这一问题。

Rokicki的解决方法相当暴力：

他们先将43,252,003,274,489,856,000种可能的情况利用群论分解为2,217,093,120组，每组19,508,428,800种情况。195亿种情况可以挤进现代电脑的内存中。

然后他们进一步用对称性将222亿组缩减到5588万组。

之后他们写了个程序，从每一种情况开始寻找最短解决路径。这个算法一开始每秒只能计算0.36种情况，如果按这个速度，那么每一组的195亿种情况需要1700多年才能全部枚举，因此他们进行了两点优化：

1 - 因为当时上帝之数的下限为20，所以他们在寻找最少步数时只需要找出任一长度不超过20的路径，而不需要找出最优解。这么一来速度一下子增加了1万倍，变成了每秒3900种情况。即使是如此每一组依然需要58天。

2 - 在分组时他们利用了数学群论中陪集的概念来巧妙分类，导致一个组里解决一种情况能够直接解决相关的大量情况，这么一来平均每秒解决的情况数一下子暴涨到10亿种，意味着每一组只需要约20秒就能完全解决。

即使如此，总共仍然有5588万组，如果20秒一组仍然会用上35年的时间。但是好在这是2010年，Rokicki利用了谷歌云计算分布到了大量电脑上并行计算最终解决了问题。

他们的代码收录在下列链接（Cube Programs）

二猹树: 🤔所以群论的一大用处就是用来剪枝？ (72 赞)

YH37 -> 二猹树: 😱😱

雨辰 -> YH37: 已经很妙了[滑稽] (3 赞)

Holy Chen -> 二猹树: cluster and prune

吴宇航 -> 二猹树: 魔方最少步比赛有种方法就叫降群法

寒山: 如果魔方一开始就是正的那岂不是一步都不用了[好奇] (5 赞)

寒山 -> 寒山: 魔方还原是不是有什么额外的约束定义

今天不用铁棍用电棍 -> 寒山: 最大需要最少多少步 (39 赞)

寒山 -> 今天不用铁棍用电棍: 明白了

寒山 -> 今天不用铁棍用电棍: 谢谢

寒山 -> 今天不用铁棍用电棍: [调皮][调皮]

骨骺线 -> 寒山: 说通俗一点就是：魔方随意一个状态，还原它最多不会超过20步，0步当然也在这个范围内 (2 赞)

Ashen Zhu: 暴力😂 (5 赞)

冽暮: 我靠，这样我也能搜[吃瓜] (4 赞)

flago: 谢谢你的答案，他们最后给出的结论是啥？

何者 -> flago: 开头第一句话即是结论 (16 赞)

忽如客行远 -> flago: "Rokicki的解决方法相当暴力："上面那段没看到吗 (3 赞)

萌萌哒小西瓜 -> flago: 最少20步可以还原任意魔方。 (1 赞)

胖胖小2 -> flago:

这篇论文的标题就是结论
god number is 20 (1 赞)

格物致知: 195亿种情况中步数最多的那种情况是多少步？😱 (2 赞)

安平 -> 格物致知: 不就是20步吗？ (18 赞)

失落: 感谢 (2 赞)

知乎用户: 可惜大学群论课都在摸鱼了

from: https://api.zhihu.com/appview/api/v4/answers/3163266029