基本介紹
- 中文名：魔方還原步數
- 最少步數：20.
- 證明時間：2010年
- 魔方發明人：Rubik
- 魔方發明時間：1974年
研究背景,研究歷程,最新進展,
研究背景
魔方作為一個經典的玩具，從1974年誕生到現在為止已經風靡全球。這種玩具的最大魅力就在於將每一面的顏色打亂之後，可以形成數目驚人的顏色組合，一個三階魔方最多可以形成的組合數在理論上超過4325億億種。
解魔方也逐漸成為了數學家們的研究項目，最少需要多少次轉動可以確保無論什麼樣的顏色組合都能被復原？這成為了一些數學家求證的難題，而最終答案也被稱為“上帝之數”（God's number）。
研究歷程
早在1981年的時候，“上帝之數”被證明為小於52，在1995年降低至29，之後的每次突破都很艱難。美國加利福尼亞州科學家在2010年利用計算機破解了這一謎團，研究人員證明任意組合的魔方均可以在20步之內還原，“上帝之數”正式定為20。
魔方都能在20步內還原
魔方都能在20步內還原這支研究團隊位於美國加利福尼亞州帕洛阿爾托市。科學家們通過計算機計算和證明，任意組合的魔方都可以在20步內還原。這一結果表明，大約有10萬多種的起始狀態恰好可以在20步內還原。
利用谷歌公司計算機強大的計算能力，研究人員檢驗了魔方任何可能的混亂狀態(確切數字為43,252,003,274,489,856,000約合4.3×1019)。美國俄亥俄州肯特州立大學數學家莫雷-戴維德森教授也是研究人員之一，他表示，“我們現在可以肯定，這個‘上帝之數’就是20。對於我來說，我也回到了原地。魔方伴隨著我成長，這也是我為什麼深入研究這個數學問題的原因。這個謎團引起了人們的廣泛關注，它也許是人類歷史上最受歡迎的謎語了。”科學家們的初步研究成果發表於線上網站上，但戴維德森表示，他們準備將研究成果提交給雜誌正式發表。
程式設計師托馬斯-羅基花了15年的時間，致力於尋找這個謎團的答案。據羅基介紹，研究團隊所採用的算法可以在1秒鐘內嘗試10億種可能，此前的計算機算法1秒鐘內只能處理4000種可能。
為了讓問題簡單化，研究團隊採用了一種所謂“群論”的數學技術。他們首先將魔方所有可能的起始狀態集分成22億個集合，每個集合包含了195億個可能的狀態。集合的分配原則是這些可能的狀態是如何應對一組10個可能的還原步驟。再通過魔方不同的對稱性，這種分組技術使得研究團隊將集合數減少到5600萬個。
研究人員所採用的算法可以快速將這些還原步驟與恰當的起始點匹配起來，從而實現在20秒內處理一個集合中的195億種可能。對於普通的家用電腦來說，以這樣的速度完成整個處理任務需要大約35年時間。
最新進展
2010年8月有研究小組宣布，“上帝之數”研究已經有了新的進展，目前這個數字被定格到20。也就是說，無論什麼樣組合的三階魔方，都可以在20步以內進行還原。這個數字是使用了由Google捐贈的閒置CPU資源進行計算的，總的CPU時間約為35年。
研究者們將4325億億種初始組合狀態分為了2,217,093,120組，然後再利用對稱性集合覆蓋將總狀態縮小至55,882,296組，在計算機上運行的解魔方算法可以在20秒內還原一組，最後完成整個工程大約耗費了35年的CPU時間。
不過這對於普通玩家來說，20步還原一個三階魔方應該還是一件很困難的事情。
