魔方游戏的设计与实现论文.doc

毕业论文 第 41 页

毕业设计（论文）

设计（论文）题目： 魔方游戏的设计与实现
学生姓名
学生学号
专业班级
指导老师
院长 (系主任)

年 5 月 20 日

魔方游戏的设计与实现
摘 要

魔方是一种变化多端的智力玩具，又称鲁毕克方块，1974年由匈牙利建筑学教授鲁毕克发明。由于魔方的奥妙无穷，一直以来，不但有魔方游戏的大批爱好者，在学术界，对魔方也有着广泛而深入的研究，包括数学、物理等各个方向，魔方的研究成果也在许多领域得到了应用。
本文基于在计算机上实现一个魔方游戏的需要，对目前复原魔方中最常用的按层求解思想进行了深入的解析，抽象出一个按层求解算法，并最终把它转化为计算机上的算法实现。然后在此算法基础上，利用OpenGL API强大的场景渲染和描绘功能，设计了一个基于OpenGL平台的3D魔方游戏，通过对Windows输入消息的处理，使用户可以用鼠标和键盘手动操作玩魔方游戏，并且当求解有困难时，可以由计算机运用设计好的按层求解算法，进行魔方游戏的自动求解及其动画演示。
整个游戏设计友好简单，效果逼真，还具有自动求解演示功能，可以让玩家同时得到游戏的乐趣和解魔方的一些启迪。
论文最后对全文进行了总结，并对后续工作进行了展望。

关键字：魔方；魔方还原算法；求解效率；Windows 编程；OpenGL
Design and Implementation of Cube Game

Abstract

Magic cube is an intellectual toy with great variety; also know as Rubik’s cube, which was invented by the Hungarian architectural professor Rubik in 1974. Due to its endless profound, not only there are a number of fans to the magic cube game, also there are many wide and deep studies about magic cube in academia, including Math, Physics and so on, and the research can be applied to various fields.
The dissertation based on the need of implementing Rubik’s cube on the computer, giving an in-depth analysis to the “by layer solution” which is in common use in the cube’s recovery at present and abstracting a “by layer algorithm”, then realize the algorithm on computer at last. Next based on the algorithm, use the powerful scene rendering and depicting function of the OpenGL API, design a 3D cube game based on the OpenGL platform. By dealing with the input message, the user can play the game by mouse or keyboard. When the manual recovery is in trouble, the player can make the computer solve the cube by the designed algorithm automatically and offer a dynamic revolving effect.
The whole game has a friendly user interface and a vivid effect, along with a automatic solving function, making the players have both the game joy and the cube solving hint.
Finally, the conclusion of this dissertation has been given and the development trend has been predicted.

Key Words: magic cube; magic cube solve algorithm; solve efficiency; Windows Programming; OpenGL

目录
1 绪论 1
1.1 魔方的起源 1
1.2 魔方的构造 1
1.2.1 力学构造 1
1.2.2 数学构造 2
1.2.3 心理学构造 2
1.3 魔方研究概况 3
1.3.1 70年代 3
1.3.2 80年代 4
1.3.3 90年代 5
1.4 论文组织结构 5
2 自动求解算法分析 7
2.1 按层求解方案的具体应用 7
2.2 按层求解算法在计算机中的实现 15
2.3 本章小结 17
3 游戏的设计目标及实现 18
3.1 游戏设计目标及要求 18
3.2 游戏的功能点及其难点分析 18
3.2.1 魔方在计算机上的存储问题 18
3.2.2 魔方在计算机上的3D效果显示 18
3.2.3 魔方的旋转问题 19
3.2.4 游戏状态的加载保存 19
3.2.5 魔方的置乱和自动求解演示 19
3.2.6 魔方的自动求解算法 19
3.3 魔方游戏基本功能的实现 19
3.3.1 Cube类的设计 19
3.3.2 cube Handle 类的设计 21
3.4 游戏的程序框架 23
3.4.1 程序主体的实现 23
3.4.2 OpenGL场景渲染 23
3.5 本章小结 24
4 总结与展望 25
4.1 开发设计工作总结 25
4.2 魔方游戏的进一步研究 25
致谢 26
参考文献 27
附录 28

