关于数独问题的算法的设计与实现

1、本栏目责任编辑：谢媛媛开发研究与设计技术雷蕾，沈富可（华东师范大学计算机科学技术系，上海）关于数独问题的算法的设计与实现摘要：数独问题（）是十八世纪瑞士数学家欧拉提出的、近年来风靡全球的一种智力游戏。本文通过分析数据结构、函数、以及预处理算法和回溯算法，深入探讨了数独问题的解决方案，并给出了该方案的具体实现。“有限递推”关键词：；算法；回溯法中图分类号：文献标识码：文章编号：（），（，）：，：；引言是十八世纪瑞士数学家欧拉发明的。年“数独”游戏登上了的版面，很快，作为该泰晤士报月日，“数独”报每日内容的游戏就风靡了英美！规则很简单：有“数独”共个方格（即依次有个九宫格，详细图可参见第节内容），

2、在其中填入到的数字，让每个数字在每一行、每一列及每一个九宫格里都只出现一次。谜题中会预先填入若干数字，其它方格为空白，玩家得依谜题中的数字分布状况，逻辑推敲出剩下的空格里是什么数字。由于规则简单，在推敲之中完全不必用到数学计算，只需运用逻辑推理能力，所以无论男女老幼，人人都可以玩，而且容易上手、容易入迷。世界各地有很多数独俱乐部，还有的国家如法国等专门举行过数独比赛，其风靡程度可见一斑。本文就是试图通过计算机程序来快速破解数独难题。范围设计成而不是，是为了程序的易读性，使得数组元素的最大下标可达，下同。（）；该数组的用途是：若数组中某位置的数字不为，则数组相应位置的元素值记录为，否则记录为。即

3、数组是用来记录哪些位置的数字是已经确定下来的。（）；该数组的用途是记录所有未确定数字的所有可能性。可能性的记录方法是：数组各元素的值在初始化时被初始化为与其第二维的下标一致，即（其中是不会用到的）；中间计算过程中，若发现第一维某位置的某种可能性已不复存在，则将第一维下标是该位置而第二维下标是该不再可能的数字的元素值改为。程序架构设计程序可以考虑使用人工智能的算法。所谓人工智能的算法，应当是算法设计者对该游戏的特性有较深入了解，依据其内在联系设计出的和人类思维相似的解决算法。这似乎太过复杂。所以笔者准备主要采用回溯法解决这个问题。实践证明，回溯法解决数独问题，可以有着极快的效果（参见第节），没有

4、必要使用人工智能的算法。然而在采用回溯法之前，还可以利用一点小小的技巧以缩短回溯法的时间，甚至可将回溯法时间缩短为。这个小技巧可称为“有限递推”。下面先给出整个程序的简单框架，再分别介绍数据结构以及算法的详细内容。程序框架：（）；该数组的用途类似于栈，在核心回溯过程中起到至关重要的作用。回溯之前，要把所有数组中值为的位置依次存放进数组；回溯中，由低到高依次逐渐确定这些位置的数值，无法确定者（即的数字都不适合者）则应当回退到前一个位置，修改其假设值，以此类推，直至数组所存放的所有位置的值都能确定，或回退到最初点的前一个位置。三个重要函数下面介绍几个在预处理和回溯过程中会用到的“有限递推”三个重要

5、函数，以便在后面看代码的过程中更易理解。另外还有一些诸如题目合法性判断、行列九宫位置判断、打印、写文件等较易理解的函数就不再列出。（）（）；该函数是用来修订数组的。其具体功能是：对于数据结构与函数的介绍数据结构最主要的数据结构是个整型数组，其中个被设计成一维数组，还有个二维数组。数组中每一个值为的位置（即对于每一个没有确定下数字的位置），考察其可能的数字是哪些，记录下来（记录的方法参见节数组的介绍）。考察的方法是：在这些数字中除去当前行、列、九宫中已有的数字。（）；该数组的用途是接收题目以及保存最终结果。所有的个数字被依次存储在该数组中，空白处则初始化为。之所以把数组收稿日期：（）（）；该函数

6、是用来修订数组和数组的，其返回值表示了在此次运行该函数过程中是否执行了修订。其具体功能是：对作者简介：雷蕾（），男，安徽省芜湖市人，华东师范大学计算机科学技术系硕士研究生；沈富可（），男，山东高密人，华东师范大学网络中心主任，硕士生导师，主要从事计算机网络方向的研究工作。开发研究与设计技术于数组中每一个值为的位置（即对于每一个没有确定下数字的位置），考察其可能的数字的个数，若为，则将数组该位置的值改为且数组该位置的值改为该唯一可能的数字（即该位置的值已确定下来），且返回真；若没有只有一种可能性的位置，则返回假。（）（，）；该函数将来会在回溯的代码中看到，有必要简单介绍一下。其用途是：判断数组中

7、位置为的元素的值是否可能为，即判断的是：位置所在的行、列以及九宫中是否已经存在数字，若存在则返回真，否则返回假。“有限递推”预处理看到节介绍的前两个函数，我们就会很自然地想到：在执行一次函数之后，就可能会确定下一些原来没有确定的数字，那么此时，数组的值必然也会变动！因为确定下的数字越多，某些位置的可能数字的数目就会减少。那么就应当再执行函数修订数组，而修订之后可能又会出现一些只有一种可能性的位置，那么就应该再执行函数了于是，只要如此循环往复下去，就能最大限度地确定下由题目本身含义与规则而确定下的内容。确定的数字越多，对于将来回溯也就越有利。实践证明，有些数独题直接就可以通过执行大约多次的有限递

