基于CFOP算法的魔方還原

唐健　席禹

摘要：科學技術是第一生產力，是人類文明進步的基石。科技的進步推動著人類社會的發展。 縱觀人類歷史，對科學思想和科技成果的廣泛傳播和普及，都積極地推動了人類社會的進 步。科學技術普及對提高國民的科技素質,增強公眾對現代科學技術的理解、掌握和運用 能力,把科學思想、科學理念植入民族精神,推動科技事業發展有著重要作用。隨著科技的 發展，智能算法得到越來越廣泛的關注，也更多地應用到日常生活的問題中。其中，還原 魔方成為科普研究的熱點，利用人工智能算法復原魔方具有很大的實用性和經濟價值。基于上述分析設計，本文最終設計并實現了魔方還原的全過程，展現了系統的優良性 能和帶來的巨大優勢，同時分析了模型的優缺點，并提出了改進方法和拓展領域。

關鍵詞：CFOP算法；魔方復原；人工智能

1問題重述

魔方，英文名為Rubik's Cube,又叫魯比克方塊，臺灣地區稱之為魔術方塊，香港地區 稱之為扭計骰，最早是由匈牙利布達佩斯建筑學院厄爾諾#魯比克教授于1974年發明的。 魔方，狹義上指三階魔方。三階魔方形狀通常是正方體，每個邊有三個方塊，官方版的魔方變長為57mm"三階魔方有一個連接著六個中心塊的中心軸以及8個角塊，12個棱塊構成，當它們連接在一起的時候會形成一個整體，并且任何一面都可水平轉動而不影響到其他方塊。

魔方在發明后不久就風靡世界。除了對教育行業帶來深遠影響，魔方也對科學研究產生了巨大推動力。截至目前，晶體學、晶體電子衍射、夸克以及基因學等多個領域的模型構建都曾借鑒過三階魔方。如今人工智能技術的很多應用場景中也有了“魔方”的身影。因此，如何設計出一種數學算法還原打亂的魔方成為熱門問題。

2符號說明和定義

符號說明R, L, U, D, F, B 分別表示右側層、左側層、上層、底層、前面層、后面層的轉動

定義1：魔方的原始狀態：當魔方同一個面上的所有小塊面均為同一種顏色，則稱魔方處于原始狀態。

定義2:魔方的復原：指將一個狀態的魔方通過特定的轉動方式變成魔方的原始狀態。

定義3:魔方的轉動：在本文中，魔方的轉動均指把魔方某個面上的所有小塊全部順 時針轉動。同時，只考慮魔方的側面一層的轉動，不考慮魔方中心層的轉動。

3問題假設

1、假設已經確定了每個面的顏色。魔方的54小面按照國際慣例貼有紅、橙、綠、藍、白、黃6種顏色的貼紙。旋轉魔方的各層可以將魔方的色面打亂或者復原。

4問題分析

本文研究的核心問題就是魔方復原。首先應該對魔方進行一般性分析，包括魔方的結構，相關操作和魔方狀態的唯一性表示方法。目前主流魔方復原方法有層先法、CFOP 法、TM法等。

層先法是一種逐層復原魔方的方法。此種方法分為底層棱塊歸位，底層角塊歸位，中間層棱塊歸位，頂層棱塊朝向調整，頂層角塊朝向調整，頂層棱塊位置調整和頂層角塊位置。

CFOP法由捷克的Jessica Fridrich提出，是一種特別適合魔方速擰比賽的方法【2】

綜上考慮，本文選擇CFOP的處理方法，對問題進行進一步分析。

5模型建立與求解

首先，我們知道魔方是由一些小方塊連接在一起組成的一個大立方體。大立方體有六個面，每個面都是由9個小方格組成的一個平面。如下圖1所示，其中，A代表中心 塊，B代表角塊，C代表邊塊。

求解

通過對魔方轉動的分析，我們發現打亂后的魔方，存在轉動序列使得魔方變為以下四種基本情況：(1)僅有三棱變換；(2)僅有三角變換；(3)僅有兩棱翻轉；(4)僅有兩角扭轉，但扭轉方向不同。下面給出這四種基本情況的轉動序列。

