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