第37卷第3期计算机科学Vol.37No.32010年3月ComputerScienceMar2010基于遗传算法求解数独难题刘延风刘三阳(西安电子科技大学应用数学系西安710071)摘要为了求解数独难题,首先将其转化成一个组合优化问题。然后,提出一个在编码、初始化、交叉、变异、局部搜索等方面具有特点的遗传算法来求解它。实验结果表明,对于所有难度等级的数独难题,算法都是有效的。关键词遗传算法,数独难题,局部搜索中图法分类号TP181文献标识码AAlgorithmBasedonGeneticAlgorithmforSudokuPuzzlesLIUYan-fengLIUSan-yang(DepartmentofAppliedMathematics,XidianUniversity,Xi.an710071,China)AbstractTosolvetheSudokupuzzles,aboveall,theywerechangedintoacombinatorialoptimizationproblem.Then,ageneticalgorithmwithspecializedencoding,initializationandlocalsearchoperatorwaspresentedtooptimizeit.Theex-perimentalresultsshowthealgorithmiseffectiveforalldifficultylevelsSudokupuzzles.KeywordsGeneticalgorithm,Sudokupuzzle,Localsearch遗传算法是一种基于种群的随机优化算法,自从提出以1引言来在很多应用方面取得了极大的成功。基于遗传算法求解数数独名称来源于日语Sudoku,可以理解为/独立的数独问题的难点在于必须搜索到数独的解(即最优解),而找到字0。数独是一个很容易使人着迷的难题,在世界各地以及互次优解是没有任何意义的。这就对算法性能提出了很高的要联网上都十分流行。它的规则十分简单,在9@9的空格里填求。为了求解数独难题,作者在编码、初始化种群等方面做了入合适的数字,使得每行(从左到右)、每列(从上到下)以及每一些改进。另外,考虑到虽然遗传算法全局搜索能力比较强,个小方块都要包含从1到9的数字。通常,有些格子里的数但是局部搜索能力弱,为了取长补短,定义并添加了局部搜字事先给定。图1就是一个数独和它的解。由于数独和有些索。从实验结果来看,提出的算法对于所有难度等级的问题调度问题非常类似,例如课表编排问题,因此求解数独不能完都是有效的。全等同于玩游戏。2问题的转化数独可以看作一个组合优化问题:将每一个小方块中未出现的数字不重复地填入其空格里,目标函数是使得满足要求的行或列的数目之和最大化。显然,最优解对应的目标函数值为18,它就是数独的解。将每一个小方块中未出现的数字任意不重复地填入其空格内,就是一个可行解。图1一个数独及其解3求解数独的局部搜索遗传算法数独看起来是一个基于逻辑推理的问题,很自然的解法3.1编码是采用基于回溯的蛮力搜索方法[1]。目前网上的许多求解器采用符号编码,按照小方块的排列顺序(先行后列、从左都是采用这种方法。但是,由于数独是一个NP难问题[2],这到右),对每一个小方块未出现的数字进行编码,然后将各自意味着利用上述方法求解很多数独问题是不现实的。文献的编码拼接而成染色体。例如,图1中第一个小方块中未出[3]提出利用现代优化算法求解数独问题,并提出了一种基于现的数字为1,2,5,7,8;第二个小方块中未出现的数字为3,模拟退火的求解方法。文献[4]提出了一种基于遗传算法的4,6,8,等等。图1数独的某个可行解编码如下所示(阴影部求解算法。该算法只是简单地应用遗传算法,加之没有局部分表示处于同一个小方块中未出现的数字)。搜索,因此效果并不理想,对于难度适中乃至困难的数独,100次独立运行中能够成功的次数不超过10次。到稿日期:2009-04-24返修日期:2009-07-14刘延风(1970-),男,讲师,主要研究方向为智能优化算法及其应用,E-mail:teacher2003@tom.com;刘三阳(1959-),男,教授,主要研究方向为最优化理论与算法。#225#块对应的染色体):由于舍弃掉了那些已经出现的数字,和文献[4]的编码相比,编码长度变小了,提高了编码效率。3.2初始化染色体种群最简单的方法是随机生成每一个小方块中未出现数字的排列,然后将其按照小方块的排列顺序拼接成一个染色体。但是,这样生成的初始种群质量很差(很多个体满