【翻译】20步可还原任意状态魔方

shifujun

原文：www.cube20.org
__________________________________________________

上帝之数是20

	3×3×3魔方的每一个状态都可以在20步以内还原。 通过由Google贡献的大约时长35年的CPU空闲时间，一个研究团队已经根本地（essentially）解决3×3×3魔方的每一个状态，并进一步提出没有状态需要超过20步还原。 每一个状态都用一个有着一连串步骤的算法解决。这用的算法可能用一连串的步骤解决顶层，然后用另一串步骤解决中间的边块，然后是类似的步骤。我们知道很多不同的算法，它们在复杂度和所需步数上有所不同，但是那些可以被人类记忆的方法通常要超过40步。
Superflip,第一个被证明最少需要20步还原的状态。	有人可能猜测上帝用的算法更高效，总是用最少的步骤解决；这被称作"上帝算法"（God's Algorithm）。这个算法在解决最复杂的魔方状态时所用的步数称作"上帝之数"。终于，上帝之数被证明是20了。 从有魔方以来，人们花了15年时间才找到第一个被证明至少需要20步才能还原的状态；在那之后，我们又花了将近15年证明了20步可以解决所有的状态。

上帝之数的历史
到1980年，通过分析小于等于17步的有效不同转动得到的状态数，发现这个数字小于3×3×3魔方的状态数，所以上帝之数的下界被确定为18。由早期的魔方解决方法小册子的算法来看，第一个上帝之数的上界大概在80左右。这个表格统计了随后的成果。

日期	下界	上界	范围	摘要和链接
1981年7月	18	52	34	Morwen Thistlethwaite 证明 52 步足够了。
1992年4月	18	42	24	Hans Kloosterman把它改善到 42步 。
1992年5月	18	39	21	Michael Reid 证明 39 步总是足够的。
1992年5月	18	37	19	Dik Winter 一天之后就把它降低到 37 步 。
1995年1月	18	29	11	Michael Reid在分析完Kociemba's two-phase algorithm后把上界减少到29 步。
1995年1月	20	29	9	Michael Reid 证明 ''superflip'' 状态(角块全正确, 棱块全部原地翻转) 需要 20 步。
2005年12月	20	28	8	Silviu Radu 证明 28 步 总是足够的。
2006年4月	20	27	7	Silviu Radu 改善他得到的上界到 27 步。
2007年5月	20	26	6	Dan Kunkle 和 Gene Cooperman 证明 26 步是足够的。
2008年3月	20	25	5	Tomas Rokicki 把上界减少到 25 步。
2008年4月	20	23	3	Tomas Rokicki 和 John Welborn 把它减少到只有 23 步。
2008年8月	20	22	2	Tomas Rokicki 和 John Welborn 把它继续减少到 22 步。
2010年7月	20	20	0	Morley Davidson, John Dethridge, Herbert Kociemba, 和 Tomas Rokicki 四人证明了上帝之数确切的是20步。

  我们是如何做的我们如何解决全部43,252,003,274,489,856,000种状态的？

• 我们把状态分成2,217,093,120个集合，每个集合有19,508,428,800种状态。
• 我们通过对称性和集合覆盖把要解决的集合数减少到55,882,296个。
• 我们并没有找到每个状态的最小步，但是我们找到了小于等于20步的解法。
• 我们写个一个可以在大约20秒解决一个集合的程序。
• 我们用了大约35个CPU年解决了这55,882,296个集合里的所有状态。

分区法
我们将这个大问题化为2,217,093,120个小问题，每个问题由19,508,428,800个不同的状态组成。每个子问题都足够小到可以用一台流行配置的电脑解决，我们分解问题的方法（数学上，运用{U,F2,R2,D,B2,L2}生成的群的陪集(coset)，简单的说就是H的陪集）使得我们可以非常快速的解决每一个集合。
对称性
如果你拿一个混乱的魔方，把它上下颠倒一下，这样你不会把它变得更难还原；它还是需要同样的步数还原。还原这两个状态，你可以只还原其中一个状态，然后把解决方法也上下颠倒一下就可以还原另一个状态了。一个魔方在空间中有24种不同的摆放方法，通过镜像可以得到2种对称状态，所以总共可以减少48倍需要还原的状态。运用类似对称论证和找到一个解决到一个大的"集合覆盖（set cover）"问题的方法，我们能把要解决的集合数从2,217,093,120减少到55,882,296。
好方法和最优方法

随机状态 H的陪集 最优化 0.36 2,000,000 20步或更少 3,900 1,000,000,000	一个最优方法不需要比还原必要的步数多的步数还原。自从发现了一个还原必要步数是20步的状态，我们就不需要用最优方法解决每一个状态了；我们只需要找到一个小于等于20步的方法还原每一个状态。这要简单相当多；左边的表格显示了一个配置较好的台式电脑解决随机状态时的速度。
解决速度，状态数/秒	快速陪集求解程序运用数学技巧和精心编程的结合，我们能在一台台式机上以左边表格里写的速度解决完整的H的陪集，得到最优方法或者小于等于20步的方法。

   大量的电脑最终，我们能将这55,882,296个H的陪集分派到Google的大量的电脑上，并在几个星期内完成计算。Google没有公布它的电脑系统信息，但是这将会花费一台配置较好的台式机(Intel Nehalem, 四核, 2.8GHz) 11亿秒，即35个CPU年，去完成这个计算。
最难的状态是什么？

