科学家15年证明还原任意魔方最多需20步

（转自：新浪科技，彬彬)

　

据国外媒体报道，相信许多人都玩过魔方，但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家（Morley Davidson, John Dethridge, Herbert Kociemba, 和Tomas Rokicki），近日利用计算机破解了这一谜团，他们证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20(God's Number is 20)。

这支研究团队位于美国加利福尼亚州帕洛阿尔托市。科学家们通过计算机计算和证明，任意组合的魔方都可以在20步内还原。这一结果表明，大约有10万多种的起始状态恰好可以在20步内还原。

利用谷歌公司计算机强大的计算能力，研究人员检验了魔方任何可能的混乱状态(确切数字为43,252,003,274,489,856,000约合4.3×10¹⁹)。美国俄亥俄州肯特州立大学数学家莫雷-戴维德森教授也是研究人员之一，他表示，“我们现在可以肯定，这个‘上帝之数’就是20。对于我来说，我也回到了原地。魔方伴随着我成长，这也是我为什么深入研究这个数学问题的原因。这个谜团引起了人们的广泛关注，它也许是人类历史上最受欢迎的谜语了。”科学家们的初步研究成果发表于在线网站上，但戴维德森表示，他们准备将研究成果提交给杂志正式发表。

程序员托马斯-罗基花了15年的时间，致力于寻找这个谜团的答案。据罗基介绍，研究团队所采用的算法可以在1秒钟内尝试10亿种可能，此前的计算机算法1秒钟内只能处理4000种可能。

为了让问题简单化，研究团队采用了一种所谓“群论”的数学技术。他们首先将魔方所有可能的起始状态集分成22亿个集合，每个集合包含了195亿个可能的状态。集合的分配原则是这些可能的状态是如何应对一组10个可能的还原步骤。再通过魔方不同的对称性，这种分组技术使得研究团队将集合数减少到5600万个。

研究人员所采用的算法可以快速将这些还原步骤与恰当的起始点匹配起来，从而实现在20秒内处理一个集合中的195亿种可能。对于普通的家用电脑来说，以这样的速度完成整个处理任务需要大约35年时间。

2007年，《每日电讯报》曾经报道称，任意组合的魔方均可在26步内还原。当然，还有其他的报道称已证明出更少的还原步骤。魔方由匈牙利埃尔诺-鲁比克教授于1974年所发明，曾经是世界上最畅销的智力玩具。

相关内容：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. The first upper bound was probably around 80 or so from the algorithm in one of the early solution booklets. This table summarizes the subsequent results.

Date	Lower bound	Upper bound	Gap	Notes and Links
July, 1981	18	52	34	Morwen Thistlethwaite proves 52 moves suffice.
April, 1992	18	42	24	Hans Kloosterman improves this to 42 moves.
May, 1992	18	39	21	Michael Reid shows 39 moves is always sufficient.
May, 1992	18	37	19	Dik Winter lowers this to 37 moves just one day later!
January, 1995	18	29	11	Michael Reid cuts the upper bound to 29 moves by analyzing Kociemba's two-phase algorithm.
January, 1995	20	29	9	Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves.
December, 2005	20	28	8	Silviu Radu shows that 28 moves is always enough.
April, 2006	20	27	7	Silviu Radu improves his bound to 27 moves.
May, 2007	20	26	6	Dan Kunkle and Gene Cooperman prove 26 moves suffice.
March, 2008	20	25	5	Tomas Rokicki cuts the upper bound to 25 moves.
April, 2008	20	23	3	Tomas Rokicki and John Welborn reduce it to only 23 moves.
August, 2008	20	22	2	Tomas Rokicki and John Welborn continue down to 22 moves.
July, 2010	20	20	0	Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki prove that God's Number for the Cube is exactly 20.