毕业论文-数独游戏的设计与开发

.引言1.1简介数独游戏是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。数独的玩法逻辑简单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。图1.11.2数独的起源数独前身为“九宫格”，最早起源于中国。数千年前，我们的祖先就发明了洛书，其特点较之现在的数独更为复杂，要求纵向、横向、斜向上的三个数字之和等于15，而非简单的九个数字不能重复。儒家典籍《易经》中的“九宫图”也源于此，故称“洛书九宫图”。而“九宫”之名也因《易经》在中华文化发展史上的重要地位而保存、沿用至今。1783年，瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”（LatinSquare）的游戏，这个游戏是一个n×n的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。19世纪70年代，美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》（DellPuzzleMαgαzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”（NumberPlace），在这个时候，9×9的81格数字游戏才开始成型。1.3数独的发展1984年4月，在日本游戏杂志《字谜通讯Nikoil》（《パズル通信ニコリ》）上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”，并将这个游戏命名为“数独”（sudoku）。

一位前任香港高等法院的新西兰籍法官高乐德（WayneGould）在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的《泰晤士报》上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程式，并将它放在网站上，使这个游戏很快在全世界流行。从此，这个游戏开始风靡全球。后来更因数独的流行衍生了许多类似的数学智力拼图游戏，例如：数和、杀手数独。2.开发工具及环境2.1C++语言简介C++语言是一种优秀的面向对象程序设计语言，它在C语言的基础上发展而来，但它比C语言更容易为人们学习和掌握。C++以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一个质的飞跃，C++完美地体现了面向对象的各种特性。2.2MFC简介MFC,微软基础类(MicrosoftFoundationClasses),实际上是微软提供的,用于在C++环境下编写应用程序的一个框架和引擎。MFC是WinAPI与C++的结合,API,即微软提供的WinDOS下应用程序的编程语言接口,是一种软件编程的规范,但不是一种程序开发语言本身,可以允许用户使用各种各样的第三方的编程语言来进行对WinDOS下应用程序的开发,使这些被开发出来的应用程序能在WinDOS下运行。3.系统需求分析3.1现行系统概况描述同类似的填字游戏不同，数独受欢迎的原因之一是它既不需要丰富的百科知识，也不要掌握大量的词汇，这使其能迅速为孩子和初学者所接受。根据游戏开始时的方格中已有的数字和位置，数独难易程度不同，有些复杂的甚至令数学家也不能完成。现在在各个系统平台上都有数独游戏的开发，且用户十分庞大3.2需求分析“数独”，即“独立的数字”的简称，游戏在一个9*9的方格中，有81个小方格组成，然后又分成9个大块，每块由3*3组成，就是九宫格，大九宫格里边再嵌套9个小的九宫格，游戏开始前会有一些格子上写好了数字，你需要在剩下的格子里面填写数字，直到把所有的鸽子填满，并且要求最后任何一行或者一列或者一个小九宫格中都不存在相同的数字。系统开发可行性分析据著名的动游戏开发商AstrawareLtd.预计，移动数独游戏的版本多达几十种，Palm和WindowsMobile设备版本的数独游戏就各有20种左右。Sudokumo推出的移动数独游戏，能够下载到大多数手机中。这家位于英国的游戏软件公司表示，已经在全球卖出了7500套数独游戏，而且来自用户的兴趣还在增加。因此，一个好的数独游戏的开发，可以吸引很多潜在的玩家。5.系统分析利用C++语言的面向对象特性，把生产游戏数据的程序封装成一个类，在玩游戏时，只要根据数独游戏的逻辑性来编写，先得到一个完整的数独，然后根据难度需要，随机的挖一些空格出来。便可以得到唯一解的数独。终盘数量数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？共有6,670,903,752,021,072,936,960（约有6.67×10的21次方）种组合，2005年由BertramFelgenhauer和FrazerJarvis计算出该数字，并将计算方法发布在他们网站上，如果将等价终盘（如旋转、翻转、行行对换，数字对换等变形）不计算，则有5,472,730,538个组合。数独终盘的组合数量都如此惊人，那么数独题目数量就更加不计其数了，因为每个数独终盘又可以制作出无数道合格的数独题目。

