（应用数学专业论文）魔方原理及其应用.pdf

摘要 作为世界三大智力玩具之一的魔方，自1 9 7 4 年发明以来，人们不断研究它 自身的原理及其应用。本文从最基本的一阶魔方讨论起，提出它与样条，小波之 间的联系；接着给出三阶魔方的状态原理；继而探讨魔方的相关算法及其应用， 其中包括讨论盲拧编解码算法原理，提出一种新的三阶竞速快速算法，解决n 阶魔方的还原问题和研究基于小波，混沌，魔方变换的图像加密算法思想。 关键词：样条魔方置换算法 a b s t r a c t r u b i k sc u b e ，a so n eo f t h et h r e eb e s ti n t e l l i g e n c et o y si nt h ew o r l d ，w h i c hi s i n v e n t e di n19 7 4 ，a t t r a c tm a n yp e o p l et os t u d yi t so w np r i n c i p l ea n da p p l i c a t i o n s i n t h i sp a p e rw ed i s c u s st h er e l a t i o nb e t w e e nl 幸1 lc u b e ，s p l i n ea n dw a v e l e ta tf i r s t 。 t h e ni n t r o d u c et h et h e o r yo f3 * 3 木3c u b e ，f i n a l l yw er e s e a r c hs o m ei m p o r t a n t a l g o r i t h m sf o rr u b i k sc u b ea n di t sa p p l i c a t i o n s ，w h e r ei n c l u d i n gt h eb l i n d f o l d a l g o r i t h m an e wa l g o r i t h mf o rt h e3 * 3 宰3c u b ei ns p e e d c u b i n g ，t h es o l u t i o nf o rn * n 事n c u b ea n da ni m a g ee n c r y p t i o ni d e ab a s e do nw a v e l e t ，c h a o sa n dm a g i cc u b e t r a n s f o r m k e yw o r d s ：s p l i n er u b i k sc u b ep e r m u t a t i o na l g o r i t h m h 1 1 背景和研究现状 第1 章绪论 魔方，又称为“魔术方块”，英文名为“r u b i k sc u b e ”，于1 9 7 4 年，由匈 牙利布答佩斯建筑学院鲁比克教授发明【1 】。8 0 年代，魔方以其独特的魔力征服 全世界，并以惊人的销量成就了玩具界史无前例的奇迹，它与“华容道”和“独 粒钻石”并称为世界三大智力玩具，曾被评为2 0 世纪最有影响的1 0 0 项发明之 一- 今天魔方进入了我们的休闲领域，它以健身，健脑的特点重新被人们所认识。 魔方不仅仅是益智玩具，也是一种教学用具，一种运动用品，玩魔方更是象征智 慧和时尚的休闲活动。魔方由三阶正方体衍生出多个品种，已经形成一系列产品 线；玩法也由简单的复原，向复合型手、眼、脑协调运用等多样化竞技运动发展： 快速还原、单手还原、闭眼还原( 盲拧) ，最少步还原等等。曾在1 9 8 0 年七月， 美国麻省理工学院m i t 成立了魔方爱好者协会，并于19 8 1 年底举行了首届全国 魔方竞标赛。之后，匈牙利举行了首届鲁比克魔方世界竞标赛，世界各地各种各 样的魔方大型赛事也纷纷举行。截止2 0 0 9 年5 月2 日，关于三阶魔方的速拧世 界记录( 7 0 8 秒) 由来自荷兰的大学生e r i ka k k e r s d i j k 保持，三阶魔方的盲拧 世界纪录( 4 7 2 2 秒) 由中国的庄海燕保持。 除了众多魔方爱好者和竞速玩家以外，魔方还一直在吸引着数学家和物理学 家的兴趣。国外数学家在计算机上用群论的方法进行研究。由捷克密码学教授 j e s s i c af r i d r i c h 于上世纪八十年代初发明的“f r i d r i c hm e t h o d ”的复原法如 今被大多数竞速玩家所采用【2 】。r i c h a r dc a r r 博士详尽论述的二到五阶魔方的 盲拧原理也广泛运用于各种盲拧方法中【3 】。目前最好的三阶魔方算法软件是国 外开发的一款叫做c u b ee x p l o r e r 的版本 4 】。最领先的最小步数研究已经达到 2 5 步以内【5 ，6 】。 科学家们不仅对魔方的内在原理展开了深入的研究工作，而且对魔方的应用 也乐此不疲。物理学家们常把魔方作为模型来描述基本粒子中国的李世春教授 还以魔方为模型，讨论了晶体学，群论，晶体电子衍射，夸克，混沌和基因等科 l 学问题，在多种科学领域建立了新颖的魔方和科学的隐喻关系【7 】。而在数学与 计算机方面，研究工作者以魔方为原型和工具，研究代数学，计算机图形图像， 加密算法理论等等。 1 2 论文工作和意义 魔方的历史只是刚刚开始，关于原理的探索也才刚刚起步。对魔方理论的探 究，不仅有助于阐释各种魔方还原算法和玩法原理，还可以作为其他数学理论研 究的参考模型。 本文从纯数学的角度出发，详细讨论了魔方的基本原理及其应用： 在第2 章中建立一阶魔方和b 样条的隐喻关系，并借此浅述了样条函数和小 波理论的联系； 在第3 章中着重研究了三阶纯色魔方状态的基本原理，主要利用代数方法， 置换理论严密论证了魔方不同状态转化之间的转动序列存在性问题。 在第4 章中结合算法继续深入探讨魔方原理及其应用。在第一个实例中结合 编解码理论阐释了魔方盲拧算法( 算法4 1 ) ；在第二个实例中分析三阶魔方快速 还原原理( 算法4 2 ) 并提出一种新的竞技还原算法( 算法4 3 ) ；在第三个实例中 建立基于新算法的一套n 阶魔方还原理论( 算法4 4 ) ；在第四个实例中提出魔方 变换思想，结合小波变换和混沌序列讨论其在图像置乱加密中应用的可行性( 算 法模型4 5 ) 。 2 第2 章一阶魔方、样条和小波 一阶魔方作为n 阶魔方的特例，因为本身状态不变，所在在还原问题上不存 在讨论性。但发现一阶魔方蕴含b 样条函数之后，不妨由此展开，浅谈下样条函 数和小波理论的联系。 2 1 一阶魔方和b 样条 一阶魔方的本质，欧氏几何空间上说无疑是一个立方体，显然立方体具备6 个面，8 个顶点，1 2 条边。除此之外，实际上它还蕴含着b 样条函数 8 ，9 】。 定理2 1 一阶魔方蕴含b 样条函数 证明：降维一阶魔方，从最先的二维正方形开始，它反映出一个一次b 样条函数。 因为假设一条直线l o ( 垂直于正方形一对角线1 1 ) 沿着与正方形的另一条对角线1 2 平行的方向运动，那么，它落在正方形内的线段长度变化趋势如下：先为0 ，后 线性增加，当与对角线重合时最大，随后又线性下降，逐渐变为0 这个线段长 度的变化函数f 1 ( x ) 反映的就是一个1 次b 样条函数( 不妨设正方形对角线长度为 1 ，x 为对角线1 1 变化长度) ： f 2 x ，o x 1 2 f 1 ( x ) ；2 2 x ，1 z x 1 【10 ，其他 现在，类似二维的方法，把直线改为平面，用一个垂直于一阶魔方对角线l 的 平面s 来平行运动，相当于研究单位立方体的切面面积，我们看到切面先为正三 角形，然后形状变为六边形，再变为正三角形，面积变化反映的实际上是一个2 次b 样条函数( 不妨设立方体对角线长度为1 ，x 仍然为对角线1 7 的变化长度) ： 3 泛函分析里面对样条函数的一个解释：一个变分方程的极小解。这个解释固 然重要，但却不够美，因为这个解是近似下得到的。而这里我们看到：一阶魔方 蕴含b 样条函数。这会是对样条函数的另一个美的解释反之，借助b 样条函数 可以建立和离散几何的联系【9 】，利用多元样条的性质也可以解决很多离散数学 相关问题，例如贾荣庆就证明了s t a n l e y 提出的关于幻方计数的一个猜想【10 】。 如今，样条函数也在c a g d 、小波及其它领域中均有了很好的应用。其中一 个非常重要的原因就是因为它有了一个很好的基底：b 样条基底。 2 2 多尺度分析和样条 当样条函数在8 0 年代进入研究高潮后，小波则逐渐兴起。不仅仅小波的数 学理论发展迅速，工程人员更是借助小波热疯狂地将其用到各自的领域。小波分 析中一个重要的内容就是多尺度分析( m r a ) 理论【1 1 ，1 2 】。关于多尺度分析的概念 如下： 定义2 1 ( 多尺度分析) 设“) j z 是空间l 2 ( r ) 的一个闭子空间列，( v j ) j ：被称为l 2 ( r ) 的一个多尺度分 析，如果 v ；) i e z 满足下面四个条件： ( 1 ) 嵌套性：v 1t - v ocv 1 ； ( 2 ) 稠密性：n j zv j = ( o ) ，丽= l 2 ( r ) ； ( 3 ) 伸缩性：f ( x ) m 舒f ( 2 x ) 、7 ；+ l ，j e z ( 4 ) 正交基性：存在巾( x ) e v o ，使得( 巾( x 一0 【) ) 是v 0 的正交基。 上述定义中的巾被称为尺度函数，v ；称为逼近空间由多尺度的定义及其性 质，可以知道一个正交的m r a 是可以来构造空间l 2 ( r ) 的，构造尺度函数的一个 较好的方法是引入细分方程。 定义2 2 ( 细分方程) 设 v j ) i e z 及审( x ) e v 0 v 1 ，而( 讵巾( x o 【) ) 是v 1 的标准正交基，且率( o ) = 1 故有巾( x ) = a z a ( 0 【) 巾( 2 x o 【) ，我们称此为细分方程( 又称双尺度方程) 4 细分方程是小波分析中的核心方程【1 3 ，1 4 】，多尺度分析在小波分析中有着 举足轻重的地位，通过多尺度分析便可以构造好的小波，而细分方程的解如果有 好的性质并再加上其他的条件就可以构造多尺度分析，从而构造正交小波等等。 应该说，小波与样条有着天然的血缘关系，这种天然的纽带恰好来由细分方 程。小波基底的建立，需要一个满足细分方程的函数。而b 样条函数恰好满足这 种双尺度方程。于是，二者的联系便在情理之中。 定义2 3 ( 基数样条空间) 任意m e n ，m 阶且具有节点序列z 的基数样条空m s m 是这样的所有函数 f ec m 一2 ( r ) 的集合，f 在区间( k ，k + 1 ) ，k e z 上是不超过m - 1 次的代数多项式。 一阶基数b 样条n 1 ( x ) 是单位区间【0 ，1 ) 上的特征函数： n 1 ( x ) x o 1 ) 2 k 巍d 而对于m 2 ，n m ( x ) 用卷积递推定义 n m ( x ) = ( n m 一1 n i ) = 亡n m - 1 ( x - t ) n i ( t ) d t = f 0 1n m l ( x t ) d t n m ( x ) s m ，即n m ( x ) 是基数样条函数。 定理2 2 对- y v j z ，定义v ；痢 2 - j 2 n m ( 2 一i x k ) ：k z ) ，n m ；是m 阶基 数b 样条函数，则 m ) i z 是l 2 ( r ) 的一个多尺度分析，即： ( 1 ) 、7 j + 1 ，对于j z ；n j zv j = ( o ) ，丽= l z ( r ) ； ( 2 ) f ( x ) v ；管f ( 2 x ) m + 1 ，j e z ； ( 3 ) ( n m ( x k ) ：k z ) 是v o 的一个r i e s z 基； ( 4 ) v ；+ l = + w j 和上w j ，其中w 是v j 在v ；+ l 内的正交牢卜子空间。 定理2 3 设c pm ( x 专刍哿一2 ( 一1 ) jn 2 m ( j + 1 ) n ! m ) ( 2 x - j ) ，则c l i m ( x ) 是生 成w r o 和所有( j ez ) 的基本小波，它有紧支撑集：s u p p 山m ( x ) = 【o ，2 m 一1 】，且 满足两尺度关系式： n m ( x ) = 器o2 一m + 1 ( t ) n m ( 2 x - - k ) ； 山m ( x ) = 匙牙2 r l 丽( - 1 ) k 厶f l m ；。( i ：1 ) n 2 m ( k + 1 一1 ) 】n m ( 2 x k ) 。 样条方法是函数逼近论中的一种重要方法，小波分析的很多重要思想来自样 条分析，例如利用b 样条基函数作为光滑函数的样条小波就是小波分析的重要内 容。崔锦泰等人就对样条小波理论的研究做出了很大的贡献【1 2 】。而在具体实现 中，样条小波也有它自身的一些优点，例如有： ( 1 ) 具有显示表达式，便于问题的深入分析和估计； ( 2 ) 作为一个平滑函数，有很高的正则性，也便于计算机的编程实现； ( 3 ) 相比较于利用多分辨分析构造普通高维小波，样条函数能更容易地构造高维 样条小波。 6 3 1 引官和记号 第3 章三阶魔方状态原理分析 本篇章跳过z - 阶，以经典的智力玩具三阶纯色魔方作为模型，研究魔方原理 关于二阶的理论研充，实际上可以用三阶魔方的8 个角块束作类比。 在给出以下有关魔方状态的基本定理及其推论之前，先简单的规定下一些符 号的表示惠义： 1 约定魔方六个平面的名称如下： 上( u ) ：上平面( 任意选一种你喜爱的颜色) 下( d ) ：下平面 前( f ) ：前平面 后( b ) ：后平面 左( l ) ：左平面 右( r ) ：右平面 2对各平面进行转动的记法是： u ：把上平面按顺时针方向转动9 o 。 u ，：把上平面按逆时针方向转动9 0 。 u 2 ：把上平面转动180 。 7 同理规定d ，f ，b ，l ，r 面的转动方法，如下目所示 u l 层作顾时针 r 面惟颤日针 嚣娜9 竺譬 u 。上层作逆时针 r 右面作啪针 竺黔r 竺第 u 2 上屡作顺时针r 2a 面t e 黼针 嘏篇冀厂：嚣瑟瑟 # i ! 荐孑 l 鹱! 祭 d 底屡作颓时什 州g o f d 。虎屡忭逆时针 g o 度# ( 印鞋 一下) d 2 康n 睡时针 1 8 0 度转而逆 黪* 1 8 # 0 豁 针显一样的i f 前面作顾时针 g o 度转( 哪# 1一t ) f 。前面作逆时针 9 嚷转唧转 f 2 前面镕餍啉十 1 日雠啭而逆 时针1 日0 9 实 际镕果与聃， 针是一样的o 。渊8 勰 一下) 一下) 面镕e 目 9 0 魔# ( 即糟 “勰 l 珑* ：b 目o 器 是一样的 b 。后面怍逆时针 10 0 廑转唧转 l 一下) 、”篇；嚣； 1目针1 8 0 e 霎 jr 镕* 日m 针是一样的 3 称位于右平面和前平面之问的那个棱块为右前( f r ) ；称位于右平面前平面 和上平面之间顶角上的那个角块为右前上( u f r ) ，以此类推： 十二个位置上的棱块分别称为： 前下( d n 、后下( d b ) 、左下( d l ) 右下( d r ) 左前( f d 、右前( f r ) 、左后( b l ) 、右后( b r ) 、 左上( u l ) 右上( u r ) 、前上( u f 】、后上( u b ) 八个位置上的角块分别称为 左前下( d f l ) 、右前下( d f r ) 左后下( i ) b l ) ，右后下( d b r ) 、 左前上( u f l ) 、右前上( u f r ) 左后上( u b l ) 右后上( u b r ) 3 2 魔方状态原理解析 3 2 1 错误状态解析 为了解决魔方还原及其引起的一系列问题，我们首先利用逆向思维和代数知 识论证在实际操作中某些基本转动序列的存在可能性，并讨论魔方错误组合状况 和可还原情况的状态总数。 定义3 1 转动序列p ：一串可执行操作步骤的有限排列，如u 7f b 2 r u l r 等等。序列p 的逆即为操作步骤的逆，记为p 7 定理3 1 对完整状态的三阶魔方进行任意层的转动，不存在转动序列p 使得魔方变化 为以下四种情况： ( i ) 仅有两个棱块对换位置 ( “) 仅有两个角块对换位置 ( i i i ) 仅有单个棱块翻转 ( i v ) 仅有单个角块扭转 证明( 邱，2 0 0 6 ，参考文献【1 5 】) ： ( i ) 和( i i ) 的情况可以同时证明。 对完整状态的魔方，对小块位置进行数字排列，块的编号顺序并不重要，假 设编号从u 层开始，从左到右再自上而下： 这样整个魔方的编号就是：123 2 7 这是一个偶排列，我们只需证明， 任意的转动序列都不能改变排列的奇偶性，则命题成立，因为仅有两个棱块对换 位置或者是两个角块对换位置都改变了块位置排列的奇偶性。 9 下面用数学归纳法来证明之。 ( 1 ) 初始状态是偶排列； ( 2 ) 假设魔方转动k 次后，魔方小块位置状态的排列是偶排列( 对奇排列的情 况类似可证) ，顶层块的排列如下： abc def g hl 当转动第k + 1 次的时候，为了方便讨论及一般性，不妨设第k + 1 次转动为u ， 那么中层和底层块的位置不变，顶层块的位置排列变化为： 这个变换可以分解为角块位置的3 次对换加上棱块位置的3 次对换。一共是 6 次对换，是偶数次对换，所以不改变排列的奇偶性。 其余转动的情况可以同理来证明。 综合( 1 ) 和( 2 ) ，可以看出任意的转动序列都不能改变初始状态块位置排列的 奇偶性。( i ) 和( ii ) 的情况不存在。 ( iii ) 和( i v ) 的情况则需要引入复杂一点的编码和逆位概念。 首先棱块的翻转和角块的扭转都涉及到块的朝向问题。 依然采用排列的方法，把魔方按平面展开( 如下图) ，为了找到转动对魔方状 态的影响，这里分别对1 2 个棱块和8 个角块进行编码。每个棱块有两个朝向， 每个角块有三个朝向，各自可以定义2 4 号位。如下图所示，以e ( e d g e ) 开头的 编码表示棱块，以c ( c o r n e r ) 开头的编码表示角块，u ，d ，f ，b ，l ，r 分别表示块的 朝向面。编码里面的“0 1 ”所在的位置代表1 号位，“0 2 ”所在的位置代表2 号位。依次类推，“n ”所在的位置代表n 号位，显然n 小于或等于2 4 确定 转动后的排列就按位依次记录各位上的数就可以了。 ( b 2 l e b 2 1c b 2 2 e b l 2be b 2 0 c b 0 8e b l 5c b lo c 【；0 9e u l6c 【1 12 e u l3ue u l 7 c l ；0 be u 0 2c t f 0 3 c l 0 7e l l 4c l 0 5c f 0 4e f 0 1c f 0 2c r0 1e r l 8c r ll e l l lle l 0 7e f 0 8fe f 0 4e r 0 3re r l 9 c l l9e l loc l lsc f l t e f 0 5c f l5c r l3e r 2 4c r 2 4 c l l7e d 0 6“) l4 e d 0 9d e d 2 3 c 0 2 i je d 2 2t _ d 23 现在处于初始状态，其角块的数字排列则记为( 编码中的前两位字母省略) ： 123 456 789 l01 11 2 131 41 5 1 61 71 8 1 92 02 1 2 22 32 4 每三位用斜线隔开，分成8 个部分，对应于8 个角块； 类似地，棱块的数字排列记为： 12 3 4 5 6 7 8 910 1 1 1 2 131 4 1 51 6 1 7 1 8 1 92 0 2 12 2 232 4 每两位用过斜线隔开，分成1 2 个部分，对应于1 2 个棱块。 对于初始状态来说，1 号位上的数字是1 ，2 号位上的数字是2 ，n 号位上的 数字是n 。但转动以后就不是这样了。转动之后状态的数字排列就按1 号位到2 4 号位上的数字依次3 位隔开排列就是了。 举个例子，顶层顺时针转动9 0 度之后角块的排列就是： 1 0 儿1 2 123 456 789 131 4l5 1 61 71 8 1 92 02 1 2 22 32 4 意思就是1 号位上的数字是1 0 ，2 号位上的数字是1 1 依次类推。这 就是块方向问题的数字排列的确定方式，按位依次进行。 在继续证明定理3 1 之前，下面再给出一个新定义。 定义3 2 魔方某个角块上的三个数中的某个数大于它在这个角上初始所在的位置号， 就称为一个逆位。一个排列中的所有逆位的数目称为逆位数【15 】。类似的，棱块 上的逆位也可以依此定义。 定理3 1 证明续： 由定义3 2 ，我们可以发现：三阶魔方棱块状态的逆位总数被2 整除。 证明继续采用数学归纳法 ( 1 ) 初始状态的逆位数是0 。满足定理。 ( 2 ) 假设转动k 次转动之后，排列的逆位数满足该定理。 第k + 1 次转动有1 8 种情况。顺时针转动9 0 度与逆时针转动9 0 度证明过程 类似，只需验证顺时针转动9 0 度的情况。即只需验证9 种情况。另外注意到， 九个层顺时针转动9 0 度的情况都相互类似，所以最后只需验证前面层顺时针转 动9 0 度的情况。 前面层顺时针转动9 0 度的情况： k 次转动之后的排列状态为( 其他层的情况不变就略去了) ： e u x 2 e f x l e l x 7 e f x 8 f k e f x 4e r x 3 e f x s e d x 6 并且排列f k 记为( 前面两个字母省略) ：x 1x 2 x 3x 4 x sx 6 x 7x a 转动k + 1 次以后： 1 2 e u x 7 e f x 8 e l x 6 e f x sf k + 1e f x le r x 2 e f x 4 e d x 3 排列f k + 1 记为：x 8x 7 x 2x l x 4x 3 x 6 x 5 四个棱上的数字都对换一次，逆位数改变4 ，逆位总数被2 整除。 其他层以及逆时针转动9 0 度的情况可以同理证明。 由上面( 1 ) 和( 2 ) ，命题成立。 现在回到情况( i i i ) 的证明上来，如果存在转动序列，则显然转动之后的棱 块逆位数改变1 ，不能被2 整除，矛盾。所以这样的序列无法找到。 角的位置类似于棱，只不过情况稍微复杂。我们继续发现：三阶魔方角块状 态的逆位总数被3 整除。 证明依然用到数学归纳法 ( 1 ) 初始状态的逆位数是0 ，满足定理。 ( 2 ) 假设转动k 次之后，排列的逆位数满足该定理。 转动k + 1 次之后，第k + 1 次转动有1 8 种情况。除去不改变角块位置和方向 的中层转动的6 种情况，还有1 2 种。顺时针转动9 0 度与逆时针转动9 0 度证明 过程类似，只需验证顺时针转动9 0 度的情况。即只需验证6 种情况。另外注意 到，顶层顺时针转动9 0 度与底层顺时针转动9 0 度的情况类似，而且4 个侧面顺 时针转动9 0 度的情况也互相类似，所以最后只需验证顶层顺时针转动9 0 度与前 面层顺时针转动9 0 度的情况。 面顶层顺时针转动9 0 度的情况 k 次转动之后的排列状态设为( 底层的情况不变就略去了) c b y 8 c b y l o c l y 7c u y 9c u y l 2c r y l l u k c l y 5c u y 6c u y 3c r y l c f y 4c f y 2 芳且圮为：j ；易y 3 y 4 蛞y d y 7y 8 y g 巧口巧jj ；2 转动k + 1 次以后： c b y 5c b b c l y 4c u y 6 c u y 9c r y 8 u k + 1 c l y 2c u y 3 c u y l 2c r y l o c f y lc f y l l 并且记为：y 1 0y 1 1y 1 2 y 1y 2y 3 y 4y sy 6 y 7y 8y 9 各角上三个数的排列顺序没有变化，也就保持了原来的逆位数了，显然被3 整除。 园前面层顺时针转动9 0 度的情况 k 次转动之后的排列状态为( 后层的情况不变就略去了) ： c u y 6c b y 3 c l y sc f y 4c f y zc r y l f k c l y l 8c f y l 6c f y l 5 c r y l 3 c d y l 7c d y l 4 1 4 并且记为：y 1y 2v 3 y 4 y sy 6 y 1 3y 1 4y 1 s y 1 6y 1 7y 1 8 转动k + 1 次以后： c u y i 8c b y 5 c l y l 7c f y l 6c f y 4c r y 6 f k + 1 c l y l 4 c f y l s c f y 2c r y 3 c d y l 3 c d y l 并且记为：y 6y 4v s t q 6y 1 7y 1 8 y 3y 1y 2 y 1 5y 1 3y 1 4 其：b v 1 6y 1 7y 1 8 对应的这个角上的三个数顺序没有变，其他的三个角上逆 位数分别增加1 ，总逆位数改变3 ，最终逆位数依然被3 整除。 底层的变换情况与顶层的情况类似，其他三个侧层的变换情况与前层的情况 类似，可以同理证明。 由上面( 1 ) 和( 2 ) ，命题成立。 则( i v ) 情况出现仅有单个角块扭转的情况不存在，无论顺时针扭转还是逆时 针扭转。 综上，证毕。 定理3 2 把一个正常的魔方拆散后随意组装，不管在组装过程中发生了多少组装错误， 组装完成后总可以使这些错误化归为不超过三个方块的错误，并且化归后的错误 只能是以下1 1 类错误情况中的一类【1 6 】： 当其它所有方块都正确时 1 一个角块顺时针扭转； 2 一个角块逆时针扭转； 3 一个棱块原地翻转； 4 两个棱块对换； 5 一个棱块翻转且它同时与另一个棱块对换； 6 情况1 和3 的组合； 7 情况1 和4 的组合； 1 5 8 情况1 和5 的组合； 9 情况2 和3 的组合； 1 0 情况2 和4 的组合； 1 1 情况2 和5 的组合。 由定理3 1 ，我们可以看到定理3 2 中列举的情况1 到4 显然，其中两角对 换情况也是不符合定理3 1 的，但两角对换的错误状态可以通过一个转动序列 ( r 7u l 7u 2 r u 7r 7u 2 l r u 7 ) 转换为两棱对换的情况，所以不加考虑。 后面的7 种情况则都是定理3 1 中叙述的4 种基本情况的组合。 定理3 3 三阶纯色魔方的状态总数为4 3 2 5 2 0 0 3 2 7 4 4 8 9 8 5 6 0 0 0 【1 ，1 7 】，而其中任意一 种状态，都可以通过不超过2 5 步的转动序列还原之【6 】。 证明：定理的后半部分证明可参考文献【6 】，这里从略。 接下来给出三阶纯色魔方总状态数的计算的两种证明方法。 方法l ( 利用定理3 1 ) ： 参照物的选取不同，计算的方法也不同，但殊途同归，唯一区别的计算的繁 简。 固定中心轴为参照，整个计算过程比较简单： ( 1 ) 角位加角色的总状态数为：81 3 7 ( 最后一个角块色向随着前面七个角 的固定而固定，定理3 1 的应用) ( 2 ) 棱位加棱色的总状态数为：1 21 2 1 0 棱位变化：1 21 2 ( 当角位与中块位置确定后，理论上棱的位置状态是1 21 种， 但从定理3 1 可以看出，最后两个棱的位置是固定的，所以位置状态数为1 21 2 ) 棱色变化：2 1 1 ( 理论上色向变化是2 1 2 ，但从定理3 1 可以看出，最后一个棱 块的色向也是固定的，所以状态数为2 1 1 ) 则棱的总状态数为2 儿1 21 2 = 1 21 2 1 0 所以三阶纯色魔方的总状态数为： 81 3 7x1 21 2 1 0 - - 4 3 2 5 2 0 0 3 2 7 4 4 8 9 8 5 6 0 0 0 以上计算结果与国外官方网站发表的数据相互映证。 方法2 ( 利用定理3 2 ) ： 1 6 有了上面错误状态分析证明，可以按照另一种思路来计算三阶纯色魔方的总 状态数，首先按照排列组合的理论和方法，易知8 个角块在魔方上的全部可能的 组合可以看成是8 个角块的全排列，其组合数为81 ；同理1 2 个边块的可能的组合 数值为1 2 1 。8 个角块方向的可能的组合数为3 8 ，1 2 个边块方向的可能的组合数为 为2 1 2 。这样纯色魔方全部可能的图案组合数为81 1 2 1 2 1 e 3 8 。 但必须剔除错误的状态情况，按推论3 1 中论述的三种基本错误状态的情况， 棱方向装对的可能性是1 2 ，角方向是1 3 ，棱位置是1 2 ，所以正确的魔方状 态数应该在上面结果的基础上再除以1 2 。 则最后算出的状态总数为8 1 1 2 1 2 1 z 3 8 1 2 = 4 3 2 5 2 0 0 3 2 7 4 4 8 9 8 5 6 0 0 0 这与起初计算的结果一致。 3 2 2 置换和循环 在讨论完某些转动序列的不存在性原理之后，接下来我们研究序列的存在性 定理。在这之前，我们引入一些置换的定义及其基本性质【1 8 】。 设t n = ( 1 ，2 ，n ) 是一个从1 到固定正整数1 1 的集合，t 的置换即为t 到其 自身的一个双射。如果在三阶魔方中对9 x 6 = 5 4 个小面进行数字标记的话，那么 魔方的任何一次转动都可以看成是t s 4 的一个置换。 定义3 3 定义置换f ：t t 用一个2 x n 的数组表示： f h ( 岳) f ( 2 ) 2 ：f ( n ) n ) 如果f ：t t ，g ：t _ t 为两个置换，则它们的组合可以得到一个新的置换，记 为f g ：t _ t ： t h f ( t ) h g ( f ( t ) ) tt-+t 定义3 4 定义置换矩阵p ( f ) 为这样的一类方阵，它的元素( f ) 满足： 吖忙k 0j 嚣 c ；，p c f ) ( 三) = ( 篓妻i ) ； 字标记后，t s 4 的一个置换f h ( 三呈：) 即表示单棱翻转，对应的转动序列 动序列p x ，再添加r 的逆p x7 ，设和p x 对应的置换为g 和9 7 ，相应的置换矩阵 列，且这样的转动序列不唯一，关于4 种情况的可行转动序列如下( 同时，这里 列举的8 个基本序列将用于第4 章提到的策略算法) ： ( i ) 三棱置换序列： u fhu lhu r 卜专u f ：r 2 u r u r 7u 7r 7u 7r 7u r 7 序歹0 p i u fhu rh u lhu f ：r u 7r u r u r u 7r 7u 7r 2 卢手歹0 巴= r 7 ( i i ) 三角置换序列： u f lhu b rhu f rhu f l ：r 2 f 2 r br f 2 r br 7 一一序列p 3 u f li - - - , u f rhu b rhu f l ：r b 7r f 2 r 7b r f 2 r 2 一一序列p 4 = p 3 7 ( i i i ) 两棱原地翻序列： u f 和u b 相对两棱翻转：m 7u m 7 u m 7u 2 m u m u m u 2 ( 这里m 7 表示让魔方左边层与右边 层之间的中间层向背面转动9 0 度，m 则向相反方向转动9 0 度) 一一序列p s u r 和u b 相邻两棱翻转：l 7b 7r b l u 2 r 7 u 7r 7u r 2 u 2 r 7 一一序列圪 ( i v ) 两角原地翻序列： u f r 角块顺时针翻转，u b r 角块逆时针翻转：l u l 7u l u 2 l 7r 7u 7r u 7r 7u 2 r 一一序列p 7 u f r 角块逆时针翻转，u b r 角块顺时针翻转：r 7u 2 r u r 7u r l u 2 l 7u 7l u 7l 7 一一序y j p 8 在置换中，一个很常用的定义就是循环： 定义3 5 若置换f 满足f ( a 1 ) = a 2 ，f ( a 2 ) = a 3 ，f ( a r ) = a l ( r n ) ，且f ( i ) = i 当i a l ，a 2 ，a ，我们称这样的一类置换为循环，并且记为( a 1a 2 a ，) 。 定义3 6 两个循环( a 1a 2 a ，) 和( b 1b 2 b t ) 不相交当且仅当集合( a 1a 2 a ，) 和 ( b 1b 2 b t ) 不相交。 定义3 7 满足f n = 1 的最小正整数n 称为置换f 的阶数。 对于循环和置换阶，我们有下面简单的性质定理： 定理3 7 循环置换( a 1a 2 a ，) 的阶数为r ；如果f ，g 为两个不相交的循环置换， 则有f g - = g f 。 进而我们有以下重要的置换分解定理： 1 9 定理3 8 任意置换f ：t _ t 都能表示成不相交循环置换的积，更确切的说，如果f 是( 1 ，2 ，n ) 的一个置换，则存在非空不相交的整数子集： s 1 = ( a 1 1 ，a 1 ，r 1 ) c ( 1 ，2 ，n ) ， s 2 - - ( a 2 1 ，a 2 ，r 2 ) c ( 1 ，2 ，n ) ， s k = ( a k l ，a k , r k ) ， 这些集合满足( 1 ，2 ，n ) = s 1u us k ，n = r l + r 2 + + r k ，并且有 f = ( a 1 1 ，a 1 以) ( a k l ，a k , ，k ) 定理3 9 ( s t e i n h a u s ) 每个关于 1 ，2 ，n ) 非平凡的置换f 都能用2 一循环的序列积形式来表示： f = 1 1 _ - 1 ( a i ，b o ，其中1 k n ，n = n ! 一1 。 回到转动序列p 上，如果我们对魔方5 4 个小面做如下数字标记： 123 4u5 678 91 01 11 71 81 92 52 62 73 33 43 5 1 2l132 0f2 12 8r2 93 6b3 7 1 41 51 62 22 32 43 03 l3 23 83 94 0 4 14 24 3 4 4d4 5 4 64 74 8 那么生成p 的基本转动集( f jb ，l ，r ，u ，d ) 可以用不相交的循环标记如下： f = ( 1 7 1 92 42 2 ) ( 1 82 12 32 0 ) ( 62 54 31 6 ) ( 72 84 21 3 ) ( 83 04 11 1 ) ， 2 0 b = ( 3 33 54 03 8 ) ( 3 43 7 3 93 6 ) ( 394 63 2 ) ( 21 24 72 9 ) ( 11 44 82 7 ) l = ( 91 11 61 4 ) ( 1 01 31 51 2 ) ( 11 74 14 0 ) ( 42 0 4 43 7 ) ( 62 24 63 s ) r = ( 2 52 7 3 23 0 ) ( 2 62 93 12 8 ) ( 33 8 4 31 9 ) ( 53 6 4 52 1 ) ( 83 34 82 4 ) u = ( 13 86 ) ( 2574 ) ( 93 3 2 51 7 ) ( 1 03 4 2 61 8 ) ( 1 13 52 71 9 ) d = ( 4 14 34 84 6 ) ( 4 24 5 4 74 4 ) ( 1 42 0 3 03 8 ) ( 1 52 33 13 9 ) ( 1 62 43 24 0 ) 定理3 1 0 一个正确组装的三阶魔方，无论其处于什么状态，任意置换都可以转化为 2 一循环的积。特别的，任意偶置换都可以转换成3 一循环的积。 证明：由定理3 9 ，任何置换转化成2 一循环的积显然。考虑到偶置换转化的2 一 循环置换由( ij ) ( k1 ) 或者( ij ) ( jk ) 组成，而( ij ) ( k1 ) = ( ijk ) ( jk1 ) ，( ij ) ( jk ) = ( ijk ) ， 所以在魔方中，任意偶置换也可以转化成3 一循环的积。 定理3 1 0 同时可以提供实现魔方状态转换的一种分解策略。由于在魔方的 状态变化中，单独的2 一循环必不存在转动序列例如定理3 1 可以看到，单棱 翻转对应的置换就是一个单独的2 一循环，而实现这一操作的转动序列p 并不存 在。所以有时候，转化成3 一循环的积，有利于我们找到可实现实际操作的转动 序列p 有了以上的置换和循环概念和性质，以及对魔方序列存在性的讨论，将不难 阐释在第4 章中分析的关于魔方的一些重要的策略算法和应用算法。 第4 章魔方原理的若干应用 原理 b li n d f o l d ，一种先记忆魔方状态再闭眼还原的玩法 c ar f 博士发明的盲拧还辱洼【3 】越来越广的被玩家采用，盲拧 随之风靡。在中央电视台的 节目和2 0 0 9 年的春晚 方盲拧节目。这看似魔术般的神奇过程实际上只是蕴含着简单 第3 章中建丑的定理31 和36 ，并结合编解码原理，可毗做 编解码，视频中的编解码的概念略有不同，这里的编码由大脑 编码必须能反映出魔方的任意一种打乱状杰，为7 减少大脑的 吗越简单越好。解码的过程是在闭眼的情况下，根据编码方式， 来完成魔万的还原。 百行的编码如下 规定魔方的o o 面为高级面，f b 面为中级面，l r 面为低级面。 注意到一个棱块的两个色向一定包含o d 色或者f b 色，所以判断一个棱块 的色向位置正确与否，需要看该棱块的最高级色与所在位置的最高级面的相对位 置。即一个棱块两种颜色中相对高级的颜色如果处于相对高级的面，则棱块色向 正确，否则视为错误。 用o ，1 ，2 表示块的色向状态： 棱块色向正确：o ；不正确：1 角块色向正确：o ；需顺时针转：1 ；需逆时针转：2 而角块和棱快位置对应的数字编号如下： 1234567891o1 11 2 角 u f lu f ru b ru b ld f ld f rd b r d b l 棱 u fu l u b u r f l b ld r f r i ) f d l d b o r 这样，我们就可以用一组数字来确定整个魔方的状态，例如： ( i ) 角块色向编码：1 0 0 12 2 2 1 ( , - - 以发现加起来被3 整除) ； ( i i ) 棱块色向编码：1 1 0 00 1 1 10 1 0 0 ( 可以发现加起来被2 整除) ( i i i ) 角块位置编码：4 6 7 58 1 2 3 ( 数字1 到8 的一个排列) ( i v ) 棱块位置编码：61 2 52 71 048 31 1 19 ( 数字1 到12 的一个排列) 记忆的时候，还可以适当的简化编码，比如色向编码的数字串可以通过几何 图形直接记忆，位置编码中的数字串可以省略最后一个数字。在解码的时候，即 还原过程中，根据编码利用定理3 6 证明中提供的转动序列解码。 算法4 1 s t e p l ：依据角块色向编码和转动序歹 j p 7 ，p 8 解决角块色向 s t e p 2 ：依据棱块色向编码和转动序列p s ，p 6 解决棱块色向 s t e p 3 ：依据角块位置编码和转动序列p 3 ，p 4 解决角块位置 s t e p 4 ：依据棱块位置编码和转动序y j p l ，p z 解决棱块位置 s t e p 5 ：利用转动序列p o 解决剩余的一对角块和一对棱块位置 关于算法4 1 的说明： 1 s t e p 5 在必要的情况下执行，转动序列p 0 的操作为：r 7 u l 7u 2 r u 7r 7u 2 l r u 7 ； 2 实际操作中，s t e p l 到s t e p 5 常用转动序列p = 毁p n 7 ( o n 8 ) 来解决( 关 于的技术性寻找这里忽略不讨论) ； 3 有时候，叠加s t e p l 和s t e p 3 ，s t e p 2 和s t e p 4 则产生一种叫做二步法的盲拧 策略算法，这部分的基础技术文献可参考【1 9 】。 4 2 一种新的竞速还原算法 在提出一种新的竞速还原算法之前，先来看看竞技比赛中几乎9 0 以上高级 玩家采用的c f o p 策略【2 ，2 0 ，2 1 】，此策略算法的步骤如下( 每一步骤的实施都不 影响前一步骤的还原) ： 算法4 2 ( c f o p 策略算法【2 】) s t e p l ：完成底层十字，即还原底层四个棱块，使之位置和方向全部正确； s t e p 2 ：完成前两层，印还原前两层的四个角块和四个棱块，使之位置和方向全 部正确； s t e p 3 ：完成顶层所有块的方向还原工作，即一次性还原顶层的四个角块和四个 块的方向； s t e p 4 ：完成顶层所有块的位置还原工作，即一次性还原顶层的四个角块和四个 棱块的位置，从而还原整个魔方。 算法4 2 中s t e p 3 和s t e p 4 的可行性证明： 继续分解s t e p 3 和s t e p 4 ，利用定理3 1 和定理3 6 可证明其可行性，并且 得到的分解算法将是顶层的一个可行性基础还原算法。下面将看到可以看到 s t e p 3 即为s t e p 3 1 和s t e p 3 2 的叠加，s t e p 4 即为s t e p 4 1 和s t e p