科學家證明:還原任意魔方最多只需要二十步

2010年08月13日09:30 | 中國發展門戶網 www.chinagate.cn | 給編輯寫信字號：T|T

關鍵詞：魔方科學家谷歌研究團隊研究人員上帝之數每日電訊報群論計算能力智力玩具

視頻播放位置

盡管擁有43,252,003,274,489,856,000種不同的可能組合狀態，但魔方都可以在20步內還原。

據國外媒體報道，相信許多人都玩過魔方，但是此前沒有人知道任意組合的魔方的最小還原步數究竟是多少。這一問題困擾了數學家長達三十多年，這個最小還原步數也被稱為“上帝之數”。美國加利福尼亞州科學家近日利用計算機破解了這一謎團，研究人員證明任意組合的魔方均可以在20步之內還原，“上帝之數”正式定為20。

這支研究團隊位于美國加利福尼亞州帕洛阿爾托市。科學家們通過計算機計算和證明，任意組合的魔方都可以在20步內還原。這一結果表明，大約有10萬多種的起始狀態恰好可以在20步內還原。

利用谷歌公司計算機強大的計算能力，研究人員檢驗了魔方任何可能的混亂狀態(確切數字為43,252,003,274,489,856,000)。美國俄亥俄州肯特州立大學數學家莫雷-戴維德森教授也是研究人員之一，他表示，“我們現在可以肯定，這個‘上帝之數’就是20。對于我來說，我也回到了原地。魔方伴隨著我成長，這也是我為什么深入研究這個數學問題的原因。這個謎團引起了人們的廣泛關注，它也許是人類歷史上最受歡迎的謎語了。”科學家們的初步研究成果發表于在線網站上，但戴維德森表示，他們準備將研究成果提交給雜志正式發表。

程序員托馬斯-羅基花了15年的時間，致力于尋找這個謎團的答案。據羅基介紹，研究團隊所采用的算法可以在1秒鐘內嘗試10億種可能，此前的計算機算法1秒鐘內只能處理4000種可能。

為了讓問題簡單化，研究團隊采用了一種所謂“群論”的數學技術。他們首先將魔方所有可能的起始狀態集分成22億個集合，每個集合包含了195億個可能的狀態。集合的分配原則是這些可能的狀態是如何應對一組10個可能的還原步驟。再通過魔方不同的對稱性，這種分組技術使得研究團隊將集合數減少到5600萬個。

研究人員所采用的算法可以快速將這些還原步驟與恰當的起始點匹配起來，從而實現在20秒內處理一個集合中的195億種可能。對于普通的家用電腦來說，以這樣的速度完成整個處理任務需要大約35年時間。

2007年，《每日電訊報》曾經報道稱，任意組合的魔方均可在26步內還原。當然，還有其他的報道稱已證明出更少的還原步驟。魔方由匈牙利埃爾諾-魯比克教授于1974年所發明，曾經是世界上最暢銷的智力玩具。