智力五环1

智力五环1 智力五环(B型)解决算法的研究 摘 要: 益智力游戏需要玩家对游戏规则进行思考、判断，其玩法比较多样化。由于益智类游戏 对启发人类的思维，培养人类的发散、创造性思维有着重要的作用，而且游戏操作不需要太 高要求，所以是现在受众面最广的游戏类型之一。 本文以智力五环游戏为研究课题。首先模拟智力五环模型设计游戏软件，对该软件的设 计思想、过程及重要模块功能进行详细的说明。在此基础上对游戏的算法进行深入的研究， 归纳游戏算法的基本规律，并找到解决算法命题的方法，最终实现算法演示程序 关键字:智力五环(B型) ;算法分析; 算法设计 The Algorithm Research On Five-Ring-Game (B Version) Abstract Puzzle games need the players to think and judge the rules of the game. It has more diverse ways to play. Because puzzle games play very important role in enlightening human thought’ cultivating human divergence and creating thought , the games’ operating do not require too high . It is became one of the popular game for the more audience. This thesis studies the Puzzle-Five-Ring-Game. First step, design the game software following the intellectual Wuhuan modeling. And make out detail explaining for the software designing 、processing and important functions module. On the base of the software ,make deep research on the algorithm of the game, summed up the basic rules of the game algorithm. Find a solution method for the proposition. In the end , achieve the performance of the algorithm. Key word: Puzzle-Five-Ring-Game(B Version);analysis of algorithm ; design of algorithm 1 目录 1. 绪论 ......................................................................................................................................... 3 1.1. 选题背景 ................................................................................................................... 3 1.2. 研究的目的和意义 ................................................................................................... 3 1.3. 五环游戏的结构介绍 ............................................................................................... 3 1.4. 课题主要工作 ........................................................................................................... 4 1.4.1. 五环游戏的理论研究 ....................................................................................... 4 1.4.2. 状态的表示和走法得产生 ............................................................................... 4 1.4.3. 搜索算法 ........................................................................................................... 4 2. 游戏软件设计 ....................................................................................................................... 5 2.1. 软件实现的功能 ................................................... 5 2.2. 开发环境 ......................................................... 5 2.3. 设计思想 ......................................................... 5 2.4. 游戏流程图 ....................................................... 6 2.5. 游戏界面设计 ..................................................... 7 2.6. 智力五环游戏界面 ................................................. 7 2.7. 设计任务 ......................................................... 8 2.8. 游戏的自动演示 .................................................. 11 2.9. 游戏的提示功能 .................................................. 11 3. 数据结构 .............................................................................................................................. 11 3.1. 循环队列赋值 .................................................... 12 3.2. 结构体和类的使用和介绍 .......................................... 12 4. 算法命题分析 ..................................................................................................................... 13 4.1. 分命题分析 ...................................................... 14 4.2. 算法命题规律 ................................................ 15 5. 算法设计 .............................................................................................................................. 15 5.1. 棋盘局势状态表示和走法产生 ...................................... 15 5.2. 棋盘中棋子转动的实现 ............................................ 16 5.3. 棋子的走法产生 .................................................. 16 5.3.1. 棋子的搜索 ........................................................................................ 17 5.3.2. 搜索算法的优化 ................................................................................ 17 6. 算法演示的实现 ................................................................................................................. 18 6.1. 第一步: ........................................................ 18 6.2. 第二步: ........................................................ 18 6.3. 第三步: ........................................................ 18 7. 算法分析 .............................................................................................................................. 20 7.1. 算法异同比较 .................................................... 20 7.2. 问题讨论 ........................................................ 20 8. 结束语 ................................................................................................................................... 21 8.1. 总结 ............................................................ 21 8.2. 展望 ............................................................ 21 2 1. 绪论 1.1. 选题背景 自古以来游戏在培养人类体、德、智等方面发展中起了重要的作用，其中有代表性的游戏有:九连环、华容道等。其对开发人类智力具有独特的功能。在实践中，无论是民间还是宫廷，更是创造出了种类齐全、花样繁多的游戏活动，这无疑是给我们人类的今天遗留一份宝贵的遗产 在当今注重智力培养的时代，智力游戏更受到人们的关注，其对培养人的发散思维，开拓人的创新思维有着重要的作用。在提高学生学习的积极性方面也有不可忽视的优势。 本文是以智力五环(B型)为研究课题，在讨论了计算机软件的设计思想、过程、实现方法之后，重点对游戏的算法进行的分析和研究，给出了解决游戏算法的最新法案 1.2. 研究的目的和意义 本课题具有综合性的特点，有求学生具有较好的数学基础，较扎实的数据结构知识，具备较强的算法设计能力。完成本课题具有以下意义: 1) 提高学生获取新知识的能力，培养学生终身学习能力; 2) 培养学生的科学研究能力，培养学生分析问题和解决问题的能力; 3) 锻炼学生综合性、灵活性应用知识的能力，培养求真务实的工作态度和 作风; 1.3. 五环游戏的结构介绍 智力五环在设计思路上，由五种不同颜色的圆环和一个共用五种颜色圆环棋子的大圆环组成、将五种颜色的圆环和中间的大圆环设计成轨道的形式，再在圆形轨道内设置若干不可脱落的彩色的棋子。实物模型如图1。 图1-1智力五环(B型)实物模型 智力五环游戏玩法规则简单，其玩法具有多种多样，但要求玩家对规则进行 3 判断和思考。处在五个小环上的棋子只能在其原有环上进行彼此覆盖，而处于中间转盘上的棋子则可以随着小圆环转动移到小圆环上，通过圆环反复的转动，完成颜色的归位。 在游戏中通过色彩鲜艳的色子或数字变化，可以培养记忆力及空间想象力，优化思维步骤，增强逻辑思维能力，加大思维的转换跨度。智力五环(B型)游戏玩法简单、乐趣无穷 ，充满了挑战性，任何人想要玩好她，都需要充分发挥智力，还必须有较高的耐性、毅力。它的难度超过了华容道、九连环等，但又不像那样让人难以破解，游戏过程还是有一定的规律的，是一类十分难得的新型智力游戏。 1.4. 课题主要工作 本课题的主要工作是将数据结构的知识应用到五环游戏的研究和实现中，建立计算机下五环游戏的基本模型。主要研究和解决的问题如下: 1.4.1. 五环游戏的理论研究 对五环游戏的相关知识进行认真的整理，针对五环游戏玩法规则简单、局势判断清晰的特点，对五环游戏的开始状态进行复杂程度的设计通过反复的手动把玩，总结其玩法规律，寻找其最快玩法算法，阐述其最新玩法规则。 1.4.2. 状态的表示和走法得产生 将五环游戏的具体问题转换成能够在计算机上进行存储与处理的数据实现。如何在计算机中表示游戏的过程，以便程序知道游戏的状态。 产生合法的走法规则，以便游戏能正常的进行，对于不同的游戏，其走法产生存在巨大的差异，五环游戏的走法相对而言比简单。 1.4.3. 搜索算法 通过搜索算法实现目标棋子的选择 4 2. 游戏软件设计 2.1. 软件实现的功能 用C++语言编写一个智力五环游戏(B型)的应用软件，设置出友好、明了、功能齐全的游戏界面。给出棋盘界面、游戏难度、步骤、自动演示以及提示功能的关键代码说明。当游戏开始时将圆环上的棋子进行混杂，点击顺转、逆转按钮转动圆环，通过大小圆环上的棋子相互覆盖，最终使得小圆环上的棋子颜色达到一致。界面上的“文件”菜单中点击“等级”来设置游戏的复杂程度，其中包括“低级”、“中级”、“高级”。打开“帮助”能够看到游戏规则说明。在菜单项中点击“下一步”可以给玩家提示下一步的玩法，点击文件里的“算法演示”可以实现整个游戏的完成过程，其中用到了搜索算法、递归算法、排序算法。 2.2. 开发环境 系统平台:Windows XP，VC++6.0 开发语言:C++ 开发工具:VC++6.0 参考文档:MSDN 2.3. 设计思想 智力五环(B型)是一款单机智力游戏。设计思想源于初等数学中“圆环”的性质及高等数学中拓扑学的概念等。设计过程中首先是做五个环，每个环上有7个棋子，一共有五种颜色。每个环通过按顺转、逆转按钮实现转动，在小圆环中，每按一次只能使棋子交换一个位置。中间的大转盘通过点击按钮可以使在盘内的10个棋子每2个为一组进行位置的交换。 智力五环在游戏开始时，先将环道上的色子或数子进行混杂，经过转换调整，使其达到颜色归位。圆形棋子按照颜色分为五色。每个轨道上的圆形棋子都可按顺时针或逆时针方向转动换位，在这一过程中有一个色子会覆盖后一个色子(前一个色子)的位置及颜色。通过旋转转盘使不同的环上的棋子移入另一环轨道上，如此反复，会在六个轨道上产生无穷的变换。如何把一个乱序的五环以最少的变换次数变为排列有序的五环，或把一种排列有序的五环以最少的变换次数变为另一种排列有序的五环，这是一个极富趣味性和挑战性的数学问题，所谓牵一发而动全身。这其中包含了深刻的数学变换思想——拓扑学。 5 2.4. 游戏流程图 6 2.5. 游戏界面设计 一个好的游戏界面能给人以舒服的感觉，引起玩家的兴趣，所以一个好的游戏界面是很重要的。 2.6. 智力五环游戏界面 智力五环游戏软件是一款基于模拟图形转动的拼图软件。游戏开始后的初始化界面如图所示。 7 图2-3智力五环游戏界面图 五个圆环上分布着红、黄、蓝、绿、黑五种颜色的棋子，五种颜色的棋子都是7个。游戏者不仅可以通过点击每个圆环上的顺时针和逆时针按钮，让棋子围绕圆环的轨道进行转动，这样只能在原小圆环内转动，不能实现圆环之间棋子的相互交换，要是小环内的棋子转动到其他圆环中，必须通过转动中间的按钮。通过中间盘的转动使中间的五组(10个)棋子(共同体)在不同的圆环上进行转动。游戏的玩法是通过点击按钮在六个轨道上任意转动棋子，最终将五种不同颜色的棋子分别转动到五个圆环上，实现颜色的归位。 2.7. 设计任务 1) 软件功能分析 智力五环游戏属于新型的智力游戏。虽然已有学长做了游戏软件的界面，但不是很美观，功能也不齐全，所以首先设计出游戏的电子版，设计出功能相对比较齐全的软件。为了吸引玩家，在设计的过程中，必须注重游戏界面的设计，设计出友好的界面，也是游戏软件成功的一部分。为了满足更多的玩家的需要，可以对游戏进行等级设置，这样可以体现游戏更大的实用性。工具栏内应包括最基 8 本的“开始-等级设置”、“游戏重置”、“游戏复位”、“游戏演示”、”游戏提示“、“说明”等功能。游戏界面上要有明显的旋转按钮，使玩家便于通过鼠标点击来玩游戏。为了玩家更清楚游戏过程目标，还应该设计游戏的自动演示，使得玩家能轻松的进行游戏。 2) 游戏界面要素分析以及属性设置 1. 构造框架 软件首先通过资源视图类(Resource View)构建菜单项，创建位图资源。菜单项包括:等级(低级、中级、高级)、重新开始、重新散乱、算法演示、退出、提示、前近、撤销功能。位图资源包括顺时针转动按钮和逆时针转动按钮 2. 加载Button按钮和位图资源 软件的游戏画面是在对话框中显示的，把按钮和位图整合到一起，来控制整个圆环的转动，这样游戏界面看起来比较美观、新颖。通过类视图(Class View)中的OnInitialUpdate()完成如下内容: a. 构建和加载按钮 游戏是通过监听按钮事件来响应玩家的，所以必须在添加按钮。游戏中共用到六个圆，每个圆分别有一个顺时针和一个逆时针转动按钮。构建按钮通过以下的语句完成: /*把位图装入应用程序中进行绘制*/ for (i = 0; i < 6; i++) { bitmap[i][0].LoadBitmap(IDB_BITMAP1);//载入位图 button[i][0].Create(NULL,WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON|BS_BITMAP,CRect( postion.button[i][0].x,postion.button[i][0].y, postion.button[i][0].x + 40, postion.button[i][0].y + 20), this, IDC_BUTTON1 + 2*i);//创建按钮 button[i][0].SetBitmap(bitmap[i][0]);//将位图和按钮加载在一起 bitmap[i][1].LoadBitmap(IDB_BITMAP2);//载入位图 button[i][1].Create(NULL,WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON|BS_BITMAP,CRect( postion.button[i][1].x,postion.button[i][1].y, postion.button[i][1].x + 40, postion.button[i][1].y + 20), this, IDC_BUTTON1 + 2*i + 1);//创建按钮 button[i][1].SetBitmap(bitmap[i][1]);//将位图和按钮加载在一起 } b. 从文件中向工程中导入位图资源，代码如下: CString str; char *name[] = {".\\棋子\\black_", ".\\棋子\\blue_", ".\\棋子\\green_", ".\\棋子\\orange_", ".\\棋子\\red_"}; /*从.bmp文件中装入位图，用LoadImage()函数把磁盘上的.bmp文件装入一个位图中*/ for(int i = 0; i < 5; i++) { for (int j = 0; j < 7; j++) { str.Format("%s%d.ico",name[i], j + 1); 9 crl_icon[i][j] = HICON(LoadImage(NULL, str, IMAGE_ICON, 0, 0, LR_LOADFROMFILE));//装载位图 } } 在OnDraw()函数中加载背景颜色 CRect rect; this->GetWindowRect(&rect); CBitmap bitmap; bitmap.LoadBitmap(IDB_GROUND);//加载背景位图 CBrush brush, *old; brush.CreatePatternBrush(&bitmap); old = pDC->SelectObject(&brush); pDC->Rectangle(0, 0, rect.Width(), rect.Height()); //整个游戏六个圆环背景色初始化函数其实现见:附录1 addCircleBackGround(pDC); 3. 绘制对话框中上的棋子 我们通过改写paint(int nCycle, int nPos, int chess) 和repaint(int n)方法来绘制对话框上的棋子，即游戏界面显示。paint(int nCycle, int nPos, int chess) 和repaint(int n)方法完成了棋子的绘制和中间虚拟圆盘的显示。这是游戏显示的关键部分，具体内容见:附录2 4. 响应按钮点击事件 软件通过响应按钮点击事件来实现玩家和游戏软件的互动。当一个按钮被点击时，程序会自动响应该事件，对棋子位置上的颜色属性进行顺时针或逆时针循环，从而实现了棋子的循环移动。这些事件的响应牵扯到从queue中获取HICON对象、 通过ChangeQueue(int number, int type)函数实现圆环上棋子的转动，通过paint(int nCycle, int nPos, int chess)函数使棋子显示在界面中。在这里详细介绍事件响应的实现过程。需要注意的是这里的事件响应方法Rotate(int ID, int t)是针对对话框上的事件;响应按钮点击事件见:附录3 为了能记录玩者在游戏过程中所做的移动步骤，我们用int step[]=new int[1024]来记录玩家每次移动棋子时所点击的按钮。 5. 构造棋子和圆环的方法 圆环就是由棋子围绕而成的，所以我们只要能确定圆环上各个棋子的坐标位置就可以画出圆环。在软件设计中通过Position.h文件和Position.cpp文件来确定棋子的坐标位置。坐标位置确定后，调用repaint(int n)和paint(int nCycle, int nPos, int chess)函数来绘制棋子。 6. 构造按钮的方法 用按钮构造方法来给五个圆环及中间的虚拟圆环分别添加一个顺时针按钮和逆时针按钮，用来点击触发棋子的旋转事件。 7. 控制事件响应 软件最关键的部分是实时的事件响应。本软件设计过程中添加了以下两类的时间响应: a. 对按钮点击事件的响应 点击任何一个旋转按钮后，都必须对该点击事件进行实时的响应。先对各个棋子的属性进行新的设置，再对整个图形进行刷新。 10 b. 对菜单点击事件的响应 菜单上的事件响应有:游戏等级、游戏重新开始、游戏重新散乱、自动演示、退出、前进、撤退、提示和游戏说明事件。其中前八个事件都是对图形的实时操作，后一个事件是基于对话框的信息提示。 在菜单响应项中游戏等级的设置，通过随机数来设置，其具体实现见:附录4 2.8. 游戏的自动演示 一个好的游戏应该有自动演示的功能，这样可以启发玩者并增强游戏的趣味性。该软件通过变量top 和OpHistory记录了程序随机执行的步骤和玩家历史操作的步骤，变量BackSteps来记录回退的步数。然后根据函数OnForward() 和OnBack()近行逆操作，这样就可以将游戏图形恢复到初始状态。即:若先前对一个大圆环执行了逆时针按钮操作，则现在对该圆环执行顺时针按钮操作;若先前对一个大圆环执行了顺时针按钮操作，则现在对该圆环执行逆时针按钮操作。这样由后往前依次执行逆操作就可以恢复到初始状态。具体的代码介绍见附录5 2.9. 游戏的提示功能 一个完整的游戏必须要有使玩家可信的提示功能，这样在玩家无法进行操作的时候就可以通过提示功能来继续进行游戏的把玩，这样不仅能能使玩家继续把玩，而且能提高用户玩耍把玩的信心。具体实现见:附录6 3. 数据结构 在这个算法研究中，主要用到了循环队列和结构体两个重要的数据结构。下面做详细的介绍: 11 3.1. 循环队列赋值 每个圆环上的棋子，我们以水平顺时针方向起从0到6进行编号，其中小圆和大圆相交的位置分别为0号和6号。在相应按钮时，我们要对每个圆环上棋子位置上的颜色属性进行顺时针或逆时针的赋值。这就要求一种循环队列赋值的算法。下面对其赋值进行项的说明，具体实现见:附录3 number 表示哪个圆环转动(number=0，为大圆;number=1，2，3，4，5，为小圆)，1pe 表示转动的方向(type=0，顺时针;type=1，逆时针)。当顺时针转动大圆时，首先把第四个小圆队列上的首、末棋子的信息存到temp1，temp2中，然后顺时针把前面小圆队列上的首、末棋子的信息依次挪动到其后一个小圆队列的首、末位置上，把第四个小圆队列上的首、末棋子的信息挪动到第一个小圆队列的首、末位置上。当逆时针转动大圆时，把后一个小圆队列上的首、末棋子的信息循环挪动到其前一个小圆队列的首、末位置上。 当转动小圆时，如果为顺时针转动，则将队首位置后移一个，若果为逆时针转动则将队首位置前移一个 3.2. 结构体和类的使用和介绍 在通过绘制棋子来显示圆环时用到了该段代码。它的主要功能是在确定半径的条件下能精确的求出圆环上各个点的X坐标和Y坐标。相比其他的几何画圆法，该算法简单实用。下面详细介绍: 我们将圆环划分了7个棋子，这样，各个棋子之间的角度是360/7度。用 变量n来记录从0到360变化的角度，通过CPosition(int R,int x, int y)函数来确定棋子在对话框中的坐标位置。 typedef struct{//表示棋子位置坐标的结构体 int x; int y; double r; }DATA; class CPosition // 表示棋子位置的类 { public: CPosition(int R = 320, int x = 160, int y = -30);//构造函数 virtual ~CPosition(); int m_X; int m_Y; DATA center;//对应中心圆的位置 DATA main[5];// 对应5个小圆的位置 DATA main_small[5][7];// 对应5个小圆的7个棋子的位置 CPoint button[6][2];//6对旋转按钮的位置 }; double Sin(int n) 12 {return sin(n*3.1415926/180.0);} double Cos(int n) {return cos(n*3.1415926/180.0);} CPosition::CPosition(int R,int x, int y)//确定大小圆的坐标 { m_X = x; m_Y = y; center.x = m_X + R; center.y = m_Y + R; center.r = R*0.5; for(int i = 0; i < 5; i++) { main[i].x = int(center.x + (3 * R * Cos(72*i - 17))/5.0); main[i].y = int(center.y + (3 * R * Sin(72*i - 17))/5.0); main[i].r = R/4.0; button[i + 1][0].x = int(main[i].x + main[i].r/6.0); button[i + 1][0].y = int(main[i].y - main[i].r/8.0); button[i + 1][1].x = button[i + 1][0].x; button[i + 1][1].y = int(main[i].y + center.r/3.0); } button[0][0].x = button[5][0].x; button[0][0].y = int(center.y - center.r/5.0); button[0][1].x = button[0][0].x; button[0][1].y = int(center.y + center.r/2.5); for(i = 0; i < 5; i++) { for(int j = 0; j < 7; j++) { main_small[i][j].r = main[i].r/2.6; main_small[i][j].x = (int)(main[i].x + main[i].r*Cos(72*i - 17 + 51.42857 * j)); main_small[i][j].y = (int)(main[i].y + main[i].r*Sin(72*i - 17 + 51.42857 * j)); } } } 4. 算法命题分析 根据游戏的玩法规则，为了描述的方便，我们对五个环进行编号，中心圆环 为0号圆环，从黑色圆环顺时针一次为1，2，3，4，5号圆环。为了能发现规律， 我们采取从易到难、循序渐进的解决方法，先把问题分解成以下几个命题，进一 步总结出游戏的规律性玩法，以适应任何散乱情况。 13 4.1. 分命题分析 1. 把一任意棋子移动到目标环上，这个是最简单的命题，也是最基本的命题， 解决步骤如下: 转动当前环，把棋子移动到公共区域，然后转动公共盘，使当前环的公共区和目标环的公共区交换，然后转动目标环就可以实现。 2. 当一个圆环上只剩一个没完成，且其他的圆环都还没完成 比如，1号现在是红色的，且剩余一个棋子，在其他的环上，假如在3号环上，解决方案如下: 先转动3号环的按钮，把3号环上的红色棋子转动到公共盘内，具体办法在程序中可以通过搜索三号环中棋子的颜色属性，确定红色棋子的位置，然后确定最少的转动步骤，现在红色棋子已经在公共盘内了，现在转动1号盘的按钮使其以最少的步骤实现两个相同的颜色的棋子在公共盘内。然后转动公共圆盘，使3号圆盘上的公共区与1号的公共区棋子交换，现在转动1号圆环使红色棋子脱离公共区，现在转动公共区使另2个棋子归到1号环上，具体的方法是记住公共圆盘的转动次数。 3. 有一个圆环已经完成，且有一个圆环上只剩一个没完成，比如1号已经完 成，2号剩余一个棋子在别的环上，解决方案如下: 搜索2号剩余棋子的圆环，找到该圆环后，转动当前圆环使需要的棋子移动到公共盘内，转动2号圆环，使2个相同颜色的棋子移动到公共盘内，现在移动公共盘，使当前环和目标环的公共区交换，再转动2号盘使目标棋子脱离公共区，再转动公共盘完成2号环。 4. 当一个圆环上剩余两个，且分布在其他不同的环上，比如1号环上剩余两 个棋子在另外两个环上，且1号环上两个不同颜色棋子的颜色不同。解决 步骤如下: 寻找目标棋子所在的两个环，标记为目标环1和目标环2，移动目标环1上的目标棋子到公共盘内，然后移动公共盘使目标环1和目标环2的公共区交换，然后移动目标环2，使目标棋子脱离公共区，现在2个目标棋子在一个环上了，下面的步骤就与情况(1)类似了。 5. 有两个圆环已经完成，剩余的其中一个圆环上有两个棋子在另外的一个圆 环上，该情况与情况(1)的解决方案类似。 6. 有三个圆环已经完成，剩余的两个环上分别有对方的一个棋子 解决方案同2类似，通过这些问题的解决，我发现了一个小规律，先搜索目标盘需要的棋子所在环(称作当前环)，找到后，移动当前环使目标棋子进入公共区，再移动目标圆盘使其在公共区的是相同颜色的目标棋子，然后移动公共盘 14 (以最少步骤)使当前盘和目标盘的公共区交换，然后再移动目标圆盘使目标棋子脱离公共区，然后移动公共圆盘完成目标圆环。 7. 有两个圆环已经完成，剩余的其中一个圆环上的棋子两个棋子在另外的两 个圆环上，该情况与情况(3)的解决方案类似。 8. 一个圆环上剩余2个棋子没完成，2个棋子在别的同一个换上，该情况解 决方案与情况(1)类似。 通过对上面分命题的反复验证和对游戏实体的反复把玩，这种玩法在时间和空间的复杂度都比较大，而且没有统一的基准，玩起来思路比较混乱，不过对游戏的玩法提供了基本的思路。 4.2. 算法命题规律总结 通过对以上命题的反复研究和对游戏玩法时间和空间复杂度的考虑，进一步对游戏玩法进行优化，已总结出该游戏玩法的基本规律。这种玩法思路比较清晰，而其适应任何情况下的混乱状态，其规律如下: 1) 将五环凑成除大盘上旗子以外，其他旗子都与小环底色相同 2) 将大环上旗子凑成两两颜色相同的状态 3) 完成最终颜色归位 5. 算法设计 5.1. 棋盘局势状态表示和走法产生 棋盘的状态分为归位态和混杂态(低级、中级、高级)。其中归位态表示游 15 戏的五色棋子全部都在与底盘颜色相同的位置，也表示游戏最终状态。混杂状态则是需要玩家进行把玩的状态，玩家通过自己的思考和判断在有限的步骤内完成游戏颜色的归位，最终实现的目标就是达到归为状态。 走法产生是设计棋子如何转动，如何使棋子归位到与小圆环底色颜色相同的位置，其转动通过 CGameView::ChangeQueue(int number, int type)函数来实现的，具体实现:见附录3 如果是小圆环上的棋子顺时针转动，则队首位置后移一个，否则队首位置前移一个。若果是大圆环上的棋子顺时针转动，则先把第四个(黑色圆环)小圆队列上的首、末棋子的信息存到temp1，temp2(其中temp1和temp2是两个临时变量)中，然后顺时针把前面小圆队列上的首、末棋子的信息依次挪动其后一个小圆队列的首、末位置上，否则则先把第四个(黑色圆环)小圆队列上的首、末棋子的信息存到temp1，temp2中，然后把后一个小圆队列上的首、末棋子的信息循环挪动到其前一个小圆队列的首、末位置上，最后通过 CGameView::repaint(int n)函数重画棋子，使其在对话框中表示出来。其中函数 CGameView::repaint(int n)的具体实现见:附录2 5.2. 棋盘中棋子转动的实现 棋子的转动主要通过循环队列来实现，通过循环队列队首、队尾的不断移动来实现不同颜色的棋子在不同的轨道上转动。 5.3. 棋子的走法产生 首先检查0号圆环上0号位置的棋子是否与0号圆环的颜色相同，如果相同则顺时针转动0号圆环，否则跳过0号圆环检查1号圆环，如果0号位置的颜色和圆环底色颜色相同，则继续顺时针转动圆环，以此类推。当检查完所有的圆环时，在判断每个圆环是否有五个颜色相同棋子连续在一起，如果是则第一步完成，否则转动圆盘，再从0号圆环开始检查，直到五个圆环都有连续与圆环底色相同的棋子在一起。 其次在第一步的基础上，再对圆盘上的棋子颜色进行配对，使圆盘中每两个与小圆环相交的位置棋子颜色相同。首先需要找到一个辅助环，该辅助环选择的是有连续六个颜色相同的棋子所在的环i，把颜色不相同的那个棋子转动到i环的0号位置，然后找到与辅助环上0号位置颜色相同的棋子n所在的j环上的位置，通过判断n棋子是在0号位还是6号位来确定i环转动的方向和转动的次数，依次知道所有大环与小环相交的位置棋子全部两两配对 最后实现整个棋盘的归位，从0号圆环(黑色)出发，检查0号圆环是否已经归位，如果已经归位则跳出，检查1号圆环。如果没有归位则搜索与0号圆环底色相同的棋子的位置，首先顺时针转动0号圆环两圈，再通过大圆盘将与圆环 16 底色相同位置的棋子转动到0号圆环的位置，依次类推直到所有的棋子全部归位 5.3.1. 棋子的搜索 搜索算法中主要应用了深度优先搜索，深度优先搜索类似于树的先根遍历，是树的先根遍历的推广。假设初始状态0、1、2、3、4五个圆环上所有的棋子都未曾被访问，则深度优先算法可0号圆环(黑色圆环)0号位置的棋子为出发点，判断0号位置的棋子是否与圆环底色的颜色相同，相同则顺时针转动该小圆环，直到0号位置的棋子与底色不同，则跳出该环，然后依次对1、2、3、4号圆环的0位置棋子进行判断，当所有的圆环都被访问时，判断每个圆环上的棋子是否有连续5个与底环颜色相同的棋子在一起，如果有其中一个没有达到，则转动圆盘继续进行深度优先遍历，直到五个环的都达到至少有五个棋子连续在一起 5.3.2. 搜索算法的优化 17 6. 算法演示的实现 6.1. 第一步: 将五环凑成除大盘上旗子以外，其他旗子都与小环底色相同，实现方法: 整个棋盘位置的编排，按顺时针对5个小圆编号(0..4)，其中底色黑环 为编号为0的小环，每个小环上的7个位置也按顺时针编号(0..6)，其中小圆和大圆相交的两个位置对应0和6。则算法如下: 1. 从黑色0号环开始按0,4顺序检测五个小环，如果小环的0位置旗子 与底盘颜色相同，则顺时针旋转小环，重新检测直到0位置旗子与底 盘颜色不同为止，为避免某一小环上所有旗子都与底盘颜色相同，所 以最多做六次检测。 2. 检测是否存在除大环上旗子外(1,5位置)五小环上旗子都与底盘颜 色相同的情况，若不存在则重复，若存在则第一步结束， 进入第二步。 6.2. 第二步: 将大环上旗子凑成两两颜色相同的状态，实现方法: 为了完成交换，需要找到一个辅助环，所谓辅助还就是小环上有六个颜色同小环底色相同的旗子。 1. 从黑色0号环开始按0,4顺序检测五个小环，找到辅助环i，调整辅 助环i，使不同颜色的旗子在0位置，然后找到辅助环颜色旗子m所 在小环j。 2. 求出大环由j环转到i环的最短步数和方向。 3. 若旗子m在j环上的位置为0位置，则逆时针转动辅助环i两圈，若 旗子m在j环上的位置为6位置，则顺时针转动辅助环一圈 4. 按最短步数转动大环，将j环大环上旗子转到i环 5. 在步骤3，若i环逆时针转两圈，则此时i环顺指针转一圈，在3步 骤，若i环顺时针转一圈，则此时i环逆时针转一圈 6. 将步骤4逆转，按反方向转动大环相同步数。即按最短步数转动大环， 将i环大环上旗子转到j环 7. 测试若五个大环上相同位置旗子都两两配对，则结束，否则回到步骤 1. 6.3. 第三步: 完成最终颜色归位，设定小环上七个旗子的颜色都和底色相同，则称其为归位环。 1. 找到大环的最佳位置，使当大环在那一位置时，归位环的数目最多。 18 2. 求出大环转动到最佳位置的步数和方向，按最短步数转动大环，将其调 整到最佳位置。 3. 从黑色0号环开始按0,4顺序检测五个小环，找到非归位环i 4. 找到i环颜色旗子所在环j 5. 求出大环由j环转到i环的最短步数和方向。 6. 顺时针旋转i环两圈 7. 按最短步数转动大环，将j环大环上旗子转到i环 8. 逆时针旋转i环两圈 9. 将步骤7逆转，按反方向转动大环相同步数。即按最短步数转动大环， 将j环大环上旗子转到i环 10.当完成0,4环检测，则五环归位。 19 7. 算法分析 7.1. 算法异同比较 自动演示算法和设计出的游戏算法在时间复杂度和空间复杂度上的异同比较(只是对规律性算法进行比较): 在研究过程中写出的棋子的混杂程度算法和自动演示算法有本质的区别。首先，不管乱序是如何实现的，这对算法演示本身不起任何影响;再者，演示算法在时间复杂度上取决于乱序时棋子混杂程度，棋子混杂程度越高，在搜索的时候花的时间越多，转动的步数越多，所以时间复杂度就高。从空间复杂度上来说，算法每搜索一步就会把搜索到的目标元素在对话框中重画一遍，并把循环队列中队首的元素前移一个或后移一个，或者把每个小圆环中首末位置的棋子位置进行交换。这样循环队列中的元素进数组到出数组只需要一个很小的空间。时间复杂度和空间复杂度都看初始化过程中乱序时的随机过程，复杂度有大有小，不能够确定。 7.2. 问题讨论 本游戏在算法实现方面掌握了基本的规律，但在算法的实现上仍然未证明其是否是最忧最短路径。另外在算法实现上只选择了每个小圆环的0号位作为基准进行颜色的判断，这样每次实现转动时的步骤难以保证最短，应该在算法演示第一步时通过步数的判断来决定是顺时针还是逆时针转动，但由于实现起来的复杂性和时间的有限性，所以还没有做进一步的考虑 另外在玩法提示中，由于没有发现比算法演示中更优的方法，所以只是针对算法演示的规律进行提示，具有局限性。 20 8. 结束语 8.1. 总结 软件设计过程中，基本的智力游戏功能已经实现，唯一有一点没做到，就是没有将算法完整的研究出来，只能让计算机做出其中的一部分。还有作为玩家只能从头开始一直玩到结束，中间不能够返回到自己的想返回的任何一步，也就是说，玩家只能自己记住自己游戏的步骤，一步一步的往前返回。还有在打乱小圆布局时算法不够好，使得设置难度后的棋子分布看起来还是不够分散;再者，算法不够高效，在设置游戏时会明显感觉到时间的延迟，功能测试我觉得还是比较满意的。 8.2. 展望 在研究的过程中列出了许多的特例，想用特殊方法来对待，现在已经基本解决了一些特例，但是整体的算法没能提炼出来。希望有人要是对这人算法有兴趣的话能够继续研究下去。研究的继续方向是如何解决共同体的问题和算法的提炼，如何提高算法的效率。 21 致 谢 本论文的完成是在武苏里老师的精心指导下得以完成的，从论文的选题、研究到成稿都得到了武老师的悉心帮助，尤其在论文资料的收集和论文的成稿，武老师给了很大的帮助;他在百忙之中对我的毕业设计关怀之至，给予我耐心的指导和细心的修改，提出了很多宝贵的意见，很大的鼓励了我完成论文的信心，也在很大程度上提高本论文的质量。在此论文完成之际，谨向武老师表示最衷心的感谢。 此外，在本次毕业设计的过程中，很多同学给我提出了很多好的建议和意见，在此，向他们致以最诚挚的谢意。 最后，深深的感谢在大学四年里辛勤培育我的各位老师，是他们的培养、关心呵护使我大学四年一路走来;同时特别感谢我的父母和亲人一直以来对我的关心、爱护和全力支持! 22 参考文献 [1] Bruce Eckel.Think in Java. [M].机械工业出版社，2003.7. [2] 王晓东(计算机算法设计与分析[M].第一版(北京:电子工业出版社，2001.1(144-149 [3] 严薇敏，吴伟民.数据结构( C语言版)[M].第一版.北京:清华大学出版社， 1996.300-350 [4] 王应明，徐南荣.最小绝对误差和回归的递推辨识算法.控制与决策[J],1991,(05) [5] 李文军，孙秀真.一个修正的1_1模算法.石油大学学报(自然科学版)[J],1997,(02) [6] 刘刚，顾乃杰，任开新，熊焰.高维环网上的一种可扩展的全交换算法[J].电子学报， 2005，(9). [7] 张爱红.倒排文档压缩技巧的改进——文档标识号重置法[J].现代图书情报技术，2004， (8) [8] 黄刘生，郑启龙，陈国良.虫孔路由二维网孔机器上的最优图论算法[J].计算机学 报,2002，(6) [9] 刘璟编著，计算机算法引论-设计与分析技术[M](北京:科学出版社，2003，8 [10] (美)巴斯(Base,B)等.计算机算法-设计与分析基础[M].第三版.北京:高等教育出 版社，2001，7. [11] (美)莱维丁(Levitin,A) 潘彦译.算法设计与分析基础[M].第一版.北京:清华大学出 版社,2004 [12] 张宪超，陈国良.小容量网络上的最大流算法[J].计算机研究与发展,2001.6 [13] 潭浩强(C语言程序设计[M](第二版(北京:清华大学出版社，1999.12. 311-324 [14] 朱站立编著.数据结构 Java语言描述[M].沈阳:2007.3 [15] 周娅，张振宇编著.数据结构(12)[M].重庆:重庆大学出版社.2007 [16] Visual C++ 6.0入门与提高使用教材 中国铁道出版社 [17] 刘鑫 杨健康等译，C++高级编程 机械工业出版社 [18] Berlinski,D.The Advent of the Algorithm.Harcourt,Inc.New York,2000. [29] T.H.Cormen,C.E.Leisersen R.L.Rivest and c.setin.Introductin to Algorithms, The MIP press,second edition, New York,McGraw-Hill,2001. [20] Sedgewick,R.Algorithms in C, 3rd ed.Part5:Algorithms,Boston,2002. [21] Shen, A.Algorithms and Programming: Problems and Solutions.Boston,1997. 23 附录1: void CGameView::addCircleBackGround(CDC *pDC) { COLORREF rgb[5]; COLORREF rgbMaxCircle=RGB(5,255,255); COLORREF rgbMidMaxCircle=RGB(255,255,255); rgb[0] = RGB(0, 0, 0); rgb[1] = RGB(30,150,220); rgb[2] = RGB(127, 255, 0); rgb[3] = RGB(210, 105, 30); rgb[4] = RGB(160, 0, 0); int x, y, z, l; CBrush maxBrush; CBrush midBrush; //CPen maxPen; int maxR =(int) postion.center.r*7/8; int mov = 35; /////maxPen.CreatePen(PS_SOLID,5,rgbMaxCircle); maxBrush.CreateSolidBrush(rgbMaxCircle); midBrush.CreateSolidBrush(rgbMidMaxCircle); x = postion.center.x - maxR; y = postion.center.y - maxR; z = postion.center.x + maxR; l = postion.center.y + maxR; pDC->SelectObject(&maxBrush); pDC->Ellipse(x + mov-180, y + mov-180, z + mov+170, l + mov+170);//画外圆盘 // pDC->UpdateColors(); pDC->SelectObject(&midBrush); pDC->Ellipse(x + mov-10, y + mov-10, z + mov+10, l + mov+10);//画圆盘 //五个小圆环背景颜色绘制 for(int i = 0; i < 5; i++) { CBrush brush; //CPen pen; //pen.CreatePen(PS_SOLID,1,rgb[i]); brush.CreateSolidBrush(rgb[i]); pDC->SelectObject(&brush); x =(int) postion.main[i].x - postion.main[i].r*5/9; y =(int)postion.main[i].y - postion.main[i].r*5/9; 24 z =(int) postion.main[i].x + postion.main[i].r*14/9; l =(int) postion.main[i].y + postion.main[i].r*14/9; pDC->Ellipse(x-36, y-36, z+16, l+16);//画圆环 } } 附录2 void CGameView::repaint(int n)//n=0，1，2，3，4，5 { int f,r,index; if(n == 0)//重绘大圆上的棋子 { //绘制5个小圆棋盘上的首、末位置的棋子 for(int i = 0; i < 5; i++) { f=front[i]; r=(f+6)%7; //绘第i个小圆棋盘的首位置上的棋子，index为该位置上的棋子所对应的 crl_icon的编号 index=queue[i][f]; paint(i,0,index); //绘第i个小圆棋盘的末位置上的棋子，index为该位置上的棋 子所对应的crl_icon的编号 index=queue[i][r]; paint(i,6,index);//绘第i个小圆棋盘的末位置上的棋子 } } else//绘制某个小圆盘 { n = n - 1; int f=front[n]; //绘制第n个小圆盘上的7个棋子，从队首依次绘制 for(int j = 0; j < 7; j++) { index=queue[n][(f+j)%7] ; paint(n,j,index);//index 为该位置上的棋子所对应的crl_icon的编号 } } } //功能:绘制某个(nCycle,)小圆上的某个位置(nPos)上的棋子， //其中棋子对应的crl_icon的编号为chess void CGameView::paint(int nCycle, int nPos, int chess) 25 { CClientDC dc(this); //将一维棋子图标坐标chess转化为二维坐标[x][y] ,以便于获取棋子图标 int x=chess/7; int y=chess%7; int m=(nPos+4)%7; int length = int(2 * postion.main_small[nCycle][m].r); ::DrawIconEx(dc.m_hDC, postion.main_small[nCycle][m].x, postion.main_small[nCycle][m].y, crl_icon[x][y], length, length, 0, NULL, DI_NORMAL); } typedef struct{//表示棋子位置坐标的结构体 int x; int y; double r; }DATA; class CPosition // 表示棋子位置的类 { public: CPosition(int R = 320, int x = 160, int y = -30);//构造函数 virtual ~CPosition(); int m_X; int m_Y; DATA center;//对应中心圆的位置 DATA main[5];// 对应5个小圆的位置 DATA main_small[5][7];// 对应5个小圆的7个棋子的位置 CPoint button[6][2];//6对旋转按钮的位置 }; double Sin(int n) { return sin(n*3.1415926/180.0); }double Cos(int n) { return cos(n*3.1415926/180.0); } CPosition::CPosition(int R,int x, int y) { m_X = x; m_Y = y; center.x = m_X + R; center.y = m_Y + R; center.r = R*0.5; 26 for(int i = 0; i < 5; i++) { main[i].x = int(center.x + (3 * R * Cos(72*i - 17))/5.0); main[i].y = int(center.y + (3 * R * Sin(72*i - 17))/5.0); main[i].r = R/4.0; button[i + 1][0].x = int(main[i].x + main[i].r/6.0); button[i + 1][0].y = int(main[i].y - main[i].r/8.0); button[i + 1][1].x = button[i + 1][0].x; button[i + 1][1].y = int(main[i].y + center.r/3.0); } button[0][0].x = button[5][0].x; button[0][0].y = int(center.y - center.r/5.0); button[0][1].x = button[0][0].x; button[0][1].y = int(center.y + center.r/2.5); for(i = 0; i < 5; i++) { for(int j = 0; j < 7; j++) { main_small[i][j].r = main[i].r/2.6; main_small[i][j].x = (int)(main[i].x + main[i].r*Cos(72*i - 17 + 51.42857 * j)); main_small[i][j].y = (int)(main[i].y + main[i].r*Sin(72*i - 17 + 51.42857 * j)); } } } 附录3 void CGameView::Rotate(int ID, int t) { //ID 标识旋转按钮ID,旋转按钮ID的分配:1000-1011，每个圆上的两个按钮的ID是紧 连的两个数，t代表动作的类型:是该按钮的正向操作(t=0)还是反向操作(t=1) int n,type; n=(ID-1000)/2;// 获取按钮所属的个圆队列编号n type=(ID+t)%2;// 获取按钮所对应的旋转方向类型type //对棋盘队列进行相应的操作，n代表是哪个圆队列，type代表旋转类型 //是顺向旋转(type=0)还是逆向旋转(type=1)。 ChangeQueue(n,type); repaint(n); //显示时只需要重绘改动的圆，这样可以提高显示效率 } void CGameView::ChangeQueue(int number, int type) { int f1,f2,r1,r2,temp1,temp2; //number 表示转动的是哪个圆(number=0，为大圆;number=1，2，3，4，5，为小圆) //type 表示转动的方向(type=0，顺时针;type=1，逆时针) 27 if(number==0) //大圆 { if(type==0) //顺时针旋转 { //先把第四个小圆队列上的首、末棋子的信息存到temp1，temp2中 f1=front[4]; r1=(f1+6)%7; temp1=queue[4][r1]; temp2=queue[4][f1]; //然后顺时针把前面小圆队列上的首、 //末棋子的信息依次挪动其后一个小圆队列的首、末位置上 for(int i=4;i>0;i--) { f2=front[i-1]; r2=(f2+6)%7; queue[i][r1]=queue[i-1][r2]; queue[i][f1]=queue[i-1][f2]; f1=f2; r1=r2; //把第四个小圆队列上的首、末棋子的信息挪动到第一个小圆队列的首、末位置上 } queue[i][r1]=temp1; queue[i][f1]=temp2; } else //逆时针旋转 { //把后一个小圆队列上的首、末棋子的信息循环挪动到其前一个小圆队列的首、末位置上 f1=front[0]; r1=(f1+6)%7; temp1=queue[0][f1]; temp2=queue[0][r1]; for(int i=0;i<4;i++) { f2=front[i+1]; r2=(f2+6)%7; queue[i][f1]=queue[i+1][f2]; queue[i][r1]=queue[i+1][r2]; f1=f2; r1=r2; } 28 queue[i][f1]=temp1; queue[i][r1]=temp2; } } else { f1=front[number-1]; if(type==0) { front[number-1]=(f1+6)%7;//队首位置后移1个 } else { front[number-1]=(f1+1)%7;//队首位置前移1个 } } } 附录4 void CGameView::OnUpdateMid(CCmdUI* pCmdUI) { // TODO: Add your command update UI handler code here if(nPlay == 2) { pCmdUI->SetCheck(1);//1表示选择中等难度 } else pCmdUI->SetCheck(0);//0表示不选择 } void CGameView::gameClass(int N) { for(int i=0;i<5;i++) { int l=i*7; for(int j=0;j<7;j++) {queue[i][j]=l+j; }front[i]=4; } N = N * 20; srand(unsigned(time(NULL)));//产生随机数 int ID; int n,type; for(i = 0; i < N; i++) 29 { ID = rand()%12 + 1000;//产生12个按钮的编号 n=(ID-1000)/2; type=(ID)%2; ChangeQueue(n,type); } for(i=0;i<5;i++) { for(int j=0;j<7;j++) { queue_begin[i][j]=queue[i][j]; } front_begin[i]=front[i]; } top=0; BackSteps=0; } 附录5 void CGameView::OnForward() { // TODO: Add your command handler code here Forward(1); } void CGameView::OnBack() { // TODO: Add your command handler code here Back(1); } void CGameView::Back(int num)//在OnBack()函数中调用 { //通过OpHistory[--top]来获取最近的操作类型，通过该操作的逆操作来回退 int id; while ( num > 0 && top > 0 ) { id=OpHistory[--top];// 通过OpHistory[--top]来获取最近的操作类型，同时 top-1 num--; BackSteps++;//回退步数加1 Rotate(id,1); // 1代表进行反向旋转 } if ( num > 0 && top == 0 ) { AfxMessageBox("已倒退到最开始的位置～"); 30 } } void CGameView::Forward(int num) { int id; while ( num > 0 && BackSteps > 0 ) { id=OpHistory[top++]; num--; BackSteps--; Rotate(id,0); } if ( num > 0 && BackSteps == 0 ) { AfxMessageBox("已前进到原来的位置～"); } } 附录6 31