数独游戏 算法期末大作业

数独游戏

董猛

(宁波工程学院 电信学院，浙江 宁波 315010)

摘 要: 过对数独求解规则的分析,归纳总结一套有效的求解算法,以计算机直接模拟人脑的思维方式,逐个排除不可能出现在宫格中的数字。论文详细阐述了比较排除法的算法思想,画出程序流程图,并提供主要代码。实验证明算法是正确并高效的。 关键词: 数独 策略 搜索

Sudoku game

Dong Meng

(NINGBO UNIVERSITY OF TECHNOLOGY, Ningbo,Zhejiang,315000 C hina ；)

Abstract: Logarithmic alone solve rule analysis, sum up a set of effective algorithm, in computer simulation of the human brain thinking directly, don't rule out one by one may appear in the GongGe Numbers. Paper illustrates the comparison method of algorithm thought, draw the procedure flow chart, and provides the key code. Experimental results show algorithm is correct and effective. Key words: Sudoku search strategy

1 引言

数独（すうどく，Sudoku ）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。

目前（截止2011年）发现的最少提示数9×9标准数独为17个提示，截止编辑此词条时间（2011.11.24 16:14），共发现了非等价17提示数谜题49151题。

独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

图 1 数独图册

2 算法设计

2.1 数独算法描述

本文所设计的比较排除法是以计算机直接模拟人脑思维方式进行搜索,需要选取对象后作出对比排查。以人脑思维方式,对数独题目进行求解,必定先会选定某个已知的数字,对其在其他行列进行比较,直至确定另一个可放置的位置。如果一个数字已用尽已知条件9个位置都出现,或还有空缺但是却已经无法确定其位置,则跳至下一个数字进行下一轮的比较与确定。然而计算机无法进行此类比较。由于计算机无法选定已知数,所以让计算机从选定未知数开始排查,再进行逐格的一项项排除,直至完成数独题目。 该方法是根据数独游戏的出题原则,每格所填数字必须有根据,故可确定总有格子是可以通过现有已知量进行推导的。算法如下：（伪码描述、自然语言描述、流程图） int main() {

ifstream fin(szDataFile);//读取数独初始化文件 if (!fin) {

cout << "error in open files!\n"; return -1; }

int i, j;

for (i=0; i<9; i++) for (j=0; j<9; j++)

{

fin >> data[i][j];

}

#ifdef OUTPUT_DEBUG

i = 0;

j = 6;

while(i++<j) TryOneStep();

cout << endl << j << "次后, 数据如下图: " << endl;

Output(data);

TryOneStep();

#else

while(TryOneStep());

#endif

cout << "已完成搜索: " << endl;

Output(data);

return 0;

}

如图1所示的数独中,可将每个宫格进行编号,Aij表示第i行第j列中的数字。比较排除法排除步骤例表完成第一步后开始下一轮比较,直至得出全部结果为止。

比较排除法算法描述如下:

(1)算法输入:一组数独,未知数数值为0。

(2)算法输出:一组经过运算后的数独,至少有一个原值为0的数字被改变的新状态输出。

(3)算法步骤:

Step1创建一个可取值域[1,2,3,4,5,6,7,8,9]。

Step2自上而下、自左而右搜索下一个数值为0的空格。

Step3与该空格所在宫的其他有效数字比较,消去在可取值域中两两相等的项。

Step4与该空格所在行的其他有效数字进行横向比较,消去在可取值域中两两相等的项。

Step5与该空格所在列的其他有效数字进行纵向比较,消去在可取值域中两两相等的项。

Step6判断可取值域中不为0的数字的个数是否为1,如果不是,则跳至Step8。

Step7可取值域中的唯一有效数字赋值于对应空格中,输出数独更新后的状态,跳至Step12。

Step8判断数独是否已完成,是否还有0,如果有0,则跳至Step11。

Step9判断是否运算至最后一个空格,如果不

是最后一格,则重回Step1。

Step10标记该方法该次运算不可行,跳至Step12。Step11输出该数独完成!。

Step12结束。2.2 算法实现

策略一：

void LookupInMatrix(int tdata[][9], int numberToPut) {

int i, j, k;

bool flag = false;

int count = 0;

int xToPut, yToPut;

for (k=1; k<=9; k++) //遍历1-9个方阵

{

count = 0; //寻找可下该数字的点的个数

flag = false;

for (i=0; i<9; i++)

for (j=0; j<9; j++)

{

if (datatemplate[i][j] == k)

{

if (tdata[i][j] == 0)

{

xToPut = i;

yToPut = j;

count++;

}

if (tdata[i][j] == numberToPut)

flag = true;

}

}

//如果可行，记下并在暂存数据中执行这一操作

if (!flag && count==1)

{

curstepx[curstepcount] = xToPut;

curstepy[curstepcount] = yToPut;

curstepnumber[curstepcount] = numberToPut;

strategy[curstepcount] = LOOKUPINMATRIX;

curstepcount++;

tdata[xToPut][yToPut] = numberToPut;

}

}

}

策略二：

void LookupInRow(int tdata[][9], int numberToPut) {

int row, j;

bool flag = false;

int count = 0;

int xToPut, yToPut;

for (row=0; row<9; row++)

{

count=0;

flag = false;

for (j=0; j<9; j++)

{

if (tdata[row][j] == 0)

{

xToPut = row;

yToPut = j;

count++;

}

if (tdata[row][j] == numberToPut)

flag = true;

}

//如果可行，记下这一操作, 并在暂存数据中执行该操作

if (!flag && count==1)

{

curstepx[curstepcount] = xToPut;

curstepy[curstepcount] = yToPut;

curstepnumber[curstepcount] = numberToPut;

strategy[curstepcount] = LOOKUPINROW;

curstepcount++;

tdata[xToPut][yToPut] = numberToPut;

}

}

}

策略三：

void LookupInColumn(int tdata[][9], int numberToPut) {

int col, i;

bool flag = false;

int count = 0;

int xToPut, yToPut;

for (col=0; col<9; col++)

{

count=0;

flag = false;

for (i=0; i<9; i++)

{

if (tdata[i][col] == 0)

{

xToPut = i;

yToPut = col;

count++;

}

if (tdata[i][col] == numberToPut)

flag = true;

}

// …… 此处隐藏：3305字，全部文档内容请下载后查看。喜欢就下载吧 ……