1 绪论
1.1 魔方的起源
魔方的概念起源于中国古代。
魔方通过转动能变化出无穷无尽的花样，然而转动是宇宙间最基本的模式。而令人惊奇的是，魔方的概念和思想起源于中国5000年前的洛书[1]。洛书上的九宫图，就是现在数学上的幻方或魔方。其后，人们对幻方一直有持续的研究，今天，数学上的幻方也转动起来了，这就是我们现在玩的幻立方体，也就是大家习惯称呼的魔方。现在魔方是一门科学或正将上升为一门科学。
1.2 魔方的构造
从外表看，魔方的结构似乎十分玄妙。但是，将魔方拆开来看，其力学结构十分精巧，几何结构非常简单。下面将介绍魔方的力学构造、数学构造和心理学构造。
1.2.1 力学构造
魔方的内部结构十分简单但非常精巧，所以我们有必要研究一下它怎么能够轻松拆散而且组装后又不至于散掉。为了分析魔方的力学结构，我们先对组成魔方的小块进行简单分析。魔方共有三种类型的小块：6个中心块（简称心块），12个边块，8个角块。心块只有一个色面，实际上是固定在一个六重心轴上，边块有两个色面，角块有三个色面。
魔方力学结构的根本诀窍就是小块彼此用脚相互钩在一起，任何小块都没有同另外的小块附着在一起。一个边块钩住两个角块的脚，两个角块又挤住一个边块，而心块又钩住边块和角块的脚。就这样，26个小块结合成一个整体，而每个表面的心块则是结合的基础。当任何一层（比如说上层）转动时，该层上的小块水平地彼此连接在一起，并且通过自己的中心和下面一层来适当地固定自己的位置。中层有一个略微陷进去的圆形轨道（由小块的缺口构成），它控制上层脚的运动，并且帮助上层结合在一起。
1.2.2 数学构造
上面，我们通过拆散魔方，了解了它的力学结构；现在我们通过组装魔方，来了解魔方小块的数学排列问题，称为数学构造。先组装角块，每个角块都能安插到8个角上的任何一个位置（称为角位）。这也就是说，一号角位有8个可能的角块来填充，二号角位有7个，三号角位有6个，等等。因此，把角块安插到角位里共有（即8！）种不同的方法。可是，每一个角块可能处于三个方向（色位）中的任何一个。因此，可以想到由于角块的色位方向还要再乘以因子。对于12个边块，也可以想到类似的情形。12个边块之间可以用12！种不同的方式置换，其次，因为每个边块还有两个不同的方向（色位），那么就还要再乘以一个因子在我们组装过程中，6个心块是固定不变的，因此，心块对于小块的排列（魔方状态）没有贡献。如果我们把以上四个数字乘起来，就得到519 024 039 293 878 272 000种可能的组装方式。
值得指出的是，以上估计的是指组装魔方时所能出现的排列花样，而拿一个魔方来操作，所能转出的花样（转出状态）要比组装出的花样（组装态）要少。比如，可以组装出这样的花样，即只有而且仅仅有一个小块的颜色反常，就是说，仅把一个角块转动一下，魔方的每个面上各小块的颜色就一致了。然而，只有一个小块颜色反常的花样，用旋转的办法不可能产生。因此，用旋转法产生的排列花样比用组装法产生的排列花样要少，即魔方的转出态比组装态要少。据此，可以估算出魔方的转出态约，仍然是一个庞然大数。
1.2.3 心理学构造
魔方的六个面有6种颜色。根据人类的视觉理论，颜色是外界光刺激作用于人的视觉器官而产生的主观感觉。颜色视觉既来源于外在世界的物理刺激，又不完全符合外界物理刺激的性质，它是人类对外界刺激的一种独特的反映形式。颜色视觉是客观刺激与人的神经系统相互作用的结果。一定波长范围的电磁波作用于人的视觉器官，经过视觉系统的信息加工而产生颜色视觉。因此，颜色是一种主观映像。我们这里是从描述观察者感觉的角度讨论问题的，因此属于心理学的范畴。
所谓魔方的心理学构造，就是根据颜色的心理学理论，来选取并排列魔方6个面的颜色，旨在增强魔方的刺激效果。根据哈德（Hard）和西瓦克（Sivik）的自然颜色系统理论（简称NCS理论），我们把魔方六个面着色成为上白（W），下黑（S），前红（R），后绿（G），左蓝（B），右黄（Y）。NCS理论把白、黑、红、黄、绿和蓝6种颜色称为纯色或原色。其它所有的颜色都看作是和这六种原色有不同程度相似性的颜色。根据NCS理论，红色可以和黄、蓝以及白和黑相似，而绝不能和绿色相似；同样，白色只能和红、黄、绿和蓝相似，而绝不能和黑色相似。其余依次类推。
1.3 魔方研究概况
魔方被列为20世纪最有影响的100项发明之一[1]，这并不是魔方爱好者们所为，而是社会学家根据魔方对人类的影响和作用，将魔方列入上个世纪对人类影响较大的100项发明之列。魔方的迷人内涵是魔方的科学隐喻，这是人们将永远要用到的。由于魔方复位非常之难，所以魔方首先引起数学家们的兴趣。随后有物理学家涉足魔方领域，现在，魔方成为人工智能领域首选的研究对象。本节按年代顺序综述魔方研究及其发展情况。
1.3.1 70年代
研究魔方的第一个人就是魔方发明人鲁毕克。1974年夏天，鲁毕克成功地研制出第一个魔方，兴奋之余，随意地旋转了几下，却发现被扭乱了的魔方无法还原[2]。他花了好几个星期的时间去研究各小方块的位置关系，最后才使魔方恢复原状。他想，这实在是一种很有教育价值的智力玩具，于是，写下了这种玩具的详细说明，并决心大量生产它。第一批商品魔方于1977年在匈牙利问世。1978年，在芬兰首都赫尔辛基召开的一次国际数学家代表会议上，匈牙利的数学家们把魔方介绍给与会的专家、学者，引起了人们极大的重视。随后，在英国出现了第一批魔方理论研究小组，其中数学家戴维德·辛格马斯特(David Sing master)被誉为魔方大师，他的专著《Notes on Rubik’s “Magic Cube”》(1980年)至今仍是魔方研究者和各种各样魔方爱好者的无可争议的参考书[1]。辛格马斯特教授在世界上被誉为是魔方问题的数学权威。他是美国加利福尼亚大学伯克利分校的数学博士，现在英国一学院任教。辛格马斯特建立了一个世界魔方交流中心，搜集了20多种变态魔方，7种魔方专著。
1.3.2 80年代
20世纪80年代，魔方时髦达到第一次高峰。当时魔方被誉为是世界上“至今发明的最有教育意义的玩具”。玩魔方被认为是测验智力锻炼思维能力的体育活动。
1980年7月，美国麻省理工学院（MIT）成立了魔方爱好者协会，1981年3月，《科学美国人》（Scientific American）发表了第一篇关于魔方的论文，1981年5月，美国的《读者文摘》（Reader's Digest）出版了关于魔方的故事。同年秋天，戴维德·辛格马斯特出版了第1期《环球魔方》（Cubic Circular）杂志，年底，美国举办了第一届全国魔方锦标赛。1982年1月，美国人彼得（Peter Sebesteny）提出 魔方的专利申请，1982年3月，加拿大在多伦多举办第一届世界魔方锦标赛，这年春天，戴维德·辛格马斯特出版了第2期《环球魔方》，5月，美国新闻媒体出现了第1期关于魔方的时事通讯，夏天，第3/4期《环球魔方》出版，6月举办了世界魔方大赛，冬天，第5/6期《环球魔方》出版。
80年代魔方研究的热潮主要集中在80年代初的几年。据辛格马斯特为作者提供的信息，1981年创办的《环球魔方》杂志，只出版到第8期(1985年) [1]。因此，暂将80年代魔方研究成果主要概括为下面两个方面。
1.3.2.1 魔方和数学
魔方首次风靡全球时，其最吸引人的是还原问题。因此，当时的数学家们出尽风头。他们根据群论和线性代数等专门的数学理论和知识，借助电子计算机，得到了各种各样的魔方复原方法。群论是研究对称性的科学，特别是转动群理论和魔方更是有着近乎又近的关系。我们知道，一般玩魔方都必然要转动，群论可以告诉操作者魔方转到什么状态了，从而可以帮助操作者找到原始态。英国数学家蒂斯特勒思韦物（Thistlethwaite）曾运用群论的思想来指导计算机搜寻特殊种类的变换方法,他求出的解答方法最多只需52转[1] (一个90°的转动或 180°的转动都算作一转)，迄今为止，英国数学家辛格马斯特教授的股份有限公司仍用一个需52转复原的魔方作为商标。52转法可能是目前世界上最短的复原方法，根据这种方法，得到最后几步才开始出现向解决态靠近的趋势。大多数人最初的算法都需要几百转，经过很多次修改的算法也需要80多转或90多转。有一些复杂的群论设计估计，从初始状态到最远的状态只需要22或23转，或许今后有人会创造出比52转更短的算法，也许是22或23转的算法。但到目前为止，还没有人知道怎样从魔方的一个状态经过最少的转动而达到另一个状态；也没有人知道，到底有没有一个简易的方法，能够告诉你离开初始态有多远？这也是魔方引人入胜和经常争论的问题之一。总之，群论最先闯入魔方领域，并从根本上支持将魔方上升为一门科学。
1.3.2.2 魔方和物理学
据《科学美国人》报导，Golomb首次建立了魔方和粒子物理的关系。对于魔方操作者来说，不可能找到这样一个操作序列，它只使得一个角块扭转1/3转，而其它所有的小块都还保持不动。粒子物理学中具有+1/3电荷的基本粒子及其具有-1/3电荷的反粒子，这些粒子在物理学中被称为夸克和反夸克。如果把魔方角块顺时针方向扭转三分之一称为一个夸克，而把反时针方向的扭转三分之一称为一个反夸克。正如魔方角块的1/3操作一样，夸克粒子是既撩人心弦，又难以捉摸，所以现在许多理论物理学家都相信夸克禁闭原理：即不可能找到孤立的自由夸克(或反夸克)。这种魔方的夸克和粒子夸克之间的类比是一种很好的对应关系。实际上，它们之间的关系还可以更深入一些。夸克粒子不能自由存在，但是它们结合在一起而存在：夸克—反夸克对就是介子，三个夸克具有整数电荷就是重子。十分令人惊奇的是，在魔方中能够使两个角块各扭转1/3，只要它们的扭转是反方向的(一个是顺时针的，另一个是反时针的)。也可以使三个角块各扭转1/3，只要它们的扭转是同方向的。Golmb把具有两个相反扭转的角块的状态称为一个魔方介子，而把具有三个同方向扭转的角块的状态称为一个魔方重子。有关魔方粒子的产生操作，读者可参看第十章。在粒子世界中，只有具备整数电荷的夸克组合才能存在。而在魔方世界中，也只有整数扭转量的夸克组合才能成立。
1.3.3 90年代
90年代，随着网络的发展，魔方得以在网络上广泛传播，其内容主要是关于三阶魔方的。归纳起来有魔方数学，魔方复位和魔方动画等方面。
1.4 论文组织结构
论文全文共分四章
第一章：绪论。简要介绍魔方的基本概念、构造及其国内外研究发展状况。
第二章：自动求解算法分析。论述了进行魔方自动求解的按层求解算法及其实现。
第三章：游戏设计目标及难点。通过提出游戏设计目标及其功能点、难点，对设计游戏进行大概的把握，接着详细说明了游戏的基本功能及程序主体的实现，结合第二章所实现的自动求解算法，最终形成一个完整的魔方游戏。
第四章：结束语。总结了游戏的设计开发工作并对未来的魔方游戏可能的扩展进行了展望。
2 自动求解算法分析
目前对魔方的求解算法很多，有穷举法、全排列和递归求解法[3]、树搜索算法[4]等。这些算法，都有一些不足之处，如穷举法，它要计算魔方的所有状态，其数量巨大，效率低下；树搜索算法需要比较复杂的数据结构和算法技巧的运用。目前也有人针对魔方提出了一个人工智能的搜索算法，并建立了数学模型[5]。本章将对按层求解思想[6]在此进行详细的剖析，先说明在现实中手动还原魔方时，按层求解思想的具体应用，然后再抽象出一个按层求解算法，并把它在计算机中实现。按层求解算法将是本游戏中实现魔方自动求解演示所采用的算法。
2.1 按层求解方案的具体应用
首先，先说明求解过程中要用到的一些术语。正如先前阐述魔方所说的，魔方单元块有3种，6个固定的中心块，只有一个颜色面，以自己为轴旋转，8个角块，有3个颜色面，12个边块，有2个颜色面，都是饶中心块旋转。由于中心块固定，它的颜色决定了魔方表面的颜色。对各个块，通过旋转能达到3种状态，即：归位、定向、还原[7]。块归位是指所需块已经正确的位置，但各面的方向不一定合适，需要通过旋转来调整。块定向是只所需块的各面的方向已经正确，但还未到达正确的位置。块还原是指块的位置和各个面的方向都已正确。
再介绍一下转动的符号图解：