按照这个数量，如果我们将一个[1,2,3,4,5,6,7,8,9]的数组随机化，然后将其作为一行数据添加到一个二维数组中去，该行能满足数独终盘规则的概率是很大的。

基于这个假设(假设的有效性会在文章后面验证)，我的算法思想如下：写一个方法用于获取一个由1到9九个数随机排列的一维数组。将获取到的1到9的随机数的一维数组放入九宫格中，每一个随机数的列坐标循环采用1到9，行坐标使用1到9的随机数，从而使步骤一中产生的随机数随机分布在九宫格中每一列中。循环寻找出当前九宫格中所有空白格中的右下角的一个空格。写一个算法找出某一个单元格中可以填入的数字的数组。在所有空白格中的最右下角的空白格中填入可能存在的数字，以此数据为新的游戏数据，接着循环寻找当前数据中空白格中的最右下角的空白格，填入当前空白格中可能存在的内容。递归寻找，若最后每一个空白格中都有可以填入的数字，则游戏终盘生产成功，否则往回递归，填入可能存在数字数组中的第二个数组，循环递归，若仍然没有终盘生产，则生产游戏失败。根据玩具设置的游戏难度，在生产的终盘游戏中随机挖取一定的空数据，空格越多，则游戏难度越大。游戏生产完毕以后，玩家开始填数字开始游戏，当玩家填写完成，则开始进行游戏是否完成的判断，在判断过程中，只需要判断当前空格中的数字是否与同行，同列和同小九宫格中的数字是否相同即可，若所有的单元格都判断成功，则玩家成功完成游戏。6.系统设计6.1设计思路先得到一个完整的数独，然后根据难度需要，随机地挖取一些空格出来，然后判断是否符合条件（游戏规则），循环再输出。6.2系统主要类设计游戏框架基于MFC的对话框，在一个对话框中显示九宫格和一些功能性按钮，该程序主要包含GamePad类，sudokuDlg类和SudokuGame类。6.2.1GamePad类该类主要对数独游戏的九宫格进行记录和操作。九宫格的状态一共分为5种：enumCellType{ ORIGINAL_CELL=0,//原始数据单元格 EDIT_CELL,//可编辑单元格 ERROR_CELL,//输入错误单元格 CLICK_CELL,//单机单元格 PROMPT_CELL//提示输入单元格};可编辑的单元格在每次点击两次之后会变成可编辑状态，玩家可通过键盘先单元格中输入数字，提示单元格在玩家开启提示功能之后，会在单元格的最下方显示该单元格中可输入的数字。该类中记录了九宫格操作需要的一些数据，具体包括：CSudokuGamem_sudo;//数独游戏数据对象 intm_x;//鼠标点击x坐标 intm_y;//鼠标点击y坐标 intm_row;//选择行 intm_col;//选择列 CRectm_rect[9][9];//保存各个小方格坐标 boolm_bCorrect[9][9];//保存各个小方块的输入状态：输入正确或者输入错误 CStringm_proStr[2];//保存提示字符串 CRectm_proRect[2];//保存显示提示符的坐标 intm_key; //键盘输入 intm_nClick;//记录单机次数：单机两次为输入 BOOLm_bPrompt;//是否显示提示·同时，该类中记录了九宫格操作的一些方法，具体包括：BoolGetRowCol(constCPointpoint);//获取鼠标单机单元格的行号和列号boolGetRowCol(int&row,int&col,constCPointpoint);//外部进程获取鼠标单机单元格的行号和列号boolGetPromptStrRect(constintrow,constintcol); //获取提示符输入voidDrawCell(constintrow,constintcol,constintinvalue,constinttype); //绘制单元格voidInitialize(); //单元格的初始化voidMarkErrorCell(); //标记输入错误的单元格voidShowTheComputeResult(constvector<vector<vector<int>>>&result,constboolbFinish); //显示游戏自动完成的结果在该类中，通过以上的变量和方法，对游戏界面的九宫格的状态进行操作。6.2.2SudokuDlg类该类主要对数独游戏的整个运行逻辑进行控制，是整个对话框的控制类，在整个对话框中除了九宫格之外，还有8个按钮，分别是“载入游戏”，“选择游戏文件”，“退出游戏”，“保存游戏文件”，“完成游戏”，“保存正确结果”，“自动计算数独结果”和“随机生成新游戏数据”，同时，还有一个复选框按钮，玩家可以通过打开此开关显示输入提示。该类通过消息映射机制，分别对每一个按钮做了相应的功能性处理，主要包括以下功能：voidCSudokuDlg::OnBnClickedLoadgame()//加载原始游戏数据文件voidCSudokuDlg::OnBnClickedChoose()//选择游戏数据文件进行游戏voidCSudokuDlg::OnBnClickedNew()//生产新的游戏数据voidCSudokuDlg::OnBnClickedSave()//保存新生产的游戏数据UINTComputing(LPVOIDlpParam)//多线程计算数据结果voidCSudokuDlg::OnBnClickedCompute()//自动计算数据结果6.2.3Sudokugame类该类是数独游戏的规则控制类，主要用于控制游戏数据的生成，计算，判断游戏成功失败等等。主要包括以下的变量和函数：intm_data[9][9];//保存原始游戏数据 intm_user[9][9];//保存用户输入数据 intm_bCompute;//判断用户是否终止自动计算 boolm_bExit;//标志线程是否终止退出 voidInitialize(); //初始化 boolCheckInput(constintrow,constintcol,constintinput);//判断输入的某个数据是否有效 boolCheckCell(constintrow,constintcol);//判断某一个单元格是否有错 boolCheckOriginalData();//检查原始数据的合法性 intGetInputNum(constintrow,constintcol,vector<int>&integer);//获取某个单元格所有可输入的整数 boolCheckTheResult();//判断用户最终是否完成了游戏 boolComputeResult(vector<vector<vector<int>>>&results);//自动计算数独结果 boolCallRecurrence(int*data,intcount,vector<vector<vector<int>>>&results);//递归计算 boolCallRecurrence(int*data,intcount,int*result);//递归计算，用于生产数独数据的中间计算过程 voidCreateSudokuData();//自动随机生产数据游戏数据 voidCopyToUser();//将原始数据拷贝到用户数据生产游戏数据代码：思路分析：首先，确定一个9*9的正方形盘。第一行：取1~9个数字，然后把数字打乱放好到每一行每个格子里面。第二行开始：（因为有了第一行的限制，所以第二行开始就不能乱填了）。这时可以建立一个函数专门用来填数字，从第一列开始到第9列结束。函数的实现过程基本是这样的：首先生产一个1到9的随机数，这时候判断跟同一行前面填了的有没有重复的，重复的重来，还要再判断跟同一列的舔的数据有没有重复的，重复的从来，总有一个会适合的。//递归计算，用于生产数独数据的中间计算过程boolCSudokuGame::CallRecurrence(int*data,intcount,int*result){ inta[9][9]; memcpy(a,data,sizeof(a)); if(count==81) { memcpy(result,a,sizeof(a)); returntrue; } unsignedintnum=10; introw=0,col=0; vector<int>mayInput; for(inti=0;i<9;i++) { for(intj=0;j<9;j++) { if(a[i][j]==0) { vector<int>integer; memcpy(m_user,a,sizeof(m_user)); GetInputNum(i,j,integer); if(integer.empty())returnfalse; if(num>integer.size()) { num=integer.size(); row=i; col=j; mayInput=integer; } } } } for(unsignedinti=0;i<mayInput.size();i++) { a[row][col]=mayInput[i]; if(CallRecurrence((int*)a,count+1,result))returntrue; } returnfalse;}//自动随机生成数独游戏数据voidCSudokuGame::CreateSudokuData(){ intdata[9][9]; memset(data,0,sizeof(data)); srand((unsigned)time(NULL)); intnum=(rand()%17)+25;//随机产生20-41个随机数 intpossible[9],i1,i2,temp; for(inti=0;i<9;i++)possible[i]=i+1; for(inti=0;i<20;i++) { i1=rand()%9; i2=rand()%9; temp=possible[i1]; possible[i1]=possible[i2]; possible[i2]=temp; } boolbNon=true; intcount=9; introw,col; while(bNon) { for(inti=0;i<9;i++) { col=rand()%9; data[i][col]=possible[i]; } if(CallRecurrence((int*)data,count,(int*)data)) { bNon=false; break; } } //随机挖去81-num个的洞 for(inti=0;i<(81-num);i++) { row=rand()%9; col=rand()%9; while(data[row][col]==0) { row=rand()%9; col=rand()%9; } data[row][col]=0; } memcpy(m_data,data,sizeof(data)); memcpy(m_user,data,sizeof(data));}//递归计算数独结果boolCSudokuGame::CallRecurrence(int*data,intcount,vector<vector<vector<int>>>&results){ if(!m_bCompute)returnfalse; if(results.size()>=MAX_NUM)returntrue; if(count==81) { memcpy(m_user,data,sizeof(m_user)); vector<vector<int>>result; result.clear(); result.resize(9); for(inti=0;i<9;i++) { for(intj=0;j<9;j++) { result[i].push_back(m_user[i][j]); } } results.push_back(result); returntrue; } inta[9][9]; memcpy(a,data,sizeof(a)); unsignedintnum=10; introw=0,col=0; vector<int>mayInput; for(inti=0;i<9;i++) { for(intj=0;j<9;j++) { if(a[i][j]==0) { vector<int>integer; memcpy(m_user,a,sizeof(m_user)); GetInputNum(i,j,integer); if(integer.empty())returnfalse; if(num>integer.size()) { num=integer.size(); row=i; col=j; mayInput=integer; } } } } boolbOK=false; for(unsignedinti=0;i<mayInput.size();i++) { a[row][col]=mayInput[i]; if(CallRecurrence((int*)a,count+1,results))bOK=true; } returnbOK;}//自动计算数独游戏的可能解代码：boolCSudokuGame::ComputeResult(vector<vector<vector<int>>>&results){ m_bExit=false; results.clear(); intdata[9][9]; memcpy(data,m_data,sizeof(m_data)); intcount=0; for(inti=0;i<9;i++) { for(intj=0;j<9;j++) { if(m_data[i][j]>0)count++; } } if(CallRecurrence((int*)data,count,results)) { m_bExit=true; returntrue; } else { m_bExit=true; returnfalse; }}//获取某个单元格中可以输入的数据代码intCSudokuGame::GetInputNum(constintrow,constintcol,vector<int>&integer){ if((col>=9)||(row>=9)||(col<0)||(row<0))return0; intnum=0; integer.clear(); intline[9]; memset(line,1,sizeof(line)); inti=0,j=0,temp; for(i=0;i<9;i++) { temp=m_user[i][col]; if((row!=i)&&temp>0)line[temp-1]=0; } for(i=0;i<9;i++) { temp=m_user[row][i]; if((col!=i)&&temp>0)line[temp-1]=0; } intt1=row/3,t2=col/3; for(i=t1*3;i<(t1*3+3);i++) { if(row==i)continue; for(j=t2*3;j<(t2*3+3);j++) { if(col==j)continue; temp=m_user[i][j]; if(temp>0)line[temp-1]=0; } } for(i=0;i<9;i++) { if(line[i]!=0) { integer.push_back(i+1); num++; } } returnnum;}//检查用户是否正确完成数据代码boolCSudokuGame::CheckTheResult(){ inti=0,j=0; for(i=0;i<9;i++) { for(j=0;j<9;j++) { if(m_user[i][j]==0)returnfalse; else { if(!CheckInput(i,j,m_user[i][j]))returnfalse; } } } returntrue;}7.系统主要技术特色游戏采用了MFC框架搭建，有着较好的界面显示，可以给用户更好的游戏体验，相对于传统的游戏设计，游戏中加入了显示输入提示功能，可以帮助水平不高的玩具更容易的完成游戏，使初学者更容易完成数独游戏，体验到数独游戏的乐趣。8.结论毕业设计是对我们四年所学知识最后一次综合性检测盒实际应用能力的考察。我们这次设计的课题是“数独游戏的设计与开发”，该课题使我对所学的知识有了一个比较系统的认识和理解。涉及了软件工程，C++语言，数据库等科目，综合能力有了进一步提高，同时使我学会了如何使用所学的知识去解决一些实际问题，增加了我们的动手能力。