《数独中的数学模型》由会员分享，可在线阅读，更多相关《数独中的数学模型（25页珍藏版）》请在金锄头文库上搜索。
1、数独中的数学模型摘要现如今数独游戏风靡全球，深受人们喜爱。其难度等级多样，求解数独难度等级较高的常常需要花费大量的时间和精力，因此我们试图用计算机来解决这一问题。在问题一中，我们主要考虑空格数的多少以及空格自由度与数独难度等级的关系。由一定的案例分析得出数独题目的难度等级与空格数存在正比关系，接着我们考虑如果只是简单的按照空格的数目多少来划分数独题目的难易程度是不全面的，因此继续分析，得出空格自由度与数独的难度等级存在正比的关系，最后又以空格数和空格自由度综合分析进行验证，得出此数独等级为3级。1 空格自由度法模型如下： 在问题二中，我们运用穷举法分析大量可能情况，再用MATLAB编写程序得出
2、此数独游戏的终盘。在问题三中，我们运用了比较排除法、唯一解法和综合法来求解此数独游戏，最终选用综合法作为较优方法。1 在问题四中，我们用循环回溯法进行求解，使用MATLAB编写程序得出结果（见表8）。1 关键字：穷举法 比较排除法 唯一解法 循环回溯法 数独 空格数 空格自由度一、问题背景 数独是一种数字解谜游戏，英文名叫Sudoku，前身为“九宫格”，当时的算法比现在的更为复杂，要求纵向、横向、斜向上的三数之和等于15，而不只是数字的不能重复，儒家典籍易经中的“九宫图”也是来源于此。关于它的起源一直存有争议，有人认为最早起源于中国，也有人认为起源于瑞士。1970年由美国一家数学逻辑游戏杂志首
3、先发表，名为Number。后在日本流行，于1984年把Sudoku取名为数独。数独全面考验做题者观察能力和逻辑推理能力，它的玩法逻辑简单，除了1到9的阿拉伯数字以外，不必用到任何东西，但数字的排列方式却又千变万化，不少教育者认为，数独是锻炼大脑的绝佳方式。它不仅具有很强的趣味性，也是一种对智慧和毅力的考验。二、问题重述 芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个 “数独之谜”。所给数独游戏表格如下： 据介绍，目前，数独游戏难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独
4、游戏难度等级是十一，可以说是所有数独游戏中，难度最高的等级。数独是根据99盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。由此我们要解决以下问题：问题一： 分析此数独的难度；问题二： 用穷举算法求解数独；问题三： 设计此数独求解的较优的算法；问题四： 建立数独求解模型并给出此数独的答案。三、问题分析根据题中所给信息我们知道数独是一种数字解谜游戏，要求游戏者有很好的观察能力和逻辑推理能力。针对问题一：分析此数独难度，我们认为有两点因素：一、空
5、格数的多少，二、空间自由度。因此我们采取例证法进行分析，根据空格数来划分等级，进行一定的数据分析求出空格率，进而得出难度系数与空格数的关系。数独的难度等级与行、列、宫格内的空格数存在着密切联系，所以数独难易程度还与空间自由度有关。数独的空格自由度，指除掉空格本身，空格所在行、列、九宫内的空格数总和。除此之外我们可以以玩家完成数独题目的时间来判定数独题目的难度。针对问题二： “穷举法”是指当一个问题有几种可能而一时难以判定时,把几种可能一一列举出来,然后逐一尝试，直到尝试结果与给定的条件和结论相符为止。这种方法一般在计算机中运用，因为计算机计算速度快，可以很快验证答案是否正确，所以我们就以此来分
6、析所有可能情况得出最终结果。针对问题三：为了找出更好的数独解法，我们运用了三种方法来求解。分别是：比较排除法、唯一解法和综合法。分析比较，选出较优方案。针对问题四：我们选用循环回溯法进行分析求解，与问题三中所求结果对比，以此验证其准确性。四、模型假设1、假设每种数独游戏都存在一定的联系且相互之间的难易程度成一定的比例；2、假设实验者水平相同，随着实验不断进行，完成数独题目熟练程度不会增加； 3、假设实验者数独时间与数独题目难度无关。五、符号说明N数独的空格数目F所有空格的自由度的总和S(i,j)数独矩阵A(9*9)中i行j列的空格自由度S(i)i行的空格数目S(j)j行的空格数目gi除去同行同
7、列的同一宫中的空格数六、模型建立与求解61问题一的求解6.1.1空格数与难度等级6.1.1.1难度等级划分为了更好的区分难易程度我们将数独以空格数划分为五个等级，具体划分如下：空格数的取值范围为0-81，以空格数来平均划分难度等级，将空格数平均分成5个类型，空格数的取值范围缩小到37-81。划分等级如下表所示：37-4546-5455-6364-7273-811级2级3级4级5级6.1.1.2实例分析以数独为例，我们得到一些数据。数独题目数为100道，表格行表示空格的个数，列表示难度的级别，一星为最容易，二星为容易，三星为难，四星为最难。例如：表一的首格3表示，难度为一星，空格数为50的题目有
8、3道。表1 统计数独空格数与难度 50 51 52 53 56 57 58 总数 一星 3 1 4 二星 1 1 21 1 1 25 三星 35 11 46 四星 14 8 325 经过多次试验与分析，我们初步得到，随着空格数的增加，数独的难度系数也相应的增加。为进一步探讨数独的难易程度是否还与其他因素有关，我们对数独题目的统计表格进行处理，在同等难度上，将每种空格的题目个数除以该难度的总题目数，得到如下表格。表2 计算数独空格率与难度 50 51 52 53 56 57 58 一星 0.75 0.25 二星 0.04 0.04 0.84 0.04 0.04 三星 0.76 0.24 四星 0
9、.56 0.32 0.12 表格的数据用图表表示（图1），由图可以清晰看出，难度等级递增，空格数也不断增加。难度等级与空格数存在正比的关系。图1 数独空格数与难度 经过我们的多次试验与分析，我们初步得到，随着空格数的增加，数独的难度系数也相应的增加，当然数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体趋势递增，不同难度等级的题目空格数也一样的情况。6.1.2空格自由度与难度等级6.1.2.1数独难度的进一步分析数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体趋势递增，不同难度等级的题目空格数也一样的情况。我们得出初步结论，简单按照空格的数目多少来划分数独题目
10、的难易程度是不全面的。同样空格数的数独题目，空格数分布位置的不同对难度等级也造成影响。注:格数是决定难度等级的因素，但不是唯一的因素。表3 统计数独-再露锋芒空格数与难度 45 47 49 51 52 53 54 55 56 57 总数 一星 3 1 1 1 1 2 1 10 二星 1 2 9 3 2 1 18 三星 2 1 22 8 5 2 40 四星 1 4 1 1 1 6 15 五星 1 3 6 10 6.1.2.2空格自由度的计算计算空格自由度的模型如下：6.1.2.3空格自由度模型空格自由度的取值范围大，当数独题目全为0时，空格的数为 81，空间自由度为2106；数独题目只剩1个空格
11、时，空格自由度为0。在0,2106的范围内平均划分，将难度级别划分为5个等级，空格自由度0-420难度等级为1；421-841为2；842-1262为3；1263-1683为4；1683-2106为5。这与实际题目的难度划分不一致。空格自由度划分的区间缩小到700，1300，700，820为1级，820，940为2级，940，1060为3级，1060，1180为4级，1080，1300为5级（图2）。图2 空格自由度难度模型6.1.2.4空格自由度模型合理性验证随机抽取数独书籍不同难度等级的题目，进行空格自由度的计算，验证空格自由度衡量数独题目的难度是否合理，首先抽取4道不同难度的数独题目，将
12、题目转换为字符串，计算空格自由度，实验结果如下：表4 实验数据 数独题目空格自由度难度书难度10008400910017006000700000504601802007002960030000709600406070006050080202000100008202220000000230300500400000037000003026500500400720076000000085009605401802009000600018803230060090000318000097000000560804000002000100070000080403600000029000053100002005
13、001008434600000004050009800000003570003060280802094000000000000080042000001000020500010008105444由实验结果看出空格自由度与数独的难度等级存在正比的关系，难度系数的划分合理，与书中的划分基本一致。6.1.3难度等级综合模型6.1.3.1难度等级综合模型的建立数独题目的难度等级由空格数与空格自由度综合决定，建立几何难度等级模型：（1）以数独的空格数来划分，将空格数为横坐标X；（2）将空格自由度的总和划分等级，将等级数设为纵坐标Y；（3）根据（X，Y）判定难度。将计算好的空格数和空格自由度划分等级，两者结合，便可得到数独题目的难度等级了。难度等级等级为A-I，A为最易，I为最难，随着字母变大，难度逐次增加。具体划分的数据如下：
