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

科学家 15 年证明还原任意魔方最多需 20步魔方由匈牙利埃尔诺- 鲁比克教授于 1974 年所发明,曾经是世界上最畅销的智力玩具。据国外媒体报道, 相信许多人都玩过魔方, 但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年,这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家( 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 约合 × 10 19) 。美国俄亥俄州肯特州立大学数学家莫雷- 戴维德森教授也是研究人员之一,他表示, “我们现在可以肯定,这个‘上帝之数’就是 20 。对于我来说, 我也回到了原地。魔方伴随着我成长, 这也是我为什么深入研究这个数学问题的原因。这个谜团引起了人们的广泛关注,它也许是人类历史上最受欢迎的谜语了。”科学家们的初步研究成果发表于在线网站上, 但戴维德森表示, 他们准备将研究成果提交给杂志正式发表。程序员托马斯- 罗基花了 15 年的时间, 致力于寻找这个谜团的答案。据罗基介绍, 研究团队所采用的算法可以在 1 秒钟内尝试 10 亿种可能, 此前的计算机算法 1 秒钟内只能处理 400 0 种可能。为了让问题简单化, 研究团队采用了一种所谓“群论”的数学技术。他们首先将魔方所有可能的起始状态集分成 22 亿个集合,每个集合包含了 195 亿个可能的状态。集合的分配原则是这些可能的状态是如何应对一组 10 个可能的还原步骤。再通过魔方不同的对称性,这种分组技术使得研究团队将集合数减少到 5600 万个。研究人员所采用的算法可以快速将这些还原步骤与恰当的起始点匹配起来,从而实现在 20 秒内处理一个集合中的 195 亿种可能。对于普通的家用电脑来说, 以这样的速度完成整个处理任务需要大约 35 年时间。 2007 年, 《每日电讯报》曾经报道称,任意组合的魔方均可在 26 步内还原。当然,还有其他的报道称已证明出更少的还原步骤。 2008 年七月, 来自世界各地的很多最优秀的魔方玩家聚集在捷克共和国(Czech Republic) 中部的帕尔杜比采(Pardubice) , 参加魔方界的重要赛事: 捷克公开赛。在这次比赛上, 荷兰玩家阿克斯迪杰克(E. Akkersdijk) 创下了一个惊人的纪录: 只用 秒就复原一个颜色被彻底打乱的魔方。无独有偶, 在这一年的八月, 人们在研究魔方背后的数学问题上也取得了重要进展。在本文中, 我们就来介绍一下魔方以及它背后的数学问题。一. 风靡世界的玩具 1974 年春天, 匈牙利布达佩斯应用艺术学院(Budapest College of Applied