人工智能数独游戏

人工智能课程项目报告1数独游戏20120615，2012061521，王智摘要：数独游戏通常含有一个9*9=81的单元格，每个单元格内有且仅有一个值，这里的值限定为1-9中的一个数字，9*9=81的大单元格又被划分为9个3*3=9的小宫格，值填写的规则是每行、每列与每个小宫格内必须有1-9这九个数字，不得重复或者缺失。本文主要通过穷举法对给定初盘进行数独求解，同时与回溯法、剪枝法数独求解的效率进行比较，研究各种算法的求解效率随难度的变化情况。关键词：人工智能；数独游戏；回溯法本组成员：王智，黄烈朝，刘云鹏本人分工：自动完成数独棋盘方法，数独游戏算法实现，程序代码实现1引言自动生成数独初盘的方法是挖空法，首先生成一个完整的数独棋盘整盘，再按照难度等级挖去数量不等的空位，成为真正显示在棋盘上的初盘。自动解决数独的方法是回溯法，此外还有穷举法和剪枝法，穷举法等方法。穷举法代价比较高，不适合使用，剪枝法是对回溯法的优化，但是在本问题的的前提下，提升并不很大，但是代码实现要困难许多，所以本项目使用的是回溯法。VC6.0是我们都比较熟悉的开发工具，我对它的使用也比较熟悉，界面也比较简单，容易实现，所以我选择使用VC6.0开发本次的项目。2算法原理与系统设计在挖洞法生成数独初盘之前，需要得到一张随机的满足数独条件的终盘，然后对终盘进行挖洞操作，从而生成初盘。在数独游戏中，对于每个数来说，都需要满足三个条件：每行不重复、每列不重复、每个小宫格不重复。回溯法的原理是，在所有空格中选择可填入数字最少的空格，填入数字后检查合法性，如果不合法则回到上一步，直到所有空格被填满，跳出循环。开始设置空位参数n=0n81弹出成功完成对话框结束否读入数独棋盘筛选合适的空位填入数字判断是否符合规则n++是人工智能课程项目报告23系统实现1.自动完成数独模块核心编码当数独棋盘中没有空位时，跳出循环，否则在所有空格中选择可填入数字最少的空格，填入数字后检查合法性，直到完成棋盘。voidCShuduDlg::Try(constintn){if(n==81)//如果n=81，则输出{temp++;if(temp==1){intq,w;for(q=0;q9;q++)for(w=0;w9;w++)shuzu[q][w]=youxi[q][w];}return;}constinti=n/9,j=n%9;if(youxi[i][j]!=0&&temp==0){Try(n+1);return;}intk;for(k=0;k9;k++)//判断是否有重复数字{youxi[i][j]++;if(Isvalid(i,j)&&temp==0)//如果有相同数字，false，没有相同的，则true。Try(n+1);}youxi[i][j]=0;}人工智能课程项目报告32.判断合法性模块通过以下代码判断在游戏区域内填入的数字是否符合规则，即在横竖和小九宫内是否有同样的数字。3.界面的消息的响应函数界面的消息响应函数，使voidCShuduDlg::OnLButtonDown(UINTnFlags,CPointpoint){//TODO:Addyourmessagehandlercodehereand/orcalldefaultinti=(point.x-19)/42;intj=(point.y-30)/42;if(i0)i=0;if(j0)j=0;number[i][j]=now_number;youxi[i][j]=number[i][j];if(now_number!=0)m_grade+=10;if(!Isvalid(i,j)&&now_number){AfxMessageBox(不可以这么放！);number[i][j]=0;youxi[i][j]=0;m_grade-=10;}Invalidate();intsum=0;for(i=0;i9;i++){for(j=0;j9;j++){intCShuduDlg::Isvalid(constinti,constintj){constintn=youxi[i][j];conststaticintquery[]={0,0,0,3,3,3,6,6,6};intt,u;for(t=0;t9;t++)if(t!=i&&youxi[t][j]==n||t!=j&&youxi[i][t]==n)//如果有相同的两个数，返回0return0;for(t=query[i];tquery[i]+3;t++)for(u=query[j];uquery[j]+3;u++)//九宫内有相同数字，返回0if((t!=i||u!=j)&&youxi[t][u]==n)return0;return1;//都没有，返回数字1}人工智能课程项目报告4if(number[i][j]!=0)sum++;}}if(sum==81){CStringstr;str.Format(恭喜你解数独成功！你的分数为%d,欢迎您的参与！,m_grade-m_time);AfxMessageBox(str);}CDialog::OnLButtonDown(nFlags,point);}4实验或测试结果1.初始状态参数截图，此时刚刚运行自动解数独的代码，其中n的值为0。2.程序继续运行当n=8后检测与规则不符回溯到n=6的状态。人工智能课程项目报告53.当n=81后跳出循环，此时数独游戏已经完成。5结论通过本次实验我了解了利用回溯法解决数独问题的方法，并且用VC6.0完成了程序的代码编写，对于解决数独问题的三种方法，穷举法代价太高并不适合使用，而剪枝法对效率的提高并不十分明显，所以回溯法是最合适的解决方法。参考文献[1]雷蕾,沈富可.关于数独问题的算法的设计与实现[J].电脑知识与技术：学术交流,2007,第2期(2):481-482.[2]胥剑.回溯法解数独问题[J].电脑编程技巧与维护,2009,第5期(5):17-21.