基于策略模式的数独优化求解算法研究
2017年5月20日 08:38 作者:lunwwcom【关键词】数独 策略模式 回溯法 优化算法
1 引言
数独（Sudoku）是一项起源于瑞士，在
美国形成雏形，在日本确立名称并得以进一步
发展的数学逻辑游戏。数独以其千变万化的数
字排列和灵活多样的求解思维方法而迅速风靡
全球，被公认为一种有效考验和增强大脑逻辑
思维能力的方法。
如图1(a) 所示，常规数独是将一个大正
方形平均划分为3 行3 列共9 个九宫格。每个
九宫格中又包含3 行3 列共9 个小单元格。这
样，大正方形就由9 行(R1-R9)、9 列(C1-C9)
共81 个小单元格构成。数独的目标是根据有
限的提示数，在大正方形的每个单元格内填入
1-9 这九个整数中的某一个，使大正方形中的
每一行、每一列及每个九宫格内均包含1-9 这
九个整数，不能重复也不可遗漏。
图1(a) 为一道常规数独问题实例，已给
出17 个数字作为提示数。其中的深色部分代
表与单元格R4C6处于同一行(R4)、同一列(C6)
及同一九宫格(R4C4-R6C6) 的区域。在本文中，
这3 个区域称为“相关限制区域”。在这些区
域中所包含的所有数字均不可与对应单元格中
的数字相同。而数独的最终解需要使整个大正
方形中的81 个单元格对应的全部相关限制区
域均符合约束条件。对于常规数独而言，满足
条件的解唯一存在。图1(b) 为该数独问题对
应的唯一解，其中的深色单元格代表给出的作
为最初推断依据的提示数。
目前，利用计算机程序求解数独问题的
主要思路是基于初步逻辑判断后的穷举法或回
溯法。穷举是指将数独中的所有候选情况以多
叉树的形式逐层遍历，并根据规则逐一排除，
最终在海量候选情况中筛选出问题的唯一解。
文/宋韬
根据常规数独问题的基本规
则，推导了五项数独求解基础方
法，然后结合计算机程序的实现，
将其设计为可各自独立执行的算
法（策略）。在此基础上，以人
工求解数独问题的思维过程为依
据，提出了基于策略模式的数独
优化求解算法。该算法实现了在
数独问题的初步推断和后续回溯
法求解过程中根据各单元格出现
的不同数值情况自主判定并选择
执行不同的策略，从而通过较少
的运算量将未知情况数量降至最
小，提高了计算机求解数独的运
算效率。
摘 要
该方法逻辑结构简单，易于计算机程序实现，
但运算量极大，算法效率低。而回溯法是在穷
举法的基础上对多叉数每一次子节点的搜索增
加验证机制，一旦判定某一节点不包含问题的
解，则该节点与其下的子树全部排除并回溯至
父节点重新搜索，直到搜索至叶子节点并验证
通过为止，即可得出满足全部约束条件的结果。
相较于穷举法，回溯法在搜索过程中排除了一
部分不必要的分支，明显减少了运算量，但由
于缺乏数独问题所涉及的逻辑推断成分，所以
仍然搜索了大量不必要的候选情况。
如果在回溯搜索的基础上依据逻辑推断
方式增加相互独立的求解策略，并通过策略模
式根据出现的不同情况选择适当的算法，便可
以在很大程度上减少候选情况的数量和未知单
元格的个数，从而降低回溯搜索的迭代次数，
进一步提高运算效率。
2 数独问题的性质与基础求解策略
2.1 数独的基本性质
根据上文所述常规数独问题的基本规则：
“所有单元格中的数字均不可与它的3 个相关
限制区域中所包含的任何数字重复”，可以得
出如下性质：
性质1：某单元格中的数字不可能是它的
3 个相关限制区域中存在的任何一个数字；
性质2：每一个单元格有且仅有唯一的解，
它一定是1 到9 这九个整数中的某一个。
性质3：任何一个单元格的3 个相关限制
区域都是由9 个单元格( 包含自身) 所构成的，
1-9 这九个数字会在每一个相关限制区域中出
现且仅出现一次。
性质4：在某一行、某一列或某一九宫格
中，若某一数字只可能存在于确定的几个单元
格中，则其余单元格不可能出现这一数字。
2.2 数独的基础求解策略
根据上述性质，可推导出针对数独问题
的5 项基础求解策略，而针对该策略的描述、
应用实例及程序算法实现如下所述：
策略1：根据性质2 可知，当某未知单元
格中仅剩一个候选数时，它必然是该单元格的
唯一解。
该策略可能在两种情况下得到应用。其
一是该未知单元格的相关限制区域内已经存在
八个互不相同的数字，则此单元格只能选择未
出现的那个数字；其二是通过其它策略将单元
格的候选数个数减小到了一个，从而得出唯一
的解。
策略1 实例：如图2 所示，为某数独问
题实例，深色背景的单元格代表提示数的位置。
通过候选数计算可知，在单元格R4C8 中的候
选数列表内仅存在一个数字“5”，则该单元
格的解必然为数字“5”。
策略1 算法实现：在计算过程中，使用
一个整型变量对每一个未知单元格每次候选数
个数的变化进行记录，当等于1 时，将剩余的
唯一候选数作为该单元格的解。
策略2：根据性质3 可知，当某一数字在
其一个相关限制区域的所有未知单元格候选数
列表中仅出现一次时，该数字必定为该单元格
的解。
策略2 实例：在图2 中，C3 列的所有未
知单元格的候选数列表中仅有R7C3 中存在数
字“2”，这说明该列中除R7C3 以外的位置
均不可能出现“2”， 故这一数字必然只能填
在单元格R7C3 内。
策略2 算法实现：对每一行、每一列及
每一个九宫格中各个数字在各未知单元格候选
数列表中出现的次数进行记录，当某一数字的
出现次数为1 时，则找到候选数列表包含该数
字的单元格，将该数字作为单元格的解。
策略3：根据性质4，在某一行、某一列
或某一九宫格中，有两个单元格的候选数列表
图1：常规数独问题实例及其唯一解示意图
182 • 电子技术与软件工程 Electronic Technology & Software Engineering
计算机技术应用 • the Application of Computer Technology
中仅包含相同的两个候选数，则这两个数字必
定只存在于这两个单元格中，可在所对应的相
关限制区域的其它单元格候选数列表中删除这
两个数字。
策略3 实例：如图2 中的C8 列，单元格
R
发给朋友
分享到朋友圈
回顶部