图 2.1 转动符号图
图2.1中最上的符号表示魔方水平方向层的转动，有3层不同的方向。
图2.1中中间的符号表示魔方竖直方向层的转动，有3层不同的方向。
图2.1中最下的符号表示魔方的整个前表面的顺-逆时针2种转动。
现在我们先选取一个中心块，颜色可以任意选择，在下面的例子我们就使用蓝色中心块，把它旋转到魔方的上表面。然后我们取一个有蓝色面的角块，通过旋转到魔方的上层，并使它的上表面颜色与中心块颜色一致，假定它旋转到魔方前面的右上角块位置，如图2.2所示，为一个蓝-红-白角块，白色在前面，红色在右面，蓝色在上面。通过这种方式准备好魔方，我们已经解决了魔方上层中的2个方块，接下来我们准备解决其余的。

图2.2 开始状态图
现在，我们分7步，开始对魔方进行按层求解[8]。
步骤一：复原魔方顶层，定位所有角块使该层各面颜色一致
当我们准备好一个魔方之后，就已经解决了顶层的一个角块，现在我们准备解决其余的三个。先整体向左旋转魔方，从而使原来的那个角块转到了魔方前面的左上方角块位置。在这个例子中，如图2.3所示，你能看到左上方角块现在是原来的那个蓝-红-白角块，其前面为红色(因为我们已经把整个魔方向左旋转了)。现在我们又需要解决转到右上方的那个角块了，所以需要先计算是哪个角块要放置到那。其实这个很容易。既然这个角块必须有一个蓝色面(否则的话，就不能和顶层颜色匹配了)，它还必须有一个红色面(否则的话，就没法让前面为红色了)，因此只需简单的找一个有蓝、红2种颜色的角块就行了，在此，我们假定找到的是一个蓝-红-黄角块。接下来的步骤是转动目标块到魔方的右下角块位置(我们用黑色标记来帮助确认目标位置)。这个魔方单元的蓝、红、黄色面可以是任意的顺序，并在任何的一个面，只要这个方块在正确的位置就行了。通过旋转底层，顶层不动，直到目标块归位。一旦目标块已经到了前面的右下角块位置，根据顶层色面(蓝色)所在的位置，我选择如下的方案(图2.4)来把它转到右上角块位置。
举例说，如果所需的蓝-红-黄角块碰巧它的蓝色面在魔方的右边(图2.3的位置1)，我们就可以使用算法1，如果是在前面(图2.3的位置2)，就可以使用第二种算法。最后，如果蓝色面是在底部(图2.3的位置3，图中手所指示的底部)，那么就可以使用算法3了。也有可能目标蓝-红-黄角块已经在顶层位归位了(同样用黑色来表示目标)，但是还没有定向(红色面没有和初始块的红色面一致)。如果蓝色面在前面(图2.3的位置4)，使用算法4，若在方块的右边(图2.3的位置5)，当然就使用算法5了。如果愿意，也可以从其他的方向开始，只要牢记实现所有顶层角块的上面颜色和顶层颜色匹配的目标就行了。如果所需的立方块转到了中间层，就跳过去处理另一个角块，一旦完成，目标块就会转到顶层或底层。当把这些角块都完成后，魔方就应当看起来像一个图2.5所显示的一个迷你小魔方，魔方的上部就是一个蓝色的“X”，并且其所有角块的颜色和其他角块颜色水平匹配。接下来，我们就可以完成边块来复原顶层了。