8、推循环体解决。那么，有限递推的循环什么时候结束呢？只有两种情况，一是推出了全部结果；二是函数返回值为假，即不存在只有一种可能性的位置。因为有了节的基础，有限递推的代码就很简洁了：（）（）（）；（！（）；（）若已经推出全部结果；返回为假时也可能是推出了所有结果（）（）；打印结果回溯算法回溯法的基本思想在节介绍数组的时候已有初步的阐述，下面给出详细的步骤与代码。（）按下标的由低到高扫描数组，将值为的位置记录进数组，记录的顺序也是由低到高。最后，整型量记录下：数组中为位置的个数再加。（）整型量初始化为，即把看作栈（虽然数组的内容永远不会变，但的增减仍代表了进栈和出栈的操作），记录的是栈顶。（）型变量

9、初始化为。下面各步骤都将在一个条件始终为真的死循环中进行，该循环由一条对进行真假判断的语句分成两大部分。所代表的意义是：若当前栈顶（）是经过了回退操作而达到的，则会已被记录为假；否则为真。死循环结束的条件是与的值相等，即解出最终结果，或者是无解，最终小于（无解的情况基本上在最初做题目的合法性检查时已经排除了）。在死循环中：若为真，进入步骤（），否则进入步骤（）。（）为真，说明栈顶（）是经过正常的假设而达到的，并非由回退达到，那么：根据数组以及函数（参见节），对栈顶所保存位置的可能出现的数字进行判断，把遇到的第电脑知识与技术本栏目责任编辑：谢媛媛一个可能数字设置进数组，并把数组的该位置的值设为，

10、并判断是否已经解出结果，即和相等否，若相等，则打印结果并退出死循环；若发现都不可能应用在栈顶所保存的位置，则说明前面的假设有错误，此时应当回退，即：数组和数组的该位置重设为，减，并将置为假。本轮循环体结束，继续下一轮的循环。（）为假，说明是经过了回退才达到现在这个栈顶的，那么：若仍然没有可能的数字可以应用在当前栈顶所保存的位置上，那么继续执行出栈操作，即：数组和数组的该位置重设为，减；否则将遇到的第一个可能数字应用到该位置，即：再设好数组和数组，将加，并将置为真。本轮循环体结束，继续下一轮的循环。下面给出回溯法的完整源程序：（）（）；预处理以提高速度（）；将所有为的位置入栈（；）（）；记录最大

11、数目加；指向栈顶；该标志位说明了当前栈顶是正常进入的，还是经过了回退才达到的（）（）；（）；（；）（！（，）若所标示的位置上，可以安插这个值，则；（）（）；（）该节点所有可能值都不可以，则回退；（）说明当前这个也没有更换可能节点的能力了，还要继续回退；（下转第页）本栏目责任编辑：李桂瑾品购买者的概率。人工智能及识别技术（）变异：采用了一种基于位置的变异算子，即随机选取染色体上的两基因，然后将两个基因互换。如：父代变异后得到子代。（）译码输出：将二进制串转换成对应的用户兴趣模式。（）选择第一次选用轮盘赌选择算子，后根据适应度大小保留最优个体。（）交叉选用随机单点交叉算子。如：父代：、父代结束语本

12、文所设计的基于遗传算法的智能模糊检索系统，目的在于建立一个基于用户兴趣的智能的个性化信息检索系统。其中包括了两个子部分：用户群模式挖掘部分及用户兴趣模式挖掘部分。用户兴趣模式挖掘部分能使系统在用户购买兴趣不明确或兴趣变化较大时亦能推荐比较适合用户购买的商品，便于用户选购决策，也增加了用户的购买机率。基于遗传算法的用户群模式的发现能有助于有关部门营销策略的制定，遗传算法得到的较优解产生于某一代的种群中，这样就可以根据种群中不同个体适应度之间的差异，对拥有不同购买概率的用户采取不同的营销策略。如可对购买概率高于的用户邮寄商品广告、发送生日贺卡、发放小礼品等，而对其他的用户则通过正常的宣传渠道来进行

13、营销宣传。：。交叉后生成新一代。子代：、子代：。（）变异选用随机变异算子。如：父代：变异后生成子代。（）译码输出将二进制串转换成对应的用户群模式。基于遗传算法的用户兴趣模式的发现该部分同样以基本遗传算法来实现，前四步和中挖掘用户群模式所用操作方法一样。（）初始化（略）；（）编码（略）；（）判断适应度值是否满足条件（略）；（）选择：（略）；（）交叉。该步骤分二步。第一步：随机在父代中选择一个交配区域。如：父代参考文献：应用与软件实现西安：王小平，曹立明遗传算法理论、西安交通大学出版社，周柏翔，冯宝剑，高蔚应用遗传算法解决数据挖掘问题的实例分析情报科学，（）：许欢庆，王永成，孙强基于遗传算法的定题

14、信息搜索策略中文信息学报，（）：徐斌，等基于遗传算法的信息检索技术计算机工程，（）：王礼刚，等一种基于改进型遗传算法的关联规则提取算法及其应用重庆师范大学学报（自然科学版），（）：例是执行循环体次就可以得出答案的数独“有限递推”题；例是通过只能确定个数字的数独题，难度较“有限递推”大；例是一道法国数独决赛的题目，通过可以确定“有限递推”下个数字。下面是对以上题各做了次的计算后，对解答时间的测试结果，测试环境是为奔腾的机器：，选交叉；父代，选交叉。第二步：父代的交配区域加到父代的前面，删除父代的交配区域；将父代的交配区域加到父代的前面，删除父代子代的交配区域，得到子代、。（上接第页）（，）；（）；（）当前节点没有更换的可能性了，继续回退；重新设定从上面的测试结果可以清楚地看出：（）本实现对数独问题最多也是