数独中的数学模型.doc

《数独中的数学模型.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数独中的数学模型摘要现如今数独游戏风靡全球，深受人们喜爱。其难度等级多样，求解数独难度等级较高的常常需要花费大量的时间和精力，因此我们试图用计算机来解决这一问题。在问题一中，我们主要考虑空格数的多少以及空格自由度与数独难度等级的关系。由一定的案例分析得出数独题目的难度等级与空格数存在正比关系，接着我们考虑如果只是简单的按照空格的数目多少来划分数独题目的难易程度是不全面的，因此继续分析，得出空格自由度与数独的难度等级存在正比的关系，最后又以空格数和空格自由度综合分析进行验证，得出此数独等级为3级。[1]空格自由度法模型如下：在问题二中，我们运用穷举法分析大量可能情

2、况，再用MATLAB编写程序得出此数独游戏的终盘。在问题三中，我们运用了比较排除法、唯一解法和综合法来求解此数独游戏，最终选用综合法作为较优方法。[1]在问题四中，我们用循环回溯法进行求解，使用MATLAB编写程序得出结果（见表8）。[1]关键字：穷举法比较排除法唯一解法循环回溯法数独空格数空格自由度一、问题背景数独是一种数字解谜游戏，英文名叫Sudoku，前身为“九宫格”，当时的算法比现在的更为复杂，要求纵向、横向、斜向上的三数之和等于15，而不只是数字的不能重复，儒家典籍《易经》中的“九宫图”也是来源于此。关于它的起源一直存有争议，有人认为最早起源于中国，也

3、有人认为起源于瑞士。1970年由美国一家数学逻辑游戏杂志首先发表，名为Number。后在日本流行，于1984年把Sudoku取名为数独。数独全面考验做题者观察能力和逻辑推理能力，它的玩法逻辑简单，除了1到9的阿拉伯数字以外，不必用到任何东西，但数字的排列方式却又千变万化，不少教育者认为，数独是锻炼大脑的绝佳方式。它不仅具有很强的趣味性，也是一种对智慧和毅力的考验。二、问题重述芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。所给数独游戏表格如下：　　据介绍，目前，

4、数独游戏难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所有数独游戏中，难度最高的等级。数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。由此我们要解决以下问题：问题一：分析此数独的难度；问题二：用穷举算法求解数独；问题三：设计此数独求解的较优的算法；问题四：建立数独求解模型并给出此数独的答案。三、问题分析根据题中所给信息我们知道数独是一

5、种数字解谜游戏，要求游戏者有很好的观察能力和逻辑推理能力。针对问题一：分析此数独难度，我们认为有两点因素：一、空格数的多少，二、空间自由度。因此我们采取例证法进行分析，根据空格数来划分等级，进行一定的数据分析求出空格率，进而得出难度系数与空格数的关系。数独的难度等级与行、列、宫格内的空格数存在着密切联系，所以数独难易程度还与空间自由度有关。数独的空格自由度，指除掉空格本身，空格所在行、列、九宫内的空格数总和。除此之外我们可以以玩家完成数独题目的时间来判定数独题目的难度。针对问题二：“穷举法”是指当一个问题有几种可能而一时难以判定时,把几种可能一一列举出来,然后逐

6、一尝试，直到尝试结果与给定的条件和结论相符为止。这种方法一般在计算机中运用，因为计算机计算速度快，可以很快验证答案是否正确，所以我们就以此来分析所有可能情况得出最终结果。针对问题三：为了找出更好的数独解法，我们运用了三种方法来求解。分别是：比较排除法、唯一解法和综合法。分析比较，选出较优方案。针对问题四：我们选用循环回溯法进行分析求解，与问题三中所求结果对比，以此验证其准确性。四、模型假设1、假设每种数独游戏都存在一定的联系且相互之间的难易程度成一定的比例；2、假设实验者水平相同，随着实验不断进行，完成数独题目熟练程度不会增加；3、假设实验者数独时间与数独题目难

7、度无关。五、符号说明N数独的空格数目F所有空格的自由度的总和S(i,j)数独矩阵A(9*9)中i行j列的空格自由度S(i)i行的空格数目S(j)j行的空格数目gi除去同行同列的同一宫中的空格数六、模型建立与求解6．1问题一的求解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.

8、2实例分析以《数独》为例