1、 人工智能课程设计报告人工智能课程设计报告 数独游戏数独游戏 一、一、游戏介绍：游戏介绍： 在9 9的格子中，用1到9共9个阿拉伯数字填满整个格子。 要求：1.每一行都用到1到9，位置不限 2.每一列都用到1到9，位置不限 3.每3 3的格子都用到1到9，位置不限 开始时： 填完后： 二、二、程序实现的功能程序实现的功能 1、玩家可以选择游戏的难易程度 2、玩家可以自己填数字 3、电脑直接显示答案 4、玩家如果不想玩可以开始新游戏 三、三、使用说明使用说明 运行 Sudoku.exe 程序，初始选择为简单模式，玩家可以自己选择，然后点击“开始游戏” ， 上面显示玩家用的时间，如果玩家想自己填数
2、字，直接点要填的空格会出现一个编辑框，在 里面输入要填的数字，按回车键。想直接显示结果，点击“显示答案” 。点击“开始游戏” 可以开始新一盘游戏。 四、四、算法设计算法设计 1、算法思想：算法思想： 本算法采用“挖洞”思想。经过以下两步生成数独题：1)运用拉斯维加斯随机算法生成一个 终盘；2)采用以下3个操作“抹去”一部分数字来生成数独题：根据所需要的难度等级选 取一种挖洞顺序；通过深度优先搜索来求解，从而保证“挖去”一个数字后该数独题仍有 唯一解引入剪枝技术来避免无效的“挖洞”尝试。 伪代码： start 生成一个完整的终盘； if(true)生成成功； else 进行循环，直到终盘为 tr
3、ue，即可解； then 按照难易成都，随机去掉几个数，进行检测； if(检测成功)输出 ； else重新“挖洞” ，直到成功； 2 2、问题的分析问题的分析 要能保证算法生成的数独题具有可变化的难度和唯一解， 该算法内部应该包含有对数独题的 求解和评级功能。在此将该算法的设 计工作分为生成、求解2部 分工作（均在类 KSudokuCaculate中） ： （1）先生成一个终盘，存在一个二维数组中。 （2 2）根据游戏者需求的难度等级，我们从已知格的总数和分布来确定“挖去”的个数。 3、生成终盘（算法如下）生成终盘（算法如下） 建立一个新类KSudokuCaculate，在类里面编写下面源代码
4、 bool KSudokuCaculate:MakeSudokuData(SUDOKUMATRIX nGameData) bool bRet = false; /PROCESS_ERROR(NULL != nGameData); / 判断指针 是否为空 bRet = true; / 先随机生成中间g_nSmallSize 方格_nSmallSize方格的个数字 RandomCenter(); / 先后产生其他g_nSmallSize 方格_nSmallSize方格的个数字 CacMiddleUpAndDown(); CacMiddleLeftAndRight(); CacCorner(); /
5、 将生成的矩阵复制输出到参数中 for (int nRow = 0; nRow g_nSize; nRow+) for (int nCol = 0; nCol g_nSize; nCol+) nGameDatanRownCol = nMatrixnRownCol; Exit0: return bRet; /* * int nRow, nCol, nNum; srand(time(0); for (nRow = g_nSmallSize; nRow g_nSmallSize * 2; nRow+) for (nCol = g_nSmallSize; nCol g_nSmallSize * 2;
6、nCol+) nNum = rand() % g_nSize; / 随机生成-9中的一个数字 while (0 != nHasAssignnNum) / 选择一个没有分配的数字 nNum = rand() % g_nSize; nMatrixnRownCol = nNum + 1; nHasAssignnNum = 1; return true; /根据中间的方格数字经过列变换计算出中间上面和下面 方格内的数字 /若成功生成则返回true, 否则返回false bool KSudokuCaculate:CacMiddleUpAndDown(void) int nUp; / 上面方格的x坐标差 int nDown; / 下面方格的x坐标差
