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

《数独求解的候选数优化算法设计 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数独求解的候选数优化算法设计(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数值的初步推断欲应用上述策略模式求解数独，需要首先根据有限的提示数和数独的基本原则确定各未知单元格的候选数，并以此为基础，依次执行各项策略判断算法，进而选取恰当的策略，将未知单元格的个数及各未知单元格中的

2、候选数个数降至最小，从而在最大程度上降低后续计算的复杂程度。对于数独问题数值初步推断的程序流程图如图3。通过执行上述数值初步推断流程，能够使各项策略在适当的数值分布状况下得到执行，从而保证了程序运算的高效性。3.3基于策略模式的回溯法求解对于较高难度的数独，单纯依靠由上述5项求解策略构成的数值初步推断是不能将所有未知单元格中的数字确定下来的。这时，需要在完成数值初步推断，将未知单元格的个数和其中候选数的个数降至最低的基础上，采用回溯法对各种剩余的可能情况进行验证。而在进行回溯计算的过程中，合理采用各项策

3、略，可以在最短的搜索路径内将错误的数值排除，从而降低回溯运算的迭代次数，提升算法的运算效率。回溯法求解数独的计算过程如下：（1）根据未知单元格及其候选数的情况构建多叉树。用多叉树的不同层次代表不同未知单元格，而每一层次的各个节点代表未知单元格中的候选数。（2）对包含了所有未知数可能取值情况的多叉树进行深度优先遍历，并在每一次增加搜索层次或改变同一层次的搜索节点（即测试某一未知单元格中的新候选数）时依次执行判定和推断算法。（3）判定算法：判断待验证的候选数是否与和它处于同一相关限制区域的已知数及测试数相同

4、。（4）推断算法:若该数通过判定算法的验证，则将该待验证的候选数作为测试数，并以整个数独中的所有已知数和测试数作为基础，通过执行3.2中所述五种策略的推断算法减少其余未知单元格中的候选数个数。（5）若该数未通过判定算法验证，则选取该父节点中的其余子节点进行验证。当父节点中的所有子节点均未通过验证时，则退回父节点所在层次，并搜索其余兄弟节点，并退回至第3步开始执行。（6）当搜索至叶子节点并验证成功后，将记录下的所有搜索路径作为数独的解。4计算实验根据上述计算方法，基于VisualBasic语言编制计算机程

5、序，并通过较高难度的数独算例对比上述优化算法与普通的回溯法在运算效率方面的区别。如图4所示，为一道高难度的常规数独实例及其答案的示意图。图中带有阴影的单元格为初始提示数的位置。该数独的难度主要体现在通过基于策略模式的数值初步推断后，能够确定数值的未知单元格个数十分有限（如图5所示），而欲得出最终结果，必须经过多次数值实验并排除大量候选情况。这就能够很显著得体现算法在运算效率方面的特点。通过计算机程序分别利用普通回溯法和本文基于策略模式的数独优化求解算法对该实例进行求解，并通过程序记录运算时长和迭代次数，

6、以衡量两种算法的求解效率。两种算法最终所得结果相同。针对本实例，两种求解算法的迭代次数和运算时长如表1所示。为了更为客观的反应两种计算方法的运算效率，分别对20个高难度数独进行求解，并计算出求解这些数独的平均迭代次数和运算时长（见表1）。从上表中的相关数据可以看出，无论是迭代次数还是运算时长，基于策略模式的优化求解算法比普通的回溯算法显著减小。5结论本文通过将策略模式引入数独的初步数值判断和回溯迭代计算中，并利用对应的策略判断算法，根据求解进程中出现的不同数值状况，实时选择合适的策略进行推导，以求能够在

7、最大程度上将数独的未知情况数量降至最小，从而在回溯计算的过程中减少迭代次数，提升整个算法的运算效率。通过计算实验表明，上述基于策略模式的优化求解算法能够利用推导的五项数独求解策略的合理搭配，在数值初步推断的过程中有效降低数独中的未知情况数量，从而在后续的回溯迭代计算中通过更少的搜索次数得出最终结果。并能够在整个计算过程中，使各项求解策略独立于用户而自主执行，是一种智能、高效的数独优化求解算法。