【翻译】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 编辑 ]

shifujun

其实俺昨天晚上就翻译完了，就是没搞定排版的问题。

kattokid

好像是不是有人先你一步了？用的是穷举法？

[ 本帖最后由 kattokid 于 2010-8-10 22:58 编辑 ]

shifujun

确实是穷举了，48同态算1个，还有我听不懂的集合覆盖，通过这两个手段减少了一部分状态。其余状态都穷举了。

黑白子

妙！两幅图案都是24步。

wyn1992

翻译得很好，我算明白一点上帝之数的算法了

shifujun

原帖由 黑白子 于 2010-8-10 23:10 发表
妙！两幅图案都是24步。

那个原网页实际只是想展示一下打乱是什么样子的，没想贴出来20步的还原步骤。

xty_90

无奈飘过。。。。。。。。。。。

firstjasmines

这……很尴尬一不小心抢了你的风头……
讨论两个翻译问题吧：
A History of God's Number，那段第一句：
By 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions.
这句话，18被确定为上帝之数的下限然后by后面的内容我其实没看懂，“the number of effectively distinct move sequences of 17 or fewer moves”，还有 “there were fewer such sequences than Cube positions”是什么意思。
还有，
Symmetry，那一段中间一句：
There are 24 different ways you can orient the Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving
这句话意思我大概看懂了，但是and后面的语法结构我没搞明白。
这两处你是怎么理解的，望指教。

42752277

怎么又变成20了，不是17吗、？？？