图2.3 步骤一状态图

图2.4 步骤一求解图

图2.5 步骤一目标图
步骤二：复原魔方顶层，定位所有边块使该层各面颜色一致
既然我们已经掌握大体思想，知道了该怎样找到目标方块并将其旋转至合适的位置，现在要做的是复原魔方顶层。按照第一步的思维，我们现在需要寻找合适的角块（蓝色）（这些方块被合适定位后，相邻四面的第一排也将分别颜色一致）并将它们旋转至合适位置。简单地旋转中层及底层，使目标方块处于图2.6标示出的位点（被涂黑的点）。根据这些方块不同的位点，分别按以下方案（图2.7）旋转它们至边角位置。当你完成前两步，魔方的整个顶层已被复原，其形态如图2.8的迷你小魔方。

图2.6 步骤二状态图

图2.7 步骤二求解图

图2.8 步骤二目标图
步骤三：复原魔方中间层，使该层各面的边块按颜色对齐，然后定位角块
现在我们来进行第三步，首先旋转中层，使其中部方块与顶层中部方块的颜色一致。按照前两步的思路，如图2.9，你可以看到红色和黄色中部方块分别与它们上面的方块颜色一致。这样，四个竖直面上就形成了“半T”。一旦所有的中部方块已对齐，中层的复原工作已部分完成。现在唯一要做的是定位剩下的边角方块。现在，让我们仅仅旋转底排，使底排的所有中部方块与中层相应位置的方块颜色一致，这样各个竖直面上就形成了“全T”。在我们的例子中，如图2.9，旋转底排我们可以得到红色的“全T”。 在我们的例子中(图2.9)，旋转底排我们可以在前部得到红色的“全T”，与此同时如果左面底排中部方块是白色，或右面底排中部方块是黄色，我们就称T底部的红色方块为“目标红”。“目标红”存在的情况下，我们就可以通过下图所视的两种方案把它转到左方或右方的边角位置。同样用以下的方案（图2.10），如果我们不能得到“目标红”，我们就只能转而在竖直面上寻找其他色的全T，并且也需要检测其是否为类似的“目标白”，“目标黄”等，你最终总会找到这样一个全T，并将“目标*”转到边角位置。同样的方法类推，最后你得到的魔方形态如图2.11所示的迷你小魔方。

