人工智能课程设计报告(数独游戏)

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