(人工智能数独游戏.doc

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