数独中的数学模型

数独中的数学模型摘要现如今数独游戏风靡全球，深受人们喜爱。其难度等级多样，求解数独难度等级较高的常常需要花费大量的时间和精力，因此我们试图用计算机来解决这一问题。在问题一中，我们主要考虑空格数的多少以及空格自由度与数独难度等级的关系。由一定的案例分析得出数独题目的难度等级与空格数存在正比关系，接着我们考虑如果只是简单的按照空格的数目多少来划分数独题目的难易程度是不全面的，因此继续分析，得出空格自由度与数独的难度等级存在正比的关系，最后又以空格数和空格自由度综合分析进行验证，得出此数独等级为3级。[1]空格自由度法模型如下：(,)()()iSijSiSjg(,)[()()]ijFSijSiSjg在问题二中，我们运用穷举法分析大量可能情况，再用MATLAB编写程序得出此数独游戏的终盘。在问题三中，我们运用了比较排除法、唯一解法和综合法来求解此数独游戏，最终选用综合法作为较优方法。[1]在问题四中，我们用循环回溯法进行求解，使用MATLAB编写程序得出结果（见表8）。[1]关键字：穷举法比较排除法唯一解法循环回溯法数独空格数空格自由度一、问题背景数独是一种数字解谜游戏，英文名叫Sudoku，前身为“九宫格”，当时的算法比现在的更为复杂，要求纵向、横向、斜向上的三数之和等于15，而不只是数字的不能重复，儒家典籍《易经》中的“九宫图”也是来源于此。关于它的起源一直存有争议，有人认为最早起源于中国，也有人认为起源于瑞士。1970年由美国一家数学逻辑游戏杂志首先发表，名为Number。后在日本流行，于1984年把Sudoku取名为数独。数独全面考验做题者观察能力和逻辑推理能力，它的玩法逻辑简单，除了1到9的阿拉伯数字以外，不必用到任何东西，但数字的排列方式却又千变万化，不少教育者认为，数独是锻炼大脑的绝佳方式。它不仅具有很强的趣味性，也是一种对智慧和毅力的考验。二、问题重述芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。所给数独游戏表格如下：据介绍，目前，数独游戏难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所有数独游戏中，难度最高的等级。数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。由此我们要解决以下问题：问题一：分析此数独的难度；问题二：用穷举算法求解数独；问题三：设计此数独求解的较优的算法；问题四：建立数独求解模型并给出此数独的答案。三、问题分析根据题中所给信息我们知道数独是一种数字解谜游戏，要求游戏者有很好的观察能力和逻辑推理能力。针对问题一：分析此数独难度，我们认为有两点因素：一、空格数的多少，二、空间自由度。因此我们采取例证法进行分析，根据空格数来划分等级，进行一定的数据分析求出空格率，进而得出难度系数与空格数的关系。数独的难度等级与行、列、宫格内的空格数存在着密切联系，所以数独难易程度还与空间自由度有关。数独的空格自由度，指除掉空格本身，空格所在行、列、九宫内的空格数总和。除此之外我们可以以玩家完成数独题目的时间来判定数独题目的难度。针对问题二：“穷举法”是指当一个问题有几种可能而一时难以判定时,把几种可能一一列举出来,然后逐一尝试，直到尝试结果与给定的条件和结论相符为止。这种方法一般在计算机中运用，因为计算机计算速度快，可以很快验证答案是否正确，所以我们就以此来分析所有可能情况得出最终结果。针对问题三：为了找出更好的数独解法，我们运用了三种方法来求解。分别是：比较排除法、唯一解法和综合法。分析比较，选出较优方案。针对问题四：我们选用循环回溯法进行分析求解，与问题三中所求结果对比，以此验证其准确性。四、模型假设1、假设每种数独游戏都存在一定的联系且相互之间的难易程度成一定的比例；2、假设实验者水平相同，随着实验不断进行，完成数独题目熟练程度不会增加；3、假设实验者数独时间与数独题目难度无关。五、符号说明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.2实例分析以《数独》为例，我们得到一些数据。《数独》题目数为100道，表格行表示空格的个数，列表示难度的级别，一星为最容易，二星为容易，三星为难，四星为最难。例如：表一的首格3表示，难度为一星，空格数为50的题目有3道。表1统计《数独》空格数与难度50515253565758总数一星314二星11211125三星351146四星148325经过多次试验与分析，我们初步得到，随着空格数的增加，数独的难度系数也相应的增加。为进一步探讨数独的难易程度是否还与其他因素有关，我们对数独题目的统计表格进行处理，在同等难度上，将每种空格的题目个数除以该难度的总题目数，得到如下表格。表2计算《数独》空格率与难度50515253565758一星0.750.25二星0.040.040.840.040.04三星0.760.24四星0.560.320.12表格的数据用图表表示（图1），由图可以清晰看出，难度等级递增，空格数也不断增加。难度等级与空格数存在正比的关系。《数独》空格数与难度00.5150515253565758空格数空格率一星二星三星四星图1《数独》空格数与难度经过我们的多次试验与分析，我们初步得到，随着空格数的增加，数独的难度系数也相应的增加，当然数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体趋势递增，不同难度等级的题目空格数也一样的情况。6.1.2空格自由度与难度等级6.1.2.1数独难度的进一步分析数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体趋势递增，不同难度等级的题目空格数也一样的情况。我们得出初步结论，简单按照空格的数目多少来划分数独题目的难易程度是不全面的。同样空格数的数独题目，空格数分布位置的不同对难度等级也造成影响。注:格数是决定难度等级的因素，但不是唯一的因素。表3统计《数独-再露锋芒》空格数与难度45474951525354555657总数一星311112110二星12932118三星212285240四星14111615五星136106.1.2.2空格自由度的计算计算空格自由度的模型如下：(,)()()(,)[()()]iijSijSiSjFSijSiSjgg6.1.2.3空格自由度模型空格自由度的取值范围大，当数独题目全为0时，空格的数为81，空间自由度为2106；数独题目只剩1个空格时，空格自由度为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道不同难度的数独题目，将题目转换为字符串，计算空格自由度，实验结果如下：表4实验数据数独题目空格自由度难度书难度10008400910017006000700000504601802007002960030000709600406070006050080202000100008202220000000230300500400000037000003026500500400720076000000085009605401802009000600018803230060090000318000097000000560804000002000100070000080403600000029000053100002005001008434600000004050009800000003570003060280802094000000000000080042000001000020500010008105444由实验结果看出空格自由度与数独的难度等级存在正比的关系，难度系数的划分合理，与书中的划分基本一致。6.1.3难度等级综合模型6.1.3.1难度等级综合模型的建立数独题目的难度等级由空格数与空格自由度综合决定，建立几何难度等级模型：（1）以数独的空格数来划分，将空格数为横坐标X；（2）将空格自由度的总和划分等级，将等级数设为纵坐标Y；（3）根据（X，Y）判定难度。将计算好的空格数和空格自由度划分等级，两者结合，便可得到数独题目的难度等级了。难度等级等级为A-I，A为最易，I为最难，随着字母变大，难度逐次增加。具体划分的数据如下：图3难度判定坐标表5难度系数划分依据难度等级ABCDEFGHIX+Y23456789106.1.3.2难度等级综合模型的验证为了测试难度等级划分的情况的准确程度，主要做了如下测试：（1）测试的数独题目，查找出自《数独》和《路途中的数独》资料表6测试题目题号数独题目字符串难度1950624003038007061000000050360209008100000006500108072070000000610900830400856097一星2000074680800000000004006910020065071000000000480310050016900800000000009032750000二星3000000023030050040000003700000302650050040072007600000008500960540180200900060001二星4006009000031800009700000056080400000200010007000008040360000002900005310000200500三星5600000004050009800000003570003060280802094000000000000080042000001000020500010008四星（2）书籍中对数独难度等级的划分，并不一定合理，为了更准确区分难度等级，我们将的题目由3个人完成，计算每道数独题目完成需要的平均时间，完成时间越长，数独题目难度越大。测试结果如下：表7测试结果Testresult题号空格数空格自由度难度书中难度完成时间是否相符145698A一星16min23s是253922E二星18min29s是352880E二星17min28s是4561008G三星20min39s是5571054G四星29min57s否（3）实验结果表明，划分的难度与书中所划分的难度基本一致。以玩家完成数独题目的时间来判定数独题目的难度的话，那么此种划分难度等级的方法也合理。6.2问题二的求解6.2.1MATLAB编程求解数独6.2.1.1“链式推导方法”解数独定义所谓链式推导方法就是根据数独题中候选数的出现关系或分布规律来推导，形成一条或多条推导链，最后证明某个或某些候选数是真或是假的解数独题的方法。现在能想到的链式推导方法有：1、由A证明B为假（由一个格子的候选数假设