图2.9 步骤三状态图

图2.10 步骤三求解图

图2.11 步骤三目标图
步骤四：复原底层，将魔方翻转，归位角块
现在，你将魔方的顶部朝下放置，如图2.12所示，我们的魔方中，前部要定位的两个边角（标签1，2所示）便都拥有红，绿两色的面。按逻辑知，背部为橙色，所以标签3，4则都拥有橙，绿两色。我们必须确保具有不同三色的边角在正确的位置，比如，红-白-绿三色的角只能处于位置1。图2.13是两个可能用到的方案。
每次翻转完，请仔细观察确保你最终只是对第一排进行了旋转，看看前部角（含红色面）和后部角（含橙色面）是否在它们应处的位置，而不影响其他已经完成的两层。一旦前部角（或后部角）已经相邻，你会发现此时你需要调换它们的位置，你只需根据上面的转换方案一进行操作。至于后部角，你将红色一面与橙色一面调换后，方法一样。但如果前部角（或后部角）相对，则使用图2.13的转换方案2。完成这一步，你差不多已经完成了角块的定位，只是可能还不完全。

图2.12 步骤四状态图

图2.13 步骤四求解图

图2.14 步骤四目标图
步骤五：复原底层，全部复原底层角块
在这一步骤，转动最后一层的角块到他们的最终位置。在我们的这个魔方中，绿色为底层的颜色。要还原这些角块，需要注意影响到绿色面的3种不同的构造。使用图2.15的图示，调整魔方整体的位置，使得你正视它时，看到的是如图2.15所示的3种效果中的任意一种。在本步骤中，其余的面(或魔方的其他部分)并不受影响，所以就没有把它们显示出来，包括底层的其他绿色面。
在魔方中，一般总是可以找到这3中排列情况中的一种的，一旦找到，就可以使用下面的转动方案(图2.16)。这个方案需要执行好几次，每次都要确保找到绿色面的正确的排列情况，然后用其余的2种排列情况继续(不要老是找同一种情况，否则会陷入死循环)。如果在本步骤开始时找不到这开始的构造，那么你执行一次这个算法，然后就会找到它们中的一种了。

