数独问题的一种简单解法

黄皓

摘要：在计算机解决数独问题的算法中，回溯法是非常有效的。这是一种数据结构简单、算法逻辑清晰、程序简洁明了、运行高速有效的解题方法，并结合源程序与实例进行说明和论述。

关键词：数独；算法；回溯；穷举；lcc-win32

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2014）22-5340-05

数独是一种逻辑填数游戏，它起源于瑞士数学家欧拉提出的拉丁方阵。20世纪70年代该游戏在美国兴起，80年代中期开始在日本流行，“数独”（sudoku）一词就源自于日本，在本世纪初数独游戏传入我国，2005年起风靡世界，其热潮至今仍方兴未艾，很多世界著名的报纸都有数独智力题的连载，每年在世界各地都举行各种各样的数独比赛，其中2013年世界数独大赛在中国举行。

1 数独游戏规则

数独是9*9的方阵，其中又可分为9个3*3的九宫格，如图1所示。玩家在方阵中填入1-9之间的数字，保证每一行、每一列、每一个九宫中的数字都不相同，所以数独又可以看作是有宫的9阶拉丁方阵。通常，方阵事先给定一些数字，以便于玩家依据这些初始数字进行填空，而初始数字的多寡与位置，亦一定程度上决定着题目的难易程度以及解是否能够唯一。据推证，最少必须有17个初始数字方可保证题目具有唯一的解。有关数独的详细资料请看参考文献[1]。

2 解法

数独可以锻炼人的脑力，玩家可以使用摒除法、余数法等方法来逐步求解。而对使用电脑来计算数独题目的研究也有很多，常用算法有递归法、候选数回溯法、枚举法、遗传算法、方程求解、使用Dancing Link算法等。由于计算机运算速度极快，对于此类有限集合的计算问题，我们可以简单地采用回溯穷举的方法来解题，几乎所有的数独题目都可以迅速地得到结果。该文提出的就是这样一种简洁高效的数独解法，其解决一道数独难题所花时间通常在ms级别。与其它回溯算法相比，本算法采用的数据结构更为简单，逻辑更为清晰。

3 程序结构

程序主体由1个全局二维数组和3个函数构成。

3.1 二维数组Table

该数组为9*9的二维数组，用来存放数独方阵每一个格子的数值。初始化时，它接收来自用户输入的提示数，试探填入数字时，它也是提供比较判断的基础，最后，如果题目有解，输出其中的每一行、每一列的数字。

3.2 函数InputTable

该函数没有输入、输出参数，其功能是输出提示信息，并接受用户输入的数独方阵，每一行的输入类似于“..1.3..7.”的形式，其中“.”（也可以为0或空格）为待填空格，数字为提示数。每一行输入完毕，就初始化二维数组Table对应的行中元素，待填空格对应的单元被初始化为0。如输入其它的内容或输入不符合规则，则退出程序。

3.3 函数Ok

该函数有三个参数：参数m为试探填入的数字，x和y是待填空格在二维数组Table中的位置。函数的功能是检测试探数是否符合数独游戏的规则。如果在同一行、同一列和九宫中没有与m相同的数字，则试探成功函数并返回1，否则失败并返回0。关键点在于计算（x，y）对应的九宫左上角在Table中的位置（x0，y0），然后循环比较即可。

3.4 函数main

主函数的功能主要完成穷举与回溯等工作。试探时采用的是暴力穷举数字1-9而非候选数的方式。因为如果采用候选数方式，则需要事先对Sp中每一个空格扫描出候选数，用相应的数据结构来储存，这样要增加数据结构；然后在试探时依次从该数据结构中取出候选数，这同样需要时间开销，而逻辑结构和程序也会变得复杂。

函数首先对二维数组Table进行扫描，记录所有待填空格（即值为0的元素）在数组中的位置，保存在数组Sp中，这是一个2*81的数组。该数组是算法的关键，通过此数组我们就把一个图的问题转化为一个线性表的问题。然后是主循环，从Sp数组的起始元素开始进行试探与回溯，当处理完Sp中所有的空格，那么表示得到了问题的解，如果回溯完Sp的起始元素仍旧不行，则表示问题无解。算法描述如图2所示。

4 源程序

6 结束语

数独这种游戏对于锻炼人的逻辑思考能力是大有裨益的，在使用计算机来解决数独问题的算法中，实践证明，该文提出的是一种数据结构简单、算法逻辑清晰、程序简洁明了、运行高速有效的解决方法。

参考文献：

[1] Frazer Jarvis.Sudoku enumeration problems[EB/OL].http：//www.afjarvis.staff.shef.ac.uk/sudoku/.

[2] 雷蕾，沈富可.关于数独问题的算法的设计与实现[J]电脑知识与技术，2007（2）：481-523.

[3] 李盘荣.数独游戏的算法研究与实现[J].电脑知识与技术，2008，26（3）：1715-1717.

[4] 王琼，邹晟.数独问题的求解、评价与生成算法的研究[J].南京师范大学学报：工程技术版，2010，10（1）：76-79.

[5] 黎永达，邓秀勤.基于改进的遗传算法的数独谜题求解[J]计算机应用与软件，2011，28（3）：68-70.

[6] 肖华勇，程海礁，王月兴.九宫数独的方程求解算法研究[J]计算机应用，2012，32（10）：2907-2910.

[7] 姜华林.数独问题高效算法的研究与实现[J]计算机光盘软件与应用，2013（12）：82-83.

[8] Jacob Navia.LCC-Win： A free compiler system for Windows Operating Systems by Jacob Navia[EB/OL]. http：//www.cs.virginia.edu/～lcc-win32/.