我们知道有些状态最少需要20步还原已经15年了；我们刚刚证明了没有状态需要更多的步数。 最少步需要20步的状态既罕见又丰富；它们罕见是因为它们只有全部状态的十亿分之一，然而很可能有超过一亿个这样的状态。我们还不能确切的知道它们到底有多少。这张右边的表格给出了每个最小步数所包含的状态数。对于大于等于16步的情况，只能给出一个估值。我们的研究已经确认前面的结果，从0到14，15步的结果是一个新成果。我们希望月内能有另外的研究者独立确认这个结果。 到目前为止我们已经发现了大约2000万个最小步20步的状态。下面的状态曾是我们的程序遇到的最难解决的状态：	最小步数 状态数量 0 1 1 18 2 243 3 3,240 4 43,239 5 574,908 6 7,618,438 7 100,803,036 8 1,332,343,288 9 17,596,479,795 10 232,248,063,316 11 3,063,288,809,012 12 40,374,425,656,248 13 531,653,418,284,628 14 6,989,320,578,825,358 15 91,365,146,187,124,313 16 大约 1,100,000,000,000,000,000 17 大约 12,000,000,000,000,000,000 18 大约 29,000,000,000,000,000,000 19 大约 1,500,000,000,000,000,000 20 大约 300,000,000
联系我们 我们的团队由这些人组成： Morley Davidson，肯特州立大学的数学家 John Dethridge，Google总部加利福尼亚州山景城的工程师 Herbert Kociemba，德国达姆施塔特的数学老师 Tomas Rokicki，美国加利福尼亚州帕罗奥图市的程序员 我们的Email是： rokicki@gmail.com davidson@math.kent.edu Rubik's Cube是Seven Towns, Ltd的注册商标。 感谢Werner Randelshofer为此页面提供的魔方展示插件。

------------------------------------------------------------------------------------

[ 本帖最后由 shifujun 于 2010-8-11 20:39 编辑 ]

李老豆

平均的话应该是15步左右吧，那么最少步WR总有一天会达到这个极限的

PTSD龌龊闵

我相信总有一天，WCA上会有人用上帝解法快乐地二速三速三盲三单三脚

qq543450409

好厉害的样子，我现在一分钟才能解开一个

younkee

太强大了，无敌了。。。

深圳老钓

最小步数        状态数量
0        1
1        18
2        243
3        3,240
4        43,239
5        574,908
6        7,618,438
7        100,803,036
8        1,332,343,288
9        17,596,479,795
10        232,248,063,316
11        3,063,288,809,012
12        40,374,425,656,248
13        531,653,418,284,628
14        6,989,320,578,825,358
15        91,365,146,187,124,313
16        大约 1,100,000,000,000,000,000
17        大约 12,000,000,000,000,000,000
18        大约 29,000,000,000,000,000,000
19        大约 1,500,000,000,000,000,000
20        大约 300,000,000

黑白子

关于最少步有什么新消息吗？

黑白子

ggglgq 发表于 2013-9-5 20:09
　　
　　
  

在计算机间接证明20步之前，数学家就用群论理论估计出三阶魔方最少步是22步或23步。

没有群论理论，计算机无法间接证明。问题是谁能保证计算机在整个证明过程中不出错？也可能真的没出错，也可能出错了但不影响结果。

相比结果而言，我更关注证明过程！计算机的结果只比群论理论少了2-3步，没什么了不起！很多计算机专家之所以没能解决这一问题，就是因为没有那么强大计算能力的计算机而已，现在，我们不是也没法复验吗？

倒是长期从事这一工作的科学家（包括数学家、程序员和魔方爱好者）更值得人们尊重！

对一个问题出现不同观点产生争论是正常的，以后还可能发生多次！直到问题得到解决。

来到论坛就是来讨论问题的。我们过去、现在合作的就很愉快！今后还是很愉快！像我们这样有话直说比欲言又止好的多！

ggglgq

　　
　　
  
    嗯，“怀疑”起码也得有个“怀疑”的方向吧？！
  
    我想，泛泛地“怀疑”也没有实际意义吧？！ 也就是：“怀疑”不如“行动”，或者“怀疑”不如“实证”。
  
    我想说，希望我们就事论事，不要参杂感情成分。对于 黑白子 的探索精神，我是非常欣赏的，但我更注重
  
“实证”，而非“空口无凭”。
  
    同时 更希望 日后合作愉快！  
   
  
    顺便说一下，我的英语很烂。对于诸如 正六面体三阶魔方 上帝之数 的英文资料也仅仅是能凑合着看，对于
  
里面的术语也不知道怎么翻译为好。有需要这方面资料的，请另找高人。  比如：
  
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__The_real_size_of_cube_space.html
　　
　　
　　

黑白子

ggglgq 发表于 2013-9-5 12:56
　　
　　
  

1、请版主先介绍一下有关三阶魔方最少步这方面的详细资料，好让我明白其中的道理。
2、“    楼上如果有“反证”，请“明示”！  否则 ......   
  
    为人不要“多疑”，而应“多思”。多年来有很多科研人员（包括很多优秀程序员）花费了大量辛血，
  
才把 正六面体三阶魔方 的 上帝之数 从 22 ～23 步直升到 20 步，楼上知道吗？ 这绝不是楼上随便一句
  
“电脑真的证明了吗？程序不会出错吗？”  能怀疑的了的。”这段话不好，请三思。
3、“否则……”之后的省略号想说什么，直接说出来好了。
4、“多年来有很多科研人员（包括很多优秀程序员）花费了大量辛血，才把 正六面体三阶魔方 的 上帝之数 从 22 ～23 步直升到 20 步”，应该是直降到20步。
5、怀疑是“多思”的结果，不是人云亦云。
6、我为什么有疑问，那是因为计算机并未遍历所有状态，况且也没有复验。
7、怀疑不等于事实，真理不怕检验，实践是检验真理的唯一标准！