图2.15 步骤五状态图

图2.16 步骤五求解图

图2.17 步骤五目标图
步骤六：复原底层，复原2个边块并准备复原剩下的2个
现在你会发现在最后一层，最少有一个剩余的边块已经归位了，尽管它还没有定向。整体翻转魔方，让已经定向的块所在的面转到前面(某些情况下，可能会有2个这样的面供选择)。在我们的图示（图2.18）中，有一个绿-白边块的面被置于前面，因为那个边块已经归位了(只需通过翻转进行定向了)。然后执行图2.19所示的归位算法把其余的边块进行归位(需执行2次)。如果找不到一个合适的边块来开始，那么先执行这个转动方案（图2.19）一次，然后再像刚才那样处理就行了。

图2.18 步骤六状态图

图2.19 步骤六求解图

图2.20 步骤六目标图
步骤七：完成魔方解决方案，复原最后的2个边块，以复原整个魔方
现在我们就快复原整个鲁比克魔方了。此时就只需关心最后未完成的那层了，所以魔方的其他层没有显示出来。几乎在所有的情况下，经过上面6个步骤后，这一层有2个边块已经还原了，2个边块未还原。而这未还原的2个边块，也是已经归位而只需定向了的。向前正视魔方，然后整体转动，直到未还原的2个边块和图2.21所示的状态中的一种一致。在图2.21中，2个已经还原的边块为粉色，未还原的则为紫色。准备好之后，执行下面的应用于最后一层的方案(图2.22)来最终还原魔方。图2.21中的第一种情况，看起来像一个"H"，我们称为"H"模式；而第二种情况看起来像一只鱼(Fish)，我们称之为"Fish"模式。在某些情况下，当你完成前6步后，所有的四个边块都已经转到位了(通常只有2个边块)，那么就执行"H"模式算法一次，然后就会发现届时已经处于这2种模式中的一种了，通过图2.22所示的方案，整个魔方就被还原了。

