数独_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，分析你们的算法的复杂性。二，基本参考文献1,Mantere,Timo,andJanneKoljonen.Solving,ratingandgeneratingSudokupuzzleswithGA.InEvolutionaryComputation,2007.CEC2007.IEEECongresson,pp.1382-1389.IEEE,2007.2,ADifficultyMetricandPuzzleGeneratorforSudoku(MCM2008获奖论文1)3,EaseandToil:AnalyzingSudoku(MCM2008获奖论文2)二，基本参考文献4,张艳宗.数独的难度衡量,生成及微粒群算法.Master'sthesis,浙江大学,2009.注1：文献1有2006和2007两个版本注2：文献4提到了文献1和文献2三，数独难度衡量什么样的数独是困难的数独？或者说：用什么指标来衡量数独的难易程度？三，数独难度衡量直观感觉：1，越花时间，越困难。。。分析：时间怎么算出来呢？用什么算法来求解所花的时间呢？需要思考更多细节。。。。三，数独难度衡量2，空格越多越困难。。。不一定。。。。三，数独难度衡量事实上，一个全部为空的数独比部分为空的数独更难吗？例子：可以很容易就生成一个4阶的终盘数独，但是有限制条件则不一定。三，数独难度衡量3，求解策略越复杂，则越困难。简单排除法就比较容易，三，数独难度衡量行列排除法更难三，数独难度衡量文献1采用的衡量标准：用遗传算法求解数独所花的平均时间；文献2采用的衡量标准：用hsolve算法求解数独所花的平均时间；hsolve：模拟人类选手的求解技巧三，数独难度衡量文献3和文献4采用的衡量标准：“数独的备选总数越大，则越困难”我们将介绍这种方法三，数独难度衡量对于数独P，每一个空格X的备选数：C(X)=|X?|有k个空格的个数记为Ck(P)若某格有k个备选，赋以权重w(k)则总权重为\sumw(k)*Ck(P),归一化：\sumw(k)*Ck(P)/(w(9)*E(P))其中，E(P)为数独的总空格数w(k)=2^k三，数独难度衡量此标准的主要优点：1，数独不需要求解，即可算出其复杂度；2，计算速度很快此标准的主要缺点：举个例子，从算式来看，空数独的难度最大，但是空数独的难度真的最大吗？三，数独难度衡量另外，不管采用哪一种指标，不要忘记以实际的数独例子来拟合你的指标，以此说明你的指标的合理性（重要！），就像文献3中所做的那样。四，数独之遗传算法遗传算法的特征：1，问题解的编码：常用的是01编码，对于数独问题，建议用整数编码：每一个解编码为长度为81的向量，若分成九个部分，则每一个部分对应于数独的“宫”四，数独之遗传算法例：[892564731......785632149]四，数独之遗传算法2，生成个体的方法每一宫赋以一个1。。。9的排列，当然，我们不能改变预先给定位置的元素四，数独之遗传算法3,适应度函数（衡量解的好坏）每一宫的元素是齐全的，但是行和列不一定，行列缺的越多，则此解越差。方法1：四，数独之遗传算法方法2：四，数独之遗传算法方法3：（推荐！）四，数独之遗传算法也可以讲前面的几种方法组合起来：四，数独之遗传算法4，三要素之选择(choose)选择策略：(1)（轮盘赌选择）越好的解，其繁衍后代的概率越大(2)（随机选择）完全随机的选择两个配对(3)（顺序选择）按序号顺序配对(4)（精英选择）只有比较好的若干解有机会生成新的解（推荐！）(5)。。。。。。四，数独之遗传算法5，三要素之交叉(crossover)交叉策略：交换不同解的相同宫四，数独之遗传算法6，三要素之变异(mutate)在某一宫中作若干两两交换，当然，我们要避开给定的位置。四，数独之遗传算法7，加速技巧为加快收敛速度，扩大搜索范围，可用如下策略：四，数独之遗传算法文献1中介绍，此遗传算法收敛速度尚可，但经过我个人的编程实践，阶数较小的数独用回溯法比较快！五，数独之回溯法遗传算法等启发式算法都不能保证找到最优解，更多的时候是给出次优解或近似解，回溯法是精确算法，一定能找到最优解，但可能耗时很多，也可能耗时极多…五，数独之回溯法在问题解空间的结构未知的情况下，所有的精确算法都可算是穷举法或者有策略的穷举法例子：旅行商问题（TSP问题）简单穷举：n^n种可能性改进穷举：n!种可能性进一步改进：(n-1)!种可能性五，数独之回溯法回溯法的算法思想：“走不通，就调头”本质上是一种深度优先搜索。例子：八皇后问题五，数独之回溯法backtrack(TypeSol*sol,TypeProb*prob)：k=0;while(knumStep){if(getStep(k,step,sol,prob))doStep(k,step,sol,prob);else{undoStep(k-1,step,sol,prob);k=k-2;}k++;if(k0)break;}六，习题智慧金字塔游戏：六，习题问题：对于“智慧金字塔”平面游戏，请定义指标来衡量不同题目的困难程度，并设计一个出题系统，该系统可按照输入的难度级别（“简单级”“一般级”“困难级”和“专家级”四个层次）自动出题并给出答案。注：不要求游戏题目对应的解有唯一性！