数独问题高效算法的与实现

摘 要：数独益智游戏（Sudoku）是近年来全球流行的一种智力游戏.本文通过分析数据结构、“非循环判断”预处理算法和回溯算法,深入探讨了数独问题的解决方案,并给出了该方案的实现算法,实验证明该算法是正确高效的.

关 键 词：数独；非循环判断；算法；回溯法

中图分类号：TP302

“数独”益智游戏（Sudoku）是瑞士数学家欧拉发明的,目前在国内外非常流行.游戏在9*9的单元表格中进行,单元表格不仅被分为9行、9列,也被分为3*3个九宫格.单元表格中已存在若干数字,其余为空格.游戏规则要求玩家在每个空格中填入1～9之间的数字,使每个数字在每行、每列、每个九宫格仅出现一次.国内许多论文对数独游戏的教学意义做了深入讨论,但研究其求解算法的论文不多[1],用计算机进行快速求解的算法更少,参考文献[2]使用“有限递推”预处理提高了算法的执行速度,但其本身每次都要处理候选数字也耗时不少；参考文献[3]提出了效率较高的算法,但其冲突检测还可提高效率.本文对“数独”游戏进行深入研究后用C语言设计出一种基于“非循环判断”预处理的回溯算法,然后用参考文献[2]中的三个实例及号称世界上迄今难度最大的数独游戏[4]（芬兰数学家因卡拉花费3个月时间设计的）进行测试,实践证明该算法正确且高效.

1数据结构与回溯法简介

1.1数据结构

精心设计的数据结构可让算法更加高效[5].主要的数据结构是5个整型数组,其中2个一维数组,3个二维数组：

（1）intaResult[81],该数组的用途是接收题目（空白处则初始值为0）以及保存最终结果（所有的9*9个数字按序存储在该数组中）；

（2）intaEmpty[81],该数组记载空白单元表格的序号和试填数字（前2位表示序号,第3位表示数字）,这样既可减少搜索空间又方便下一次试填数字（原试填数字+1）；

（3）intaRow[9][9],该数组标识某行某个数字是否存在,减少判断时间；

（4）intaCol[9][9],该数组标识某列某个数字是否存在,减少判断时间；

（5）intaNine[9][9],该数组标识某九宫格某个数字是否存在,减少判断时间.

1.2回溯法简介

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标.探索到某一步,发现原先选择并不优或达不到目标时,就退回一步重新选择[6].

2预处理算法

在读取数独问题时用特定数组记载空白单元表格的序号,过滤掉已填数字表格,减少搜索空间；判断某一空格能否填入某一数字时本文采用“非循环判断”预处理算法（一般采用循环判断[2][3]）,该算法思想是：按序扫描问题时,对原有数字进行预处理,即根据该格序号及数字对aRow、aCol和aNine数组进行相应标记,如：第9格（下标从0开始）的数字为5,预处理时该格行号为1、列号为0、九宫格序号为0,结果为：aRow[1][4]等于1,aCol[0][4]等于1,aNine[0][4]等于1,则表明第1行、第0列和第0九宫格不能填数字5.

3算法设计

（1）读入数独问题.

（2）给数组aEmpty、aResult、aRow、aCol和aNine赋初值.

（3）按序扫描问题,把未填数字的空格序号乘以10后存入aEmpty数组,把已填数字或0按序号存入aResult数组,同时根据序号及已经填的数字给aRow、aCol和aNine数组进行预处理.

（4）如果aEmpty数组中存在未填写数字的空格序号,则从aEmpty数组中取出一个未填写数字的空格序号,否则执行（11）.

（5）把取出的空格序号进行行号、列号及九宫格序号分解.

（6）从数字1开始直到数字9尝试填写,并对其行、列及九宫格进行冲突判断,若尝试成功执行（7）,否则执行（8）.

（7）执行相应标识处理后转到（4）.

（8）退回到上一个填数序号,若该填数序号存在则执行相应标识处理后执行（9）,否则执行（12）.

（9）如果原来填写数字的下一个数字存在,对原来填写数字的下一个数字尝试填写.

（10）下一个数字尝试填写成功执行（7）,否则执行（8）.

（11）成功找到1个解,退出.

（12）无解,退出.

//关键源代码

voidgetAnswer（inttx）

{

//tx表示未填空格数

while（no

{

row等于tno/9；//取行序号

col等于tno%9；//取列序号

tno等于aEmpty[no]/10；//取小格序号

bnum等于aEmpty[no]%10；//取小格试填数字

jno等于row/3*3+col/3；//在九宫格中对应的序号

if（rflag等于等于0）

{

//说明上次未能填数

aResult[tno]等于0；

aEmpty[no]等于tno*10；

aRow[row][bnum-1]等于0；//标识行

aCol[col][bnum-1]等于0；//标识列

aNine[jno][bnum-1]等于0；//标识九宫格

}

rflag等于0；//填数标志//bnum表示小格试填数字

for（num等于bnum+1；num<10；num++）

{

if（aRow[row][num-1]等于等于1）continue；//判断同行

if（aCol[col][num-1]等于等于1）continue；//判断同列

if（aNine[jno][num-1]等于等于1）continue；//判断九宫格

aResult[tno]等于num；//填数字

aRow[row][num-1]等于1；//标识行

aCol[col][num-1]等于1；//标识列

aNine[jno][num-1]等于1；//标识九宫格

aEmpty[no]等于tno*10+num；//第no个为"序号*10+数字"

no++；

rflag等于1；

break；//填好1个就跳出for循环

}

//没有填数

if（no等于等于0）

{

printf（"NoAnswer＼n"）；

break；

}

elseif（rflag等于等于0）

{

no--；//返回上一数重填

}

}

}

4实例测试

前3个实例取自参考文献[2],第4个实例出自芬兰数学家因卡拉[4]：

下面是对上述4题各计算5次的时间测试结果（在操作系统xp和CPU为AMD4600+（2.4G）的环境下测试的）：从上面结果可知,一般的数独难题（包括号称世界上迄今难度最大的数独游戏）可在15ms内找出答案；由此可见,本算法是高效的；通过检验本算法所给答案也是正确的.