⑴對于僅有三棱置換的情況，存在轉動序列如下所示：

(B2U)(RL3B2LR3)(UB2) = (ULB, UBR, URF) (2)

使得在該轉動序列下魔方的三個棱發生變化，相互置換，其他小塊均保持不變。其他情況的三棱置換以此類推。

對于僅有三角置換的情況，存在轉動序列形式如下：

(R3FR3)B2(RF3R3)B2R2 = (ULB, UBR, URF) (3)

使得在該轉動序列下魔方的三個較快發生了變化，相互置換，其他小塊均保持不變。其他情況的三棱置換以此類推。

對于僅有兩棱翻轉的情況，分為相鄰的棱和相對的棱這兩個類別。對于相鄰的棱存在轉動序列如下：

(BL3(DFU)BL)(B3L(U3F3D3)B3L3) = (UL, LU)(UB, BU) (4)

對于相對的棱存在轉動序列如下：

(BF3)(L3U)B3(LU3)(FB3)(RU3)B(R3U) = (UL, LU)(UR, RU) (5)

使得在該轉動序列下的魔方僅有兩棱轉動，其他小塊均保持不變。其他情況的三棱置 換以此類推。

對于僅有兩角扭轉，且扭轉方向不同的情況，分為相對的角塊和相鄰的角塊兩個類別。對于相鄰的兩角扭轉，且方向不同，存在轉動序列如下：

B(U3FL3)(U2LU)B3(U3L3U2)(LF3U) = (ULB, LBU, BUL)(UBR, RUB, BRU) (6)

如果相對的兩角扭轉，且扭轉方向不同，存在序列如下：

(F3UBU3F)(U(LFL3)B3(LF3L3)U3) = (ULB, LBU, BUL)(UFR, FRU, RUF) (7)

使得在該轉動序列下的魔方僅有兩角扭轉，且方向不變，其他小塊均保持不變。其他情況的三棱置換以此類推。在轉動時，我們默認中間層是不參與轉動的因為所有中間層的轉動均可由周邊層轉動進行實現。基于上述的定義，我們可以完整還原魔方的色塊和位塊的所有轉動。

6模型的優缺點和推廣

6.1模型的優缺點

6.1.1優點

本模型的建立，推導合理縝密。由于魔方的狀態的復雜性，我們采用CFOP法將魔方進行分層次的分析，從而降低了魔方還原時的復雜性，使還原時更加簡便快捷。采用該方法運行結果有較高的概率可以將打亂的魔方進行還原，若還原失敗，可以再次運行進入循，使魔方最終還原。

6.1.2缺點

本模型僅采用了六種還原方法，還原方法較少，將導致采用該方法時運行時間依舊較長，與人為還原魔方相比，較為不靈活。運行結果時發現，對于某少數打亂的魔方難以還原。

6.2模型的推廣

（本文魔方系統是將解魔方算法應用程序語言，模擬人）魔方的思維過程對任意狀態下的魔方進行復原求）。由對魔方群的分析可知，解魔方是一個依賴搜索解決問題的 非確定多項式問題，即可在多狀態空間內被非唯一確定。因此如果試圖用更少的巧動步驟開解魔方，便意味著捜索要在更廣闊的狀態空間中進行。由此產生的同構狀態會隨著巧數的減少而成指數形式增長，本文僅采用六種方法，程序較為簡單可行，可以作為初學程序解魔方的典型方法。

參考文獻：

[1]鄭瑜.魔方原理及其應用[D].浙江大學，2009.

[2]揭宗昌，郭力峰，蔡澤輝.多變魔方機器人的控制系統設計[J].微型機與應用，2011, 30（7）:101-103.

[3]李世春.魔方的科學和計算機表現[M]. 2003.

[4]黎廣輝.三維虛擬魔方游戲軟件的設計與實現[D].華中科技大學，2011.

[5]魔方算法的研究和系統實現[D].東北大學，2013.