数独2013年暑期建模PPT.ppt

数独算法简介 目录 一， 数独介绍 二， 基本参考文献 三， 数独难度衡量 四， 数独之遗传算法 五， 数独之回溯法 六， 习题 一， 数独介绍 一， 数独介绍 一， 数独介绍 数独(sudoku)，起源于瑞士，于1970 年代由美国的一家数学逻辑游戏杂志首先发表，当时名为Number Place。及后在日本大力推广下得以发扬光大，于1984 年取名“数独”，即“独立的数字”的省略说法。 “中国大陆是在2007年2月28日正式引入数独。。。成为世界谜题联合会的39个成员之一。” （维基百科） 一， 数独介绍 (MCM 2008B) 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 difficulty 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，分析你们的算法的复杂性。 二， 基本参考文献 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 for Sudoku (MCM2008获奖论文1) 3,Ease and Toil: Analyzing Sudoku (MCM2008获奖论文2) 二， 基本参考文献 4, 张艳宗. 数独的难度衡量, 生成及微粒群算法. Masters thesis, 浙江大学, 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) 则总权重为 \sum w(k)*Ck(P), 归一化： \sum w(k)*Ck(P)/( w(9)*E(P) ) 其中，E(P)为数独的总空格数 w(k)=2^k 三， 数独难度衡量 此标准的主要优点： 1，数独不需要求解，即可算出其复杂度； 2，计算速度很