基于策略模式的数独优化求解算法研究

1、基于策略模式的数独优化求解算法研究 摘 要根据常规数独问题的基本规则，推导了五项数 独求解基础方法，然后结合计算机程序的实现，将其设计为 可各自独立执行的算法(策略) 。在此基础上，以人工求解 数独问题的思维过程为依据，提出了基于策略模式的数独优 化求解算法。该算法实现了在数独问题的初步推断和后续回 溯法求解过程中根据各单元格出现的不同数值情况自主判 定并选择执行不同的策略，从而通过较少的运算量将未知情 况数量降至最小，提高了计算机求解数独的运算效率。 【关键词】数独 策略模式 回溯法 优化算法 1 引言 数独( Sudoku )是一项起源于瑞士，在美国形成雏形， 在日本确立名称并得以进一步发

2、展的数学逻辑游戏。数独以 其千变万化的数字排列和灵活多样的求解思维方法而迅速 风靡全球，被公认为一种有效考验和增强大脑逻辑思维能力 的方法。 如图1 (a)所示，常规数独是将一个大正方形平均划分 为 3 行 3 列共 9 个九宫格。每个九宫格中又包含 3 行 3 列共 9个小单元格。这样，大正方形就由 9行( R 1 -R9) 、9列( C 1 -C9) 共 81 个小单元格构成。数独的目标是根据有限的提示数， 在大正方形的每个单元格内填入 1-9 这九个整数中的某一个， 使大正方形中的每一行、每一列及每个九宫格内均包含 1-9 这九个整数，不能重复也不可遗漏。 图1 （a）为一道常规数独问题

3、实例，已给出 17个数字 作为提示数。其中的深色部分代表与单元格R4C6处于同一 行（R4）、同一列（C6）及同一九宫格（R4C4-R6C6的区域。 在本文中，这 3 个区域称为“相关限制区域” 。在这些区域 中所包含的所有数字均不可与对应单元格中的数字相同。而 数独的最终解需要使整个大正方形中的 81 个单元格对应的 全部相关限制区域均符合约束条件。对于常规数独而言，满 足条件的解唯一存在。图（b）为该数独问题对应的唯一解， 其中的深色单元格代表给出的作为最初推断依据的提示数。 目前，利用计算机程序求解数独问题的主要思路是基于 初步逻辑判断后的穷举法或回溯法。穷举是指将数独中的所 有候选情况

4、以多叉树的形式逐层遍历，并根据规则逐一排除， 最终在海量候选情况中筛选出问题的唯一解。该方法逻辑结 构简单，易于计算机程序实现， 但运算量极大， 算法效率低。 而回溯法是在穷举法的基础上对多叉数每一次子节点的搜 索增加验证机制，一旦判定某一节点不包含问题的解，则该 节点与其下的子树全部排除并回溯至父节点重新搜索，直到 搜索至叶子节点并验证通过为止，即可得出满足全部约束条 件的结果。相较于穷举法，回溯法在搜索过程中排除了一部 分不必要的分支，明显减少了运算量，但由于缺乏数独问题 所涉及的逻辑推断成分，所以仍然搜索了大量不必要的候选 情况。 如果在回溯搜索的基础上依据逻辑推断方式增加相互 独立的求

5、解策略，并通过策略模式根据出现的不同情况选择 适当的算法，便可以在很大程度上减少候选情况的数量和未 知单元格的个数，从而降低回溯搜索的迭代次数，进一步提 高运算效率。 2 数独问题的性质与基础求解策略 2.1 数独的基本性质 根据上文所述常规数独问题的基本规则： “所有单元格 中的数字均不可与它的 3 个相关限制区域中所包含的任何数 字重复”，可以得出如下性质： 性质 1：某单元格中的数字不可能是它的 3 个相关限制 区域中存在的任何一个数字； 性质 2：每一个单元格有且仅有唯一的解，它一定是1 到 9 这九个整数中的某一个。 性质 3：任何一个单元格的 3 个相关限制区域都是由 9 个单元格