图2.21 步骤七状态图

图2.22 步骤七求解图

图2.23 步骤七目标图
2.2 按层求解算法在计算机中的实现
对上面按层求解的思想，把它转化为计算机语言，就能在计算机上通过一定的算法把它给表示出来了。算法分为7个步骤，如下：
步骤一：上层四个角块还原。
步骤二：上层四个边块还原。
步骤三：中间四个边块还原。
步骤四：下层四个角块归位。
步骤五：下层四个角块定向。
步骤六：下层四个边块归位。
步骤七：下层四个边块定向。
对具体每步的算法实现，可见附录，每个步骤对应了一个实现的函数体。
现就7个按层求解的函数体中所调用的其他的一些函数的功能做以下说明：
FindCen(int a)，返回所给颜色的中心块位置。
FindEdge(int a, int b) ，返回所给颜色的边块位置。
FindCorn(int a, int b, int c) ，返回所给颜色的角块位置。
UL()，顶层向左转。
UR()，顶层向右转。
DL()，底层向左转。
DR()，底层向右转。
LU()，左层向上转。
LD()，左层向下转。
RU()，右层向上转。
RD()，右层向下转。
FC()，前层顺时针。
FA()，前层逆时针。
BC()，后层顺时针转 (从前面看) 。
BA()，后层逆时针转 (从前面看) 。
ML()，中间层左转。
MR()，中间层右转。
MU()，中间层上转。
MD()，中间层下转。
MC()，中间层顺时针转。
MA()，中间层逆时针转。
CL()，魔方整体左转。
CR()，魔方整体右转。
CU()，魔方整体上转。
CD()，魔方整体下转。
CC()，魔方整体顺时针转。
CA()，魔方整体逆时针转。
XCL()，魔方整体左转，中间层不转。
XCR()，魔方整体右转，中间层不转。
XCU()，魔方整体上转，中间层不转。
XCD()，魔方整体下转，中间层不转。
XCC()，魔方整体顺时针转，中间层不转。
XCA()，魔方整体逆时针转，中间层不转。
以上函数体在求解步骤中的函数得到了调用，其具体调用过程就体现了魔方的解法。
2.3 本章小结
本章主要讨论魔方的自动求解算法，重点是其中的按层求解算法，这也是最普遍使用的按层求解魔方思想在计算机中的体现。相对于其他的算法来说，按层求解算法思想明确，易于理解和接受，而且求解的步骤亦相对的精简。而像全排列和递归求解法和树搜索算法]等其他算法，都牵涉到比较复杂的数学计算、数据结构和算法技巧，实现起来亦要相对的复杂，效率也并不比按层求解算法要高。在本程序中，所实现的按层求解算法还有一些改善的余地，求解的步骤还可以去进一步的去精简，这可做为将来研究的一个工作。有了求解算法的实现，就可以在此基础上实现一个可以自动求解的魔方，这将是下一章讨论的内容。
3 游戏的设计目标及实现
本章首先提出了魔方游戏的设计目标，然后针对具体的设计目标进行难点分析和可以采取的途径，依照分析，可以得出游戏设计与实现的大概方法。最后，对游戏的具体实现进行了详细的说明，确定了实现的技术方案和细节。其中，对魔方的自动求解功能的实现，将依赖于前面所探讨的按层求解算法。
3.1 游戏设计目标及要求
考虑到现实中魔方的基本功能，游戏需要提供一个平台，它可以在计算机上显示魔方的3D逼真效果，可以让玩家手动操作魔方的旋转，可以自动演示魔方打乱后任意状态的复原。要求游戏界面友好简单，玩家可以轻松玩游戏，能够加载上次的游戏状态以及保存任意时刻的游戏状态，并在游戏中随时得到计算机的帮助完成魔方的复原。
3.2 游戏的功能点及其难点分析
整个游戏的概念比较的简单，即在计算机上可以展示一个3D魔方并可以手动操作它，但其实现还是会有一些难点问题需要解决[9]。
3.2.1 魔方在计算机上的存储问题
一个3维3阶魔方可由2 7个小立方块组成，其中一个在魔方的正中心，整个小立方块不可见，其余可见的2 6块中，有６个在面中心(一个面可见)，８个在角上(3个面可见)，1 2个在棱上(2个面可见)。在计算机上表示魔方时，其可见的块，可见的面都必须进行存储，同时，魔方6个不同的面由不同的颜色值进行区分，其颜色值也需存储。这样，我们可以有一些不同的选择。可以只存储看得见的一些面，这样会相对的复杂，因为你必须对每个小立方块的每个面进行判断它是否可见；也可以简单的存储所有的面和它的颜色值。
3.2.2 魔方在计算机上的3D效果显示
基于游戏的便利性和逼真性，魔方的6个面必须立体的组合在一起，而不是简单的平铺在计算机的显示屏幕上。这就需要对魔方的显示进行特殊的处理以实现其3D立体效果，在这方面，需要用到计算机图形学的一些知识，使用OpenGL[10]或者DirectX[11]都是可能的选择。
3.2.3 魔方的旋转问题
游戏过程中，需要通过鼠标或键盘控制魔方的整体旋转和魔方6个面不同方向的单层旋转。对每个面的单层旋转，需要使它慢慢的转动以实现一定的动画效果，使得游戏更具有逼真性。
3.2.4 游戏状态的加载保存
为便于玩家不必每次从头开始玩，许多游戏都有游戏状态的加载和保存。由于魔方游戏也比较的复杂，玩家短时间不能将其复原，因此可以考虑将玩到中途的魔方的状态进行保存，以便于在下一次继续玩。
3.2.5 魔方的置乱和自动求解演示
游戏有自动打乱和求解功能，可以对一个初始的魔方进行自动的随机旋转进行魔方的打乱，并在任意时刻对一个状态混乱的魔方进行求解并进行自动复原的演示。
3.2.6 魔方的自动求解算法
魔方的自动求解算法是实现魔方自动求解演示的依赖，由于魔方变化复杂，其状态繁多，穷举似乎不可能，只能通过推导，按照某种算法原则去求解。因此，自动求解算法的实现将是本游戏实现中最大的难点。
3.3 魔方游戏基本功能的实现
在游戏的实现中，设计了几个类，以完成游戏的功能，本节对这些类依次予以说明。
3.3.1 Cube类的设计
组成魔方的小立方块是一个独立的单元，在此将其称为一个魔方单元，可以设计一个Cube类来表示。Cube类的声明如下图所示：

