基于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.