盡管有43,252,003,274,489,856,000（約合4.3×1019）種不同的可能組合狀態(tài)，但魔方都能在20步內(nèi)還原。

北京時(shí)間8月13日消息，據(jù)國外媒體報(bào)道，相信許多人都玩過魔方，但是此前沒有人知道任意組合的魔方的最小還原步數(shù)究竟是多少。這一問題困擾了數(shù)學(xué)家長達(dá)三十多年，這個(gè)最小還原步數(shù)也被稱為“上帝之?dāng)?shù)”。美國加利福尼亞州科學(xué)家近日利用計(jì)算機(jī)破解了這一謎團(tuán)，研究人員證明任意組合的魔方均可以在20步之內(nèi)還原，“上帝之?dāng)?shù)”正式定為20。

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

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

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

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

研究人員所采用的算法可以快速將這些還原步驟與恰當(dāng)?shù)钠鹗键c(diǎn)匹配起來，從而實(shí)現(xiàn)在20秒內(nèi)處理一個(gè)集合中的195億種可能。對于普通的家用電腦來說，以這樣的速度完成整個(gè)處理任務(wù)需要大約35年時(shí)間。

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

原文鏈接： http://tech.sina.com.cn/d/2010-08-13/07334540637.shtml

科學(xué)家15年證明還原任意魔方最多需20步