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

《基于策略模式的数独优化求解算法研究 》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于策略模式的数独优化求解算法研究【关键词】数独策略模式回溯法优化算法1引言数独（Sudoku）是一项起源于瑞士，在美国形成雏形，在日本确立名称并得以进一步发展的数学逻辑游戏。数独以其千变万化的数字排列和灵活多样的求解思维方法而迅速风靡全球，被公认为一种有效考验和增强大脑逻辑思维能力的方法。如图1(a)所示，常规数独是将一个大正方形平均划分为3行3列共9个九宫格。每个九宫格中又包含3行3列共9个小单元格。这样，大正方形就由9行(R1-R9)、9列(C1-C9)共81个小单元格构成。数独的目标是根据有限的提示数，在大正方形的每个单元格内填入1-9这九个整数中的某一个，使大正方形中的每一行

2、、每一列及每个九宫格内均包含1-9这九个整数，不能重复也不可遗漏。图1(a)为一道常规数独问题实例，已给出17个数字作为提示数。其中的深色部分代表与单元格R4C6处于同一行(R4)、同一列(C6)及同一九宫格(R4C4-R6C6)的区域。在本文中，这3个区域称为“相关限制区域”。在这些区域中所包含的所有数字均不可与对应单元格中的数字相同。而数独的最终解需要使整个大正方形中的81个单元格对应的全部相关限制区域均符合约束条件。对于常规数独而言，满足条件的解唯一存在。图1(b)为该数独问题对应的唯一解，其中的深色单元格代表给出的作为最初推断依据的提示数。目前，利用计算机程序求解数独问题的主要

3、思路是基于初步逻辑判断后的穷举法或回溯法。穷举是指将数独中的所有候选情况以多叉树的形式逐层遍历，并根据规则逐一排除，最终在海量候选情况中筛选出问题的唯一解。文/宋韬根据常规数独问题的基本规则，推导了五项数独求解基础方法，然后结合计算机程序的实现，将其设计为可各自独立执行的算法（策略）。在此基础上，以人工求解数独问题的思维过程为依据，提出了基于策略模式的数独优化求解算法。该算法实现了在数独问题的初步推断和后续回溯法求解过程中根据各单元格出现的不同数值情况自主判定并选择执行不同的策略，从而通过较少的运算量将未知情况数量降至最小，提高了计算机求解数独的运算效率。摘要该方法逻辑结构简单，易于计

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

5、迭代次数，进一步提高运算效率。2数独问题的性质与基础求解策略2.1数独的基本性质根据上文所述常规数独问题的基本规则：“所有单元格中的数字均不可与它的3个相关限制区域中所包含的任何数字重复”，可以得出如下性质：性质1：某单元格中的数字不可能是它的3个相关限制区域中存在的任何一个数字；性质2：每一个单元格有且仅有唯一的解，它一定是1到9这九个整数中的某一个。性质3：任何一个单元格的3个相关限制区域都是由9个单元格(包含自身)所构成的，1-9这九个数字会在每一个相关限制区域中出现且仅出现一次。性质4：在某一行、某一列或某一九宫格中，若某一数字只可能存在于确定的几个单元格中，则其余单元格不可能

6、出现这一数字。2.2数独的基础求解策略根据上述性质，可推导出针对数独问题的5项基础求解策略，而针对该策略的描述、应用实例及程序算法实现如下所述：策略1：根据性质2可知，当某未知单元格中仅剩一个候选数时，它必然是该单元格的唯一解。该策略可能在两种情况下得到应用。其一是该未知单元格的相关限制区域内已经存在八个互不相同的数字，则此单元格只能选择未出现的那个数字；其二是通过其它策略将单元格的候选数个数减小到了一个，从而得出唯一的解。策略1实例：如图2所示，为某数独问题实例，深色背景的单元格代表提示数的位置。通过候选数计算可知，在单元格R4C8中的候选数列表内仅存在一个数字“5”，则该单元格的解

7、必然为数字“5”。策略1算法实现：在计算过程中，使用一个整型变量对每一个未知单元格每次候选数个数的变化进行记录，当等于1时，将剩余的唯一候选数作为该单元格的解。策略2：根据性质3可知，当某一数字在其一个相关限制区域的所有未知单元格候选数列表中仅出现一次时，该数字必定为该单元格的解。策略2实例：在图2中，C3列的所有未知单元格的候选数列表中仅有R7C3中存在数字“2”，这说明该列中除R7C3以外的位置均不可能出现“2”，故这一数字必然只能填在单元