数独游戏实验报告篇一：Sudoku 数独实验报告Project2：Sudoku实验报告一、算法描述求解Sudoku让人最容易想到的方法是穷举每个方格可能的值，如果符合条件，则得到解，不符合条件则进行回溯。
通过递归的方法，显然可以得到数独的解。
我想到的简单的递归方法，是每一行从左到右，试验每一个方格可能的数字，进行递归。
这种方法看似非常麻烦，实际上对于一般的数独题，速度是非常快的，思想比较简单，写出来的代码也非常简单、易懂。
算法1：简单递归方法从第一个格开始，从1到9试验，是否满足行、列、九宫格互不相同的条件。
若满足条件，则填入该数字，再试验下一个格。
当一个格子出现没有数字能填的情况时，说明已经填的数字有误，回溯，再进行递归。
算法2：优化的递归算法先遍历所有格子，统计每种格子可能出现数字的个数。
每次挑选可能出现数字个数最少的格子来进行递归。
设置三维数组poss[i][j][k]来存储可能出现数字的信息。
poss[i][j][0]记录i行j列的格子可能出现数字的个数，poss[i][j][k](1 算法3：生成数独棋盘的算法我最开始的想法是穷举法，随机生成满足行各不相同的9行，再判断9宫格、每列是否符合要求，符合条件时，随机生成停止。
然而，这种算法的当然时间复杂度显然是过高。
第99一步的随机生成的次数是9*9/P9=9608。
随机生成一组棋盘耗时就非常大。
后来，我从求解的个数的程序获得启发。
算法二对于1000多组解的数独棋盘，解起来也很快。
随机生成填9个方格，再用算法一的方法解出来，取第一组正确的解作为棋盘即可生成填好的棋盘。
再把一定数量的格子的数字随机删除，计算解的个数。
如果解唯一，就得到了棋盘。
二、数据结构这两种算法的数据结构不是非常复杂，只是普通的数组。
算法一：数组a[i][j]算法二：数组a[i][j]和poss[i][j][k] 算法三：数组a[i][j]和poss[i][j][k] 三、时间效率分析算法1：这种算法在tsinsen系统上只用了15ms得到全部答案。
虽然这种算法在tsinsen系统的测试中有很好的表现，但是我试了试在几道骨灰级难度的题，发现这种算法可能会用到10秒以上的时间，并且测试数据不同，时间差异非常大。
我认为，这种算法的漏洞在于，如果开始的格子可能出现的数字非常多，递归树开始的枝会非常多。
并且，我们一般做数独题，都会先挑可能出现数字个数最少的格子来填，充分利用了已知条件。
然而，这种算法只按格子的行列顺序来试验，显然非常傻。
于是，我想出了第二种算法。
算法2：非常令人失望的是，虽然它能在短时间内解出骨灰级题目，但是，和上一个算法相比，对于简单的题目，它比较耗时。
在tsinsen系统中测试的时间是91ms。
它的缺陷在于，每次递归都必须更新（i，j）格子所在的行、列、九宫格所有的元素。
每次要求20个数的poss[i][j][]。
回溯同样要更新。
并且求poss[i][j][]的函数时间复杂度是O（n）。
每一步所耗时间比上一种算法多很多。
但是，总的试验的步数能显著减少。
所以，这种算法适用于数独解题的动画演示和解极难题目。
四、程序结构算法一：算法二：五、运行结果五、总结和反思后来老师提高了难度，要求程序能求出多解数独题的解的个数。
几千个解的数据都能迅速得出答案，但是几万个解的数据，需要很长时间，更别提几百万的数据。
这两种递归的算法都有问题，优化的空间也有限，需要更强大、高效的算法。
这次Project让我不断思考，改进了最初的算法。
编程是确实是一个克服困难、不断改进与超越的过程。
总有新的数据摆在面前，把原来的算法打击得很惨，激励着我们研究更加先进的算法。
篇二：android课程设计报告(数独游戏)?河南科技学院《物联网移动应用开发》课程设计报告设计题目：基于android的数独游戏设计班级：学号： XX156555 姓名：胡建刚指导教师：信息工程学院课程设计报告说明一、写报告前，请认真阅读《课程设计报告说明》。
二、打印装订要求1、一律用A4纸，双面打印，并左侧装订。
报告正文部分均采用宋体小四。
《课程设计报告说明》页也打印。
2、课程设计概述部分占一页；课程设计内容长度根据实际需要填写；结论和指导教师评语及成绩单独占一页。
保证打印格式工整。
3、指导教师评语及成绩部分由指导教师填写。
三、报告内容要求1、课程设计目的结合实际自己写，不要雷同。
2、课程设计原理简要说明所完成课程设计项目所涉及的理论知识。
3、课程设计内容这是课程设计报告极其重要的内容。
概括整个课程设计过程。
（最好在上述内容基础上画出相应的流图、设计思路和设计方法，再配以相应的文字进行说明。
）篇三：人工智能课程设计报告(数独游戏)人工智能课程设计报告数独游戏学号：姓名：指导老师：日期：一、游戏介绍：在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();// 先后产生其他g_nSmallSize×方格_nSmallSize 方格的个数字CacMiddleUpAndDown(); CacMiddleLeftAndRight();CacCorner();// 将生成的矩阵复制输出到参数中 for (int nRow = 0; nRow {for (int nCol = 0; nCol {nGameData[nRow][nCol] = nMatrix[nRow][nCol];}}Exit0:return bRet;}/*** &brief 用于随机生成中间×方格的个数字* &return 若成功生成则返回true, 否则返回false */bool KSudokuCaculate::RandomCenter(void){// nHasAssign[i]标志数字i+1是否已经被分配int nHasAssign[g_nSize] = {0}; int nRow, nCol, nNum;srand(time(0));for (nRow = g_nSmallSize; nRow for (nCol = g_nSmallSize; nCol {nNum = rand() % g_nSize; // 随机生成-9中的一个数字 while (0 != nHasAssign[nNum]) // 选择一个没有分配的数字 nNum = rand() % g_nSiz(原文来自：小草范文网:数独游戏实验报告)e;nMatrix[nRow][nCol] = nNum + 1;nHasAssign[nNum] = 1;}return true;}//根据中间的方格数字经过列变换计算出中间上面和下面×方格内的数字 //若成功生成则返回true, 否则返回falsebool KSudokuCaculate::CacMiddleUpAndDown(void) {int nUp; // 上面方格的x坐标差int nDown;// 下面方格的x坐标差int nRow, nCol;// 交换中间第一列nCol = g_nSmallSize;nUp = 1;nDown = 2;for (nRow = g_nSmallSize; nRow {// 复制数字nMatrix[nRow - g_nSmallSize][nCol + nUp] =nMatrix[nRow][nCol];nMatrix[nRow + g_nSmallSize][nCol + nDown] = nMatrix[nRow][nCol]; } // 交换中间第二列 nCol++;nUp = 1;nDown = -1;for (nRow = g_nSmallSize; nRow // 复制数字nMatrix[nRow - g_nSmallSize][nCol + nUp] = nMatrix[nRow][nCol];nMatrix[nRow + g_nSmallSize][nCol + nDown] = nMatrix[nRow][nCol]; } // 交换中间第三列nCol++;nUp = -2;nDown = -1;for (nRow = g_nSmallSize; nRow // 复制数字nMatrix[nRow - g_nSmallSize][nCol + nUp] = nMatrix[nRow][nCol];nMatrix[nRow + g_nSmallSize][nCol + nDown] = nMatrix[nRow][nCol]; } return true;}/*** &brief 根据中间的方格数字经过列变换计算出中间左边和右边×方格内的数字* &return 若成功生成则返回true, 否则返回false*/bool KSudokuCaculate::CacMiddleLeftAndRight(void) {int nLeft; // 左边方格的y坐标差int nRight; // 右边方格的y坐标差int nRow, nCol;// 交换中间第一行。