6、（包含自身）所构成的， 1-9 这九个数字会在每一 个相关限制区域中出现且仅出现一次。 性质 4：在某一行、某一列或某一九宫格中，若某一数 字只可能存在于确定的几个单元格中，则其余单元格不可能 出现这一数字 2.2 数独的基础求解策略 根据上述性质，可推导出针对数独问题的 5 项基础求解 策略，而针对该策略的描述、应用实例及程序算法实现如下 所述： 策略 1：根据性质 2 可知，当某未知单元格中仅剩一个 候选数时，它必然是该单元格的唯一解。 该策略可能在两种情况下得到应用。其一是该未知单元 格的相关限制区域内已经存在八个互不相同的数字，则此单 元格只能选择未出现的那个数字；其二是通过其它策略将

7、单 元格的候选数个数减小到了一个，从而得出唯一的解。 策略 1 实例：如图 2 所示，为某数独问题实例，深色背 景的单元格代表提示数的位置。通过候选数计算可知，在单 元格 R4C8 中的候选数列表内仅存在一个数字“ 5”，则该单 元格的解必然为数字“ 5”。 策略 1 算法实现：在计算过程中，使用一个整型变量对 每一个未知单元格每次候选数个数的变化进行记录，当等于 1 时，将剩余的唯一候选数作为该单元格的解。 策略 2 ：根据性质 3 可知，当某一数字在其一个相关限 制区域的所有未知单元格候选数列表中仅出现一次时，该数 字必定为该单元格的解。 策略2实例：在图2中，C3列的所有未知单元格的候选

8、 数列表中仅有 R7C3中存在数字“ 2”，这说明该列中除 R7C3 以外的位置均不可能出现“2”， 故这一数字必然只能填在 单元格 R7C3内。 策略 2 算法实现：对每一行、每一列及每一个九宫格中 各个数字在各未知单元格候选数列表中出现的次数进行记 录，当某一数字的出现次数为 1 时，则找到候选数列表包含 该数字的单元格，将该数字作为单元格的解。 策略 3 ：根据性质 4，在某一行、某一列或某一九宫格 中，有两个单元格的候选数列表中仅包含相同的两个候选数， 则这两个数字必定只存在于这两个单元格中，可在所对应的 相关限制区域的其它单元格候选数列表中删除这两个数字。 策略3实例：如图2中的C8

9、列，单元格 R5C8和R6C8 的候选数均为 “2”和“9” ，则该列中应填的数字 “2”和“9” 只能在这两个单元格中选择，所以可在C8列其它单元格的 候选数列表中删除数字“ 2”和“ 9”。策略 3算法实 现：对候选数个数为 2 的单元格所在的每一个相关限制区域 进行搜索，若搜索到和它具有相同候选数列表的单元格时， 则在对应的相关限制区域的其它单元格的候选数列表中删 除这两个数字。 策略 4：依据性质 4，在某一九宫格中，当所有候选数 列表中含有某一数字的单元格均位于同一行（列）时，则可 将这一数字在该行（列）中的其它单元格的候选数列表中删 除。 策略4实例：在图2的九宫格（R7C7-R9

10、C9中，数字 “3”仅在R7行出现（R7C7和R7C9，说明该九宫格中的数 字“ 3”只可能出现在 R7行。这也说明整个 R7行中的数字 “3”仅会在九宫格（R7C7-R9C9的区域内出现。因此，可 以在R7行的其它位置（九宫格 R7C7-R9C9以外）的候选数 列表中删除数字“ 3”。 策略 4 算法实现：遍历每个九宫格，依次记录每个候选 数在该九宫格中出现的行数和列数。当某一数字对应可能出 现的行数或列数全部相同时，则删除该行（列）中处于其它 九宫格范围的单元格候选数列表中的这一数字。 策略 5：同样依据性质 4，在某一行或某一列中，当所 有候选数列表中含有某一数字的单元格均位于同一九宫格

