数独_2013年暑期建模

1、数独算法简介目录v一， 数独介绍v二， 基本参考文献v三， 数独难度衡量v四， 数独之遗传算法v五， 数独之回溯法v六， 习题一， 数独介绍一， 数独介绍一， 数独介绍v数独(sudoku)，起源于瑞士，于1970 年代由美国的一家数学逻辑游戏杂志首先发表，当时名为Number Place。及后在日本大力推广下得以发扬光大，于1984 年取名“数独”，即“独立的数字”的省略说法。v“中国大陆是在2007年2月28日正式引入数独。成为世界谜题联合会的39个成员之一。” （维基百科）一， 数独介绍v游戏规则：v以经典的9X9数独为例：v要求：每行、每列和每个宫（即3x3的大格）均出现1至9中的所有

2、数字。v“规则简单，老少皆宜！”一， 数独介绍v(MCM 2008B)v Develop an algorithm to construct Sudoku puzzles of varying difficulty. Develop metrics to define a difficulty level. The algorithm and metrics should be extensible to a varying number of difficulty levels. You should illustrate the algorithm with at least 4 diff

3、iculty levels. Your algorithm should guarantee a unique solution. Analyze the complexity of your algorithm. Your objective should be to minimize the complexity of the algorithm and meet the above requirements.一， 数独介绍翻译要点： 1，设计数独游戏的生成算法。定义合适的测度来衡量数独的难度级别。 2，至少要对4个难度级别来说明该算法。 3，算法应该保证有唯一解。 4，分析你们的算法的复

4、杂性。二， 基本参考文献1, Mantere, Timo, and Janne Koljonen. Solving, rating and generating Sudoku puzzles with GA. In Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, pp. 1382-1389. IEEE, 2007.2,A Difficulty Metric and Puzzle Generator forSudoku (MCM2008获奖论文1)3,Ease and Toil: Analyzing Sudoku(MCM20

5、08获奖论文2)二， 基本参考文献v4, 张艳宗. 数独的难度衡量, 生成及微粒群算法. Masters thesis, 浙江大学, 2009.v注1：文献1有2006和2007两个版本v注2：文献4 提到了文献1和文献2三， 数独难度衡量v什么样的数独是困难的数独？v或者说：用什么指标来衡量数独的难易程度？三， 数独难度衡量v直观感觉：v1，越花时间，越困难。v分析：时间怎么算出来呢？v用什么算法来求解所花的时间呢？v需要思考更多细节。三， 数独难度衡量v2，空格越多越困难。v不一定。三， 数独难度衡量v事实上，一个全部为空的数独比部分为空的数独更难吗？v例子：可以很容易就生成一个4阶的终盘

6、数独，v但是有限制条件则不一定。三， 数独难度衡量v3，求解策略越复杂，则越困难。v简单排除法就比较容易，三， 数独难度衡量v行列排除法更难三， 数独难度衡量v文献1采用的衡量标准：v用遗传算法求解数独所花的平均时间；v文献2采用的衡量标准：v用 hsolve 算法求解数独所花的平均时间；vhsolve：模拟人类选手的求解技巧三， 数独难度衡量v文献3和文献4采用的衡量标准：v“数独的备选总数越大，则越困难”v我们将介绍这种方法三， 数独难度衡量v对于数独P，每一个空格X的备选数： C(X)=|X?|v有k个空格的个数记为 Ck(P)v若某格有k个备选，赋以权重w(k)则总权重为 sum w(

7、k)*Ck(P),归一化： sum w(k)*Ck(P)/( w(9)*E(P) )其中，E(P)为数独的总空格数w(k)=2k三， 数独难度衡量v此标准的主要优点：v1，数独不需要求解，即可算出其复杂度；v2，计算速度很快v此标准的主要缺点：v举个例子，从算式来看，空数独的难度最大，v但是空数独的难度真的最大吗？三， 数独难度衡量v另外，不管采用哪一种指标，v不要忘记以实际的数独例子来拟合你的指标，v以此说明你的指标的合理性（重要！），v就像文献3中所做的那样。四， 数独之遗传算法v遗传算法的特征：v1，问题解的编码：v常用的是01编码，v对于数独问题，建议用整数编码：每一个解编码为长度为8

8、1的向量，若分成九个部分，则每一个部分对应于数独的“宫”四， 数独之遗传算法v例：v8 9 2 5 6 4 7 3 1. 7 8 5 6 3 2 1 4 9四， 数独之遗传算法v2，生成个体的方法每一宫赋以一个1。9的排列，当然，我们不能改变预先给定位置的元素四， 数独之遗传算法v3,适应度函数（衡量解的好坏）每一宫的元素是齐全的，但是行和列不一定，行列缺的越多，则此解越差。方法1：四， 数独之遗传算法v方法2：四， 数独之遗传算法v方法3：（推荐！）四， 数独之遗传算法v也可以讲前面的几种方法组合起来：四， 数独之遗传算法v4，三要素之选择(choose)v选择策略：v(1) （轮盘赌选择）

9、越好的解，其繁衍后代的概率越大v(2)（随机选择）完全随机的选择两个配对v(3)（顺序选择）按序号顺序配对v(4)（精英选择）只有比较好的若干解有机会生成新的解（推荐！）v(5)。四， 数独之遗传算法v5，三要素之交叉(crossover)v交叉策略：交换不同解的相同宫四， 数独之遗传算法v6，三要素之变异(mutate)v在某一宫中作若干两两交换，v当然，我们要避开给定的位置。四， 数独之遗传算法v7，加速技巧v为加快收敛速度，扩大搜索范围，可用如下策略：四， 数独之遗传算法v文献1中介绍，此遗传算法收敛速度尚可，v但经过我个人的编程实践，v阶数较小的数独用回溯法比较快！五， 数独之回溯法v

10、遗传算法等启发式算法都不能保证找到最优解，v更多的时候是给出次优解或近似解，v回溯法是精确算法，一定能找到最优解，v但可能耗时很多，v也可能耗时极多五， 数独之回溯法v在问题解空间的结构未知的情况下，v所有的精确算法都可算是穷举法或者有策略的穷举法例子：旅行商问题（TSP问题）简单穷举： nn 种可能性改进穷举：n! 种可能性进一步改进：(n-1)! 种可能性五， 数独之回溯法v回溯法的算法思想：“走不通，就调头”v本质上是一种深度优先搜索。例子：八皇后问题五， 数独之回溯法v backtrack(TypeSol *sol,TypeProb *prob)：v k=0;v while( knumStep )v v if( getStep(k, step, sol, prob) )v doStep(k, step, sol, prob);v elsev v undoStep(k-1, step, sol, prob);v k