数独-2013年暑期建模课件

数独算法简介目录一，数独介绍二，基本参考文献三，数独难度衡量四，数独之遗传算法五，数独之回溯法六，习题一，数独介绍一，数独介绍数独(sudoku)，起源于瑞士，于1970年代由美国的一家数学逻辑游戏杂志首先发表，当时名为NumberPlace。及后在日本大力推广下得以发扬光大，于1984年取名“数独”，即“独立的数字”的省略说法。“中国大陆是在2007年2月28日正式引入数独。。。成为世界谜题联合会的39个成员之一。”（维基百科）一，数独介绍游戏规则：以经典的9X9数独为例：要求：每行、每列和每个宫（即3x3的大格）均出现1至9中的所有数字。“规则简单，老少皆宜！”一，数独介绍(MCM2008B)DevelopanalgorithmtoconstructSudokupuzzlesofvaryingdifficulty.Developmetricstodefineadifficultylevel.Thealgorithmandmetricsshouldbeextensibletoavaryingnumberofdifficultylevels.Youshouldillustratethealgorithmwithatleast4difficultylevels.Youralgorithmshouldguaranteeauniquesolution.Analyzethecomplexityofyouralgorithm.Yourobjectiveshouldbetominimizethecomplexityofthealgorithmandmeettheaboverequirements.一，数独介绍翻译要点：1，设计数独游戏的生成算法。定义合适的测度来衡量数独的难度级别。2，至少要对4个难度级别来说明该算法。3，算法应该保证有唯一解。4，分析你们的算法的复杂性。二，基本参考文献4,张艳宗."数独的难度衡量,生成及微粒群算法."Master'sthesis,浙江大学,2009.注1：文献1有2006和2007两个版本注2：文献4提到了文献1和文献2三，数独难度衡量直观感觉：1，越花时间，越困难。。。分析：时间怎么算出来呢？用什么算法来求解所花的时间呢？需要思考更多细节。。。。三，数独难度衡量事实上，一个全部为空的数独比部分为空的数独更难吗？例子：可以很容易就生成一个4阶的终盘数独，但是有限制条件则不一定。三，数独难度衡量3，求解策略越复杂，则越困难。简单排除法就比较容易，三，数独难度衡量行列排除法更难三，数独难度衡量文献1采用的衡量标准：用遗传算法求解数独所花的平均时间；文献2采用的衡量标准：用hsolve算法求解数独所花的平均时间；hsolve：模拟人类选手的求解技巧三，数独难度衡量文献3和文献4采用的衡量标准：“数独的备选总数越大，则越困难”我们将介绍这种方法三，数独难度衡量此标准的主要优点：1，数独不需要求解，即可算出其复杂度；2，计算速度很快此标准的主要缺点：举个例子，从算式来看，空数独的难度最大，但是空数独的难度真的最大吗？三，数独难度衡量另外，不管采用哪一种指标，不要忘记以实际的数独例子来拟合你的指标，以此说明你的指标的合理性（重要！），就像文献3中所做的那样。四，数独之遗传算法例：[892564731......785632149]四，数独之遗传算法2，生成个体的方法每一宫赋以一个1。。。9的排列，当然，我们不能改变预先给定位置的元素四，数独之遗传算法方法2：四，数独之遗传算法方法3：（推荐！）四，数独之遗传算法也可以讲前面的几种方法组合起来：四，数独之遗传算法5，三要素之交叉(crossover)交叉策略：交换不同解的相同宫四，数独之遗传算法6，三要素之变异(mutate)在某一宫中作若干两两交换，当然，我们要避开给定的位置。四，数独之遗传算法7，加速技巧为加快收敛速度，扩大搜索范围，可用如下策略：四，数独之遗传算法文献1中介绍，此遗传算法收敛速度尚可，但经过我个人的编程实践，阶数较小的数独用回溯法比较快！五，数独之回溯法遗传算法等启发式算法都不能保证找到最优解，更多的时候是给出次优解或近似解，回溯法是精确算法，一定能找到最优解，但可能耗时很多，也可能耗时极多…五，数独之回溯法在问题解空间的结构未知的情况下，所有的精确算法都可算是穷举法或者有策略的穷举法例子：旅行商问题（TSP问题）简单穷举：n^n种可能性改进穷举：n!种可能性进一步改进：(n-1)!种可能性五，数独之回溯法回溯法的算法思想：“走不通，就调头”本质上是一种深度优先搜索。例子：八皇后问题五，数独之回溯法backtrack(TypeSol*sol,TypeProb*prob)：k=0;while(k<numStep){if(getStep(k,step,sol,prob))doStep(k,step,sol,prob);else{undoStep(k-1,step,sol,prob);k=k-2;}k++;if(k<0)break;}六，习题智慧金字塔