摘要:作为一种数字拼图游戏,数独在各个国家都有着广大的玩家群。目前求解数独的方法主要有两种：基于计算机的回溯法或全枚举方法和基于人的思维寻找特殊的解题技巧。本文介绍了适用于初学者的枚举法，用计算机语言实现后能有效解决数独问题，该方法虽然稍显笨拙且运算量较大，但不失为一种有效的求解方法。
关键词：数独、枚举法、计算机语言、注意搜索、推理规则
引言：数独又称九宫格，已知若干格内数字，玩家需要根据特定规则补全其余格内的数字，在两百多年的发展过程中，数独的求解形成了各种各样的思路，而枚举法则是最基础的一种解题方法。枚举法通过对规则内每一格内的可选数字逐一尝试，将各种排列方式全部考虑到并选出符合游戏规则的解，从而完成数独。这种求解数独的方法尽管复杂，但结合计算机语言则便于理解与使用。
1.数独求解规则 本文考虑六阶标准数独，图1展示了一个位于6x6方格阵列中的数独题目，在数独求解过程中必须遵从下述规则：
（1）每一行中，数字1-6都出现且只出现一次；
（2）每一列中，数字1-6都出现且只出现一次；
（3）每一个小九宫格中，数字1-6都出现且只出现一次； 游戏过程中需要确保解题步骤的逻辑性和合理性，直至得到符合规则的解。为了方便说明，对阵列中的每一格按其行列序号进行编号，如（1,1）表示第一行第一列的方格，以此类推，将36格分别编号。 2.求解思路 使用枚举的思想，可以通过以下迭代推理的步骤，求解上述数独问题。
【步骤 1】如图 2，在 6x6 方格阵列的每一格中标注 1、2、3、4、5、6，代表初始时该格可能的备选数字，暂时不考虑已知数字。
【步骤 2】逐个考虑预填已知数字，并相应修改标注。比如，(1,1)已知数字 4，依据数独游戏规则 1、2、3，按以下方法修改标注。 （1）(1,1)标注改为 0、0、0、4、0、0，其中 0 表示原对应位 1、2、3、5、6 不再能作为备选数字（下同）； （2）第 1 行（同一行）各格内，4 改作 0，不再作为备选数字； （3）第 1 列（同一列）各格内，4 改作 0，不再作为备选数字； （4）同一宫其他各格内，4 改作 0，不再作为备选数字。 经修改后，标注如图 3 示。针对图 1 给出的其余已知数字，一一处理，修改标注后，得到图 4。
【步骤 3】增添指针标记，在图 4 中每格首个数字有下划线标记，将用于后续枚举过程的操作。令 k=1。 【步骤 4】针对第 k 格寻找和测试一个合适备选数字，称为一轮（搜索）处理，可细分为 3 个小步骤。
【步骤 4.1】针对第 k 格，检查指针（下划线）所在位置的数值。若该数值可作为备选（不为 0），则至步骤 4.3，尝试修改并检查标注；若该数值为 0，则至步骤 4.2。
期刊文章分类查询,尽在期刊图书馆
【步骤 4.2】尝试把指针标记后移一位，回到步骤 4.1，但如果不再有下一位（当前已只在第 6数项，本格 6 个标注都已尝试）则表示需要回退一格搜索，执行步骤 5。
【步骤 4.3】保存当前全图标注状态。尝试修改标注，将第 k 格中指针所指数字之外备选数字清0；在同行、同列、同宫其他各格内，该数字不再作为备选数字（对应标注清 0）。检查修改后的全图标注局面，若发现某格标注全 0，说明此路不通，放弃上述对标注的修改，前往步骤 4.2 继续；否则，将本次对标注的修改记录为“处理第 k 格时的修改”，前往步骤 6。
【步骤 5】（回退一格）将第 k 格指针复原指向首个数字（无论其是否为 0），令 k=k-1，如果 k 变为 0 说明本题无解，终止算法，否则继续。将全图标注恢复到“处理第 k 格时的修改”之前的状态，将第 k 格指针后移一位，转往步骤 4.1，但如果不再有下一位，则表示需要再次回退，重复执行本步骤 5。
【步骤 6】（前进一格）令 k=k+1，前往步骤 4.1，但如果已经有 k=37，说明求解已完成，停止算法，此时全图每一格都只有一个有效备选数字标注，可作为答案。 3.关键步骤实例 3.1前进一格的操作 图 5 是第 14 格即(3,2)已处理后开始处理第 15 格时的标注状态，保存好此时的全图标注情况。为方便说明，加深了(3,3)的底色。此时，第 15 格指针位于首个数字 1，所以选择它作为尝试。(3,3)中除 1 之外，全部清 0；同行、同列、同宫的其他格，1 不再作为备选，(4,3)、(3,4)因此受到实质性影响。全图标注状态如图 6，经检查未发现有任何一格标注变为全 0 的情况。因此，前进一格处理第16 格。 3.2回退一格的操作 图 6 是第 15 格即(3,3)经处理后开始处理第 16 格时的标注状态，保存好此时的全图标注情况。此时，第 16 格指针位于首个数字 0，无法作为备选，经多次后移指针搜索，确定数字 6 作为尝试。(3,4)中除 6 之外，已全部为 0；同行、同列、同宫的其他格，6 不再作为备选，(3,6)、(6,4)因此受到实质性影响。全图标注状态如图 7，经检查发现(3,6)、(6,4)标注出现全 0 的情况，说明此路不通，需回退一格继续搜索。将全图标注还原成第 15 格处理前状态，如图 8，请注意看，它与图 5 的差异仅在于第 15 格指针已后移到第 2 位的 0。
总结：从本文的枚举算法研究来看，此类算法操作过程比较简单，很容易理解和掌握；但不足的是计算次数与频率比较大，速度慢。因此，这类方法适用于比较简单的数独问题，对于复杂问题，建议寻找特殊求解方法技巧。
参考文献：【1】李盘荣. “数独”游戏的算法研究与实现[J]. 电脑知识与技术, 2008, 3(26):113-115.
【2】杜琦, 孔银飞, 罗程宏. 数独问题初探[J]. 数学教学, 2009(1):26-29.
【3】肖华勇, 田铮, 马雷. 数独基于规则的逐步枚举算法设计[J]. 计算机工程与设计, 2010, 31(5):1035-1037. 【4】易珺, 朱静文, 曹东. 数独求解算法的设计与实现[J]. 科学技术与工程, 2010, 10(27):6772-6774.
【5】肖华勇, 杨菲菲, 黄奔茹. 基于区域序列枚举法的蜂巢数独求解算法研究[J]. 计算机工程与应用, 2014, 50(23):36-40.
论文作者:李宁
论文发表刊物:《青年生活》2018年第7期
论文发表时间:2018/11/17
标签：数字论文; 步骤论文; 数独论文; 指针论文; 算法论文; 全图论文; 方法论文; 《青年生活》2018年第7期论文;