11、 时，则可将这一数字在该九宫格其它单元格的候选数列表中 删除。 策略5实例：如图2,在R7行中，数字8仅出现在R7C5 和R7C4这两个单元格中，而它们同属于一个九宫格 （R7C4-R9C6的区域内。则该行中的数字“ 8”必然位于这 一九宫格中。故该九宫格中的数字“ 8”也应该在R7行，所 以可将九宫格中其它位置候选数列表中的数字“ 8”删除。 策略 5 算法实现：遍历每一行（列 ，记录每个候选数 所出现的列（行 ，当某个数字所出现的位置均在同一九宫 格区域中时，则在该九宫格中其它行（列）的单元格候选数 列表中删除这一数字。 3 数独优化求解算法 3.1 策略判断算法 上文所述 5 项策略涵盖

12、了数独问题求解过程中的主要逻 辑推断方式，且它们之间可以相互独立存在。但是在各个策 略的执行过程中也会互相影响和制约：一部分策略的执行可 能会为其它策略的应用创造新的条件，而也有可能会消除原 本具备执行某项策略的初始条件。因此，在计算过程的不同 情况下，自主合理的选择适宜的策略进行逐步推导，会对提 高求解效率起到积极的作用。 为使整个算法能够独立于用户运行，从而实现自主根据 数值分布状态选择适当的策略进行逐步求解，需要采用策略 模式。 策略模式是一种将一系列可独立存在的具体策略进行 封装，并利用策略提取函数在程序运行的各个阶段自主选择 适宜的策略进行求解的特殊算法。 对于数独问题而言，要实现在

13、推导过程中对各项策略的 自主提取，需要用到针对上述五项求解策略的提取算法。根 据这些策略执行的先决条件，可设计提取算法如下： 对每一个未知单元格使用变量（CountCand （r, c）,记 录并更新单元格（r, c）中的候选数个数。此外，依次对每 一行、每一列及每一个九宫格中各未知单元格进行搜索，对 每一个未知数i在相关限制区域中出现的次数(Counti)及第 j次出现时的行数(Rowi (j)与列数(Columni (j)进行 记录，并在每一个相关限制区域搜索完成后，利用如下策略 判断算法判定是否具备执行某一策略的前提条件： 策略 1 判断算法：当 CountCand( r，c)=1 时，

14、则单元 格(r，c)中仅存在唯一候选数，具备执行策略1的条件； 策略 2 判断算法：当 Counti=1 时，数字 i 仅在未知单元 格( Rowi ( 1)， Columni ( 1)出现过一次，则该单元格具 备执行策略 2 的条件； 策略 3判断算法：当 Counti1=2，Counti2=2 且 Rowi1( 1 ) =Rowi2( 1 )； Rowi1 ( 2)=Rowi2( 2)； Columni1 ( 1 )=Columni2 ( 1 )； Columni1 ( 2)=Columni2 ( 2)时，说明未知数 i1 ， i2 仅存在于单元格 ( Rowi1 ( 1 )， Colum

15、ni1 ( 1 )和( Rowi1 ( 2)， Columni1 ( 2)中，适用于策略 3； 策略4判断算法：当完成搜索九宫格(r，c)时(r, c) 代表九宫格左上角的坐标)，若Rowi (1) =Rowi (2)二， 或Columni (1) =Columni (2)=，则说明该九宫格内的 数字 i 位于同一行或同一列中，则适用于策略 4； 策略 5 判断算法： 在完成搜索第 n 行后，若对于数字 i： 1Counti3，且 Columni (1)、Columni (Counti )均 为 m 、 m+1 或 m+2 时( m 为 1 或 4 或 7)，则适用于策略 5。 3.2 数值的初步推断 欲应用上述策略模式求解数独，需要首先根据有限的提 示数和数独的基本原则确定各未知单元格的候选数，并以此 为基础， 依次执行各项策略判断算法， 进而选取恰当的策略， 将未知单元格的个数及各未知单元格中的候选数个数降至 最小，从而在最大程度上降低后续计算的复杂程度。对于数 独问题数值初步推断的程序流程图如图3。 通过执行上述数值初步推断流程，能够使各项策略在适 当的数值分布状况下得到执行，从而保证了程序运算的高效 性。 3.3 基于策略模式的回溯法求解 对于较高难度的数独，单纯依靠由上述 5 项求解策略构