图3.1 cube类
每个小魔方单元由6个不同的颜色面组成，则有6种颜色属性值，而每个颜色值又由RGB三个颜色属性决定，因此可以存储在一个二维数组sideColor[6][3]中，魔方单元有一个中心三维坐标centerCoordinate[3]，数组包含中心坐标的X、Y、Z三个属性，可作为确定魔方单元的唯一标志。
在绘制魔方单元时，实际就是绘制6个不同的颜色面，组合在一起就是一个立方体的效果[12]。对不同面的颜色值的设置，我们用面在坐标系中的方向来决定。规定，正X方向为黄色，负X方向为绿色，正Y方向为红色，负Y方向为紫色，正Z方向为蓝色，负Z方向为青色。因此，cube类中用一个数组direct[6]来存储魔方单元的6个方向值，以作为绘制魔方单元时确定面颜色值之用。
当魔方的某个面朝某个方向进行旋转时，其涉及的魔方单元在三维坐标系中围绕面中心进行旋转。则这些面的颜色值务必要发生改变以实现这种旋转的效果，由于魔方单元每个面的颜色值由它的方向所决定，因此要对魔方单元的各个direct值进行重新设定，以体现其在坐标系中的旋转变换，这里用用3个函数来实现，turnByX(int sign)、turnByX(int sign)、turnByX(int sign)， 分别表示魔方单元饶X、Y、Z轴方向进行旋转，其中sign为正反方向的标志，用-1来表示反方向，1来表示正方向。
设立DrawCubeUnit()方法通过调用openGL的API生