唐健　席禹

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

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

1問題重述

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

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

2符號說明和定義

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

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

定義2:魔方的復原：指將一個狀態(tài)的魔方通過特定的轉(zhuǎn)動方式變成魔方的原始狀態(tài)。

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

3問題假設

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

4問題分析

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

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

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

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

5模型建立與求解

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

求解

通過對魔方轉(zhuǎn)動的分析，我們發(fā)現(xiàn)打亂后的魔方，存在轉(zhuǎn)動序列使得魔方變?yōu)橐韵滤姆N基本情況：(1)僅有三棱變換；(2)僅有三角變換；(3)僅有兩棱翻轉(zhuǎn)；(4)僅有兩角扭轉(zhuǎn)，但扭轉(zhuǎn)方向不同。下面給出這四種基本情況的轉(zhuǎn)動序列。

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

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

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

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

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

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

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

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

對于相對的棱存在轉(zhuǎn)動序列如下：

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

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

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

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

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

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

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

6模型的優(yōu)缺點和推廣

6.1模型的優(yōu)缺點

6.1.1優(yōu)點

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

6.1.2缺點

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

6.2模型的推廣

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

參考文獻：

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

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

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

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

[5]魔方算法的研究和系統(tǒng)實現(xiàn)[D].東北大學，2013.