基于CFOP算法的魔方還原

唐健　席禹

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

關(guān)鍵詞：CFOP算法；魔方復(fù)原；人工智能

1問(wèn)題重述

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

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

2符號(hào)說(shuō)明和定義

符號(hào)說(shuō)明R, L, U, D, F, B 分別表示右側(cè)層、左側(cè)層、上層、底層、前面層、后面層的轉(zhuǎn)動(dòng)

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

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

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

3問(wèn)題假設(shè)

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

4問(wèn)題分析

本文研究的核心問(wèn)題就是魔方復(fù)原。首先應(yīng)該對(duì)魔方進(jìn)行一般性分析，包括魔方的結(jié)構(gòu)，相關(guān)操作和魔方狀態(tài)的唯一性表示方法。目前主流魔方復(fù)原方法有層先法、CFOP 法、TM法等。

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

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

綜上考慮，本文選擇CFOP的處理方法，對(duì)問(wèn)題進(jìn)行進(jìn)一步分析。

5模型建立與求解

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

求解

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

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

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

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

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

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

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

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

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

對(duì)于相對(duì)的棱存在轉(zhuǎn)動(dòng)序列如下：

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

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

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

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

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

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

使得在該轉(zhuǎn)動(dòng)序列下的魔方僅有兩角扭轉(zhuǎn)，且方向不變，其他小塊均保持不變。其他情況的三棱置換以此類推。在轉(zhuǎn)動(dòng)時(shí)，我們默認(rèn)中間層是不參與轉(zhuǎn)動(dòng)的因?yàn)樗兄虚g層的轉(zhuǎn)動(dòng)均可由周邊層轉(zhuǎn)動(dòng)進(jìn)行實(shí)現(xiàn)?；谏鲜龅亩x，我們可以完整還原魔方的色塊和位塊的所有轉(zhuǎn)動(dòng)。

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

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

6.1.1優(yōu)點(diǎn)

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

6.1.2缺點(diǎn)

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

6.2模型的推廣

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

參考文獻(xiàn)：

[1]鄭瑜.魔方原理及其應(yīng)用[D].浙江大學(xué)，2009.

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

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

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

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