数独求解的候选数优化算法设计

(2)=…，则说明该九宫格内的数字i 位于同一

行或同一列中，则适用于策略4；

策略5 判断算法：在完成搜索第n 行后，

若对于数字i：1<Counti ≤ 3，且Columni (1)、…、

Columni (Counti ) 均为m、m+1 或m+2 时（m

为1 或4 或7），则适用于策略5。

3.2 数值的初步推断

欲应用上述策略模式求解数独，需要首

先根据有限的提示数和数独的基本原则确定各

未知单元格的候选数，并以此为基础，依次执

行各项策略判断算法，进而选取恰当的策略，

将未知单元格的个数及各未知单元格中的候选

数个数降至最小，从而在最大程度上降低后续

计算的复杂程度。对于数独问题数值初步推断

的程序流程图如图3。

通过执行上述数值初步推断流程，能够使

各项策略在适当的数值分布状况下得到执行，

从而保证了程序运算的高效性。

3.3 基于策略模式的回溯法求解

对于较高难度的数独，单纯依靠由上述5

项求解策略构成的数值初步推断是不能将所有

未知单元格中的数字确定下来的。这时，需要

在完成数值初步推断，将未知单元格的个数和

其中候选数的个数降至最低的基础上，采用回

溯法对各种剩余的可能情况进行验证。而在进

行回溯计算的过程中，合理采用各项策略，可

以在最短的搜索路径内将错误的数值排除，从

而降低回溯运算的迭代次数，提升算法的运算

效率。

回溯法求解数独的计算过程如下：

（1）根据未知单元格及其候选数的情况

构建多叉树。用多叉树的不同层次代表不同未

知单元格，而每一层次的各个节点代表未知单

元格中的候选数。

（2）对包含了所有未知数可能取值情况

的多叉树进行深度优先遍历，并在每一次增加

搜索层次或改变同一层次的搜索节点（即测试

某一未知单元格中的新候选数）时依次执行判

定和推断算法。

（3）判定算法：判断待验证的候选数是

否与和它处于同一相关限制区域的已知数及测

试数相同。

（4）推断算法: 若该数通过判定算法的

验证，则将该待验证的候选数作为测试数，并

以整个数独中的所有已知数和测试数作为基

础，通过执行3.2 中所述五种策略的推断算法

减少其余未知单元格中的候选数个数。

（5）若该数未通过判定算法验证，则选

取该父节点中的其余子节点进行验证。当父节

点中的所有子节点均未通过验证时，则退回父

节点所在层次，并搜索其余兄弟节点，并退回

至第3 步开始执行。

（6）当搜索至叶子节点并验证成功后，

将记录下的所有搜索路径作为数独的解。

4 计算实验

根据上述计算方法，基于Visual Basic 语

言编制计算机程序，并通过较高难度的数独算

例对比上述优化算法与普通的回溯法在运算效

率方面的区别。

如图4 所示，为一道高难度的常规数独

实例及其答案的示意图。图中带有阴影的单元

格为初始提示数的位置。该数独的难度主要体

现在通过基于策略模式的数值初步推断后，能

够确定数值的未知单元格个数十分有限（如图

5 所示），而欲得出最终结果，必须经过多次

数值实验并排除大量候选情况。这就能够很显

著得体现算法在运算效率方面的特点。

通过计算机程序分别利用普通回溯法和

本文基于策略模式的数独优化求解算法对该实

例进行求解，并通过程序记录运算时长和迭代

次数，以衡量两种算法的求解效率。两种算法

最终所得结果相同。针对本实例，两种求解算

法的迭代次数和运算时长如表1 所示。

为了更为客观的反应两种计算方法的运

算效率，分别对20 个高难度数独进行求解，

并计算出求解这些数独的平均迭代次数和运算

时长（见表1）。从上表中的相关数据可以看出，

无论是迭代次数还是运算时长，基于策略模式

的优化求解算法比普通的回溯算法显著减小。

5 结论

本文通过将策略模式引入数独的初步数

值判断和回溯迭代计算中，并利用对应的策略

判断算法，根据求解进程中出现的不同数值状

况，实时选择合适的策略进行推导，以求能够

在最大程度上将数独的未知情况数量降至最

小，从而在回溯计算的过程中减少迭代次数，

提升整个算法的运算效率。

通过计算实验表明，上述基于策略模式

的优化求解算法能够利用推导的五项数独求解

策略的合理搭配，在数值初步推断的过程中有

效降低数独中的未知情况数量，从而在后续的

回溯迭代计算中通过更少的搜索次数得出最终

结果。并能够在整个计算过程中，使各项求解

策略独立于用户而自主执行，是一种智能、高

效的数独优化求解算法。

参考文献

[1] 李昊. 基于图搜索策略的数独问题

算法与实现[J]. 通化师范学院学

报,2009,v.30;No.17510:43-45.

[2] 肖华勇, 田铮, 马雷. 数独基于规则的逐

步枚举算法设计[J]. 计算机工程与设计,

2010,v.31;No.26905:1035-1037+1113.

[3] 程曦, 肖华勇, 吴林波. 数独求解的候

选数优化算法设计[J]. 科学技术与工

程,2011,v.1126:6409-6412.

[4] 肖华勇, 程海礁, 王月兴. 九宫数独

的方程求解算法研究[J]. 计算机应

用,2012,v.32;No.26610:2907-2910.

[5] 王新鑫, 李星, 钟宁. 数独游戏的难度划

分及创建算法设计[J]. 计算机光盘软件

与应用,2013,v.16;No.22518:45-46.

[6] 王琼, 邹晟. 数独问题的求解、评价与生

成算法的研究[J]. 南京师范大学学报( 工

程技术版),2010,v.10;No.3701:76-79.

作者简介

宋韬（1989-），男，四川省成都市人。工学硕士。

现为中国民航飞行学院助理讲师。主要研究方

向为多系统定位信息融合理论与方法。

作者单位

中国民航飞行学院空中交通管理学院 四川省

德阳市 618307

表1：两种数独求解算法运算效率对比表

算法名称普通回溯法基于策略模式的优化求解算法

本算例迭代次数96929 5051

本算例运算时长110ms 6ms

平均迭代次数119235 6223

平均运算时长133ms 7ms