征服世界上最流行的玩具——魔方

文/僅此

魯比克立方（Rubik’s cube），或稱魔方，相信大家多多少少都擰過幾下，也有不少人能成功複原最常見的三階六面魔方。筆者也可厚着臉弱弱地自稱為一個前魔方愛好者，練過一陣子三階速擰，收集并複原過各種異形魔方，其中最愛鏡面，超适合耍帥，然至今未能複原那個被我手賤打亂的SSQ1，望大神指點 [拱手狀]！

三階魔方

複原任意狀态三階魔方的最少步數已被證明為20步*，換句話說，任何超過20步的打亂，都可以用更少的步數還原回去，所以給别人打亂魔方的時候不需要再努力地亂轉了，并無卵用~[調皮臉]。這一數字有時被稱為“上帝之數”，不過裝逼的時候最好還是不要隻說這個稱呼啦，畢竟“上帝之數”有不止一兩個代指，對方可能并不會get你的點[攤手]。

鏡面魔方

在探索最少步數的道路上，群論（group theory）可謂發揮了至關重要的作用，于是作為群論迷妹的筆者此番來意便是：略去嚴格的證明不提，帶領各位看官感受一下如何從群論的角度來征服魔方！

先來簡單解釋一下為何魔方會和群論有着如此密切的關系。數學中，群可以用一個集合G配合一種運算（如加法、乘法等）來定義，其中這項運算要滿足結合律（以加法為例，即(a b) c=a (b c)），同時集合G要滿足以下三點要求：

（1）集合中存在一個元素e使得對集合G中任意元素g，有e與g的運算結果仍為g（如加法中0的地位，乘法中1的地位）；

（2）集合中任意元素間運算的結果仍在這個集合中（簡稱為封閉性）；

（3）集合中每個元素g都有唯一對應的相反數g’，使得g與g’的運算結果為e（如加法中相對應的正負數）。舉個最常見的栗子：全體整數配上加法運算就滿足以上所有條件，因此可以看作一個加法群**

将魔方側面展開編号

對于魔方來說，存在一個由“全體可能的色塊排列”組成的集合，不妨成為集合M吧。為方便研究，我們将魔方展開并編号，這樣一來，每一種可能的色塊排列都可看作對這些編号的置換（permutation），通俗一點說，就是将編号打亂順序。例如，将複原态魔方的橙色面（看作前面）順時針轉動90°後（通常記作F轉動），就會有19換到21的位置，21換到27的位置，27換到25的位置，25換到19的位置，可記作（19 21 27 25）。依此記下各色棱塊角塊的置換，F轉動後的色塊排列可以記作（19 21 27 25）（20 24 26 22）（7 28 48 18）（9 34 46 12）（8 31 47 15）。

置換間的組合即為一種運算，如連續做兩次F轉動就是進行了一次運算，運算結果是橙色面轉動180°的狀态，可以用（19 27）（21 25）（20 26）（24 22）（7 48）（28 18）（9 46）（34 12）（8 47）（31 15）表示。不難接受，任何置換（或說轉動）的組合結果都會在集合M中。同時這種運算也滿足結合律，盡管實際操作上很難看出，但數學上不難驗證***

魔方的複原态可以充當集合中e的地位。置換的相反數也很容易得到，隻要每個小置換“反着寫”就好，如F轉動的相反數就是（25 27 21 19）（22 26 24 20）（18 48 28 7）（12 46 34 9）（15 47 31 8），不難看出，這就是将（處于複原态的魔方）橙色面逆時針轉動90°後的色塊排列。對于更複雜的狀态，即使無法确定複原方法，隻要寫出編号的置換，仍可以輕松寫出它的相反數（盡管手動寫出置換并不是一件容易的事）。

對照上述“群的定義”，可以發現，集合M是一個群。

不難理解，一旦我們有了90°順時針轉動白色頂面（U），黃色底面（D），藍色左面（L），綠色右面（R），橙色前面（F），紅色後面（B）的六個基本置換，就可以通過它們之間的運算得出任意色塊排列，或說這六個基本置換可以“生成”集合M。當然，在生成的過程中會有不同轉動組合得到同一最終狀态的情況，不過不必擔心，這一問題後續會得到解決。

接下來我們需要準備54×54的階梯空格子，并按照（列數，行數）的方式标号，見筆者作為靈魂畫手所做的下圖。我們将把集合M裡的元素挨個放入相應的格子中，每格一個。

54×54階梯格

首先我們填入六個基本轉動（U,D,L,R,F,B）及它們的相反數，以F轉動為例，參與置換的最小數字為7，且7被置換到了28的位置，所以我們将F轉動後的這種色塊排列填入格子（7，28）。

填好六個基本轉動後，我們将格子裡已有的六個狀态分先後兩兩組合。所謂分先後就是說，先做U轉動再做F轉動與先做F轉動再做U轉動是分别對待的，因為它們會造成不同的色塊排列（不好腦補的時候就拿起魔方轉一轉）。此時如果我們仍按填入基本轉動的規則将組合結果填入格子，會發現有些格子已經被占領了，如先U再F組合後的色塊排列應該被填在（1，3），然而（1，3）已經填入了U轉動。這種時候我們就在原有的U、F組合之後再組合一個U的相反數，這樣編号1就會被複位，我們需要确定新的格子。如果新的格子仍被占用，就再組合一次占領新的格子的置換的相反數，直到有空格子讓我們填入或得到複原态，一定要按順序記錄好都組合了哪些轉動，這是得到複原方法的關鍵。得到複原态意味着我們最初組合得到的色塊排列可以通過另一系列步數等同或更少的轉動得到，這就解決了我們之前的擔憂。

三階魔方轉動圖解

聰明的看官們一定已經猜到了，接下來的工作就是不停地兩兩組合格子中已有的狀态并按照上述規則填入空格子中，直到整張表格不再變化，即任何新的組合都會被簡化到複原态。

如此一來，這張表格完成之時，便是我們确定最少步數之日。同時，擁有了這張表格後，理論上隻要我們确定了色塊排列所對應的置換，将其所在格子中的操作逆向而為就能複原。然而，相信看官們已經發現，此處有個悲傷的消息曰：這張表格非人力所能完成，我們需要向計算機尋求幫助，設定好一定的程序，就能在有限的時間内完成複原。

魔方與計算機視覺識别

So，至此我們終于得到了“暴力”征服魔方的方法，這項方法廣泛适用于各式魔方和類魔方玩具****，障礙隻在于計算機的算法足不足以在可接受的時間内完成表格的制作。

不過筆者始終認為，真正的暴力征服魔方，是拆了重裝啊！紅紅火火恍恍惚惚[手比V字]

高階魔方内部結構

【附加說明】

*追求嚴謹看這裡：此處的20步不含（為操作方便進行的）魔方整體翻轉，并将單面旋轉180°看作一步。我們的方法是将單面旋轉180°看作兩步，所以總步數要多些，具體數字疏于考證，約在25步上下。

**值得一提的是，群的定義中并不要求運算滿足交換律，例中的全體整數滿足加法交換律，屬于一類特殊群——阿貝爾群。

***置換本質是映射，映射間的複合從定義上滿足結合律。

****能用這種方法破解的一類玩具被稱為permutation puzzle

基于排列組合的小玩具

訂閱“來吧 學數學”頭條号 享更多精彩内容

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!