数独中的数学模型

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

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

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

4、独游戏中，难度最高的等级。数独是根据9X9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。由此我们要解决以下问题：1问题一：分析此数独的难度；问题二：用穷举算法求解数独；问题三：设计此数独求解的较优的算法；问题四：建立数独求解模型并给出此数独的答案。三、问题分析根据题中所给信息我们知道数独是一种数字解谜游戏，要求游戏者有很好的观察能力和逻辑推理能力。针对问题一：分析此数独难度，我们认为有两点因素：一、空格数的多少，二、空间自由度。因此我们采取

5、例证法进行分析，根据空格数来划分等级，进行一定的数据分析求出空格率，进而得出难度系数与空格数的关系。数独的难度等级与行、歹h宫格内的空格数存在着密切联系，所以数独难易程度还与空间自由度有关。数独的空格自由度，指除掉空格本身，空格所在行、歹h九宫内的空格数总和。除此之外我们可以以玩家完成数独题目的时间来判定数独题目的难度。针对问题二：“穷举法”是指当一个问题有几种可能而一时难以判定时，把几种可能一一列举出来，然后逐一尝试，直到尝试结果与给定的条件和结论相符为止。这种方法一般在计算机中运用，因为计算机计算速度快，可以很快验证答案是否正确，所以我们就以此来分析所有可能情况得出最终结果。针对问题三：为

6、了找出更好的数独解法，我们运用了三种方法来求解。分别是：比较排除法、唯一解法和综合法。分析比较，选出较优方案。针对问题四：我们选用循环回溯法进行分析求解，与问题三中所求结果对比，以此验证其准确性。四、模型假设1、假设每种数独游戏都存在一定的联系且相互之间的难易程度成一定的比例；2、假设实验者水平相同，随着实验不断进行，完成数独题目熟练程度不会增加；3、假设实验者数独时间与数独题目难度无关。五、符号说明N数独的空格数目F听有空格的自由度的总和S(i,j)数独矩阵A(9*9)中i行j列的空格自由度S(i)行的空格数目S(j).行的空格数目gi除去同行同列的同一宫中的空格数六、模型建立与求解6.1问

7、题一的求解为了更好的区分难易程度我们将数独以空格数划分为五个等级，具体划分如下：空格数的取值范围为0-81,以空格数来平均划分难度等级，将空格数平均分成5个类型，空格数的取值范围缩小到37-81。划分等级如下表所示：37-4546-5455-6364-7273-811级2级3级4级5级以数独为例，我们得到一些数据。数独题目数为100道，表格行表示空格的个数，列表示难度的级别，一星为最容易，二星为容易，三星为难，四星为最难。例如：表一的首格3表示，难度为一星，空格数为50的题目有3道。独题目的统计表格进行处理，在同等难度上，将每种空格的题目个数除以该难度的总题目数，得到如下表格。图1数独空格数与

8、难度经过我们的多次试验与分析，我们初步得到，随着空格数的增加，数独的难度系数也相应的增加，当然数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体趋势递增，不同难度等级的题目空格数也一样的情况。6.1.2空格自由度与难度等级数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体趋势递增，不同难度等级的题目空格数也一样的情况。我们得出初步结论，简单按照空格的数目多少来划分数独题目的难易程度是不全面的。同样空格数的数独题目，空格数分布位置的不同对难度等级也造成影响。注:格数是决定难度等级的因素，但不是唯一的因素。表3统计数独-再露锋芒空格数与难度4547495152535

9、4555657总数一星311112110二星12932118三星212285240四星14111615五星13610计算空格自由度的模型如下：空格自由度的取值范围大，当数独题目全为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,1

10、180为4级，1080,1300为5级(图2)。图2空格自由度难度模型随机抽取数独书籍不同难度等级的题目，进行空格自由度的计算，验证空格自由度衡量数独题目的难度是否合理，首先抽取4道不同难度的数独题目，将题目转换为字符用，计算空格自由度，实验结果如下：表4实验数据数独题目空格自由度难度书难度18202228803231008434105444由实验结果看出空格自由度与数独的难度等级存在正比的关系，难度系数的划分合理，与书中的划分基本一致。数独题目的难度等级由空格数与空格自由度综合决定，建立几何难度等级模型：(1)以数独的空格数来划分，将空格数为横坐标X;(2)将空格自由度的总和划分等级，将等级

11、数设为纵坐标Y;(3)根据(X,Y)判定难度。将计算好的空格数和空格自由度划分等级，两者结合，便可得到数独题目的难度等级了。难度等级等级为A-I,A为最易，I为最难，随着字母变大，难度逐次增加。具体划分的数据如下：图3难度判定坐标表5难度系数划分依据ABCDEFGHIX+Y2345678910为了测试难度等级划分的情况的准确程度，主要做了如下测试：(1)测试的数独题目，查找出自数独和路途中的数独资料表6测试题目题号数独题目字符串难度4四星(2)书籍中对数独难度等级的划分，并不一定合理，为了更准确区分难度等级，我们将的题目由3个人完成，计算每道数独题目完成需要的平均时间，完成时间越长，数独题目难

12、度越大。测试结果如下：表7测试结果Testresult题号空格数空格自由度难度书中难度完成时间是否相符145698A一星16min23s是253922E二星18min29s是352880E二星-7min28s是4561008G三星：!0min39s是5571054G四星29min57s否(3)实验结果表明，划分的难度与书中所划分的难度基本一致。以玩家完成数独题目的时间来判定数独题目的难度的话，那么此种划分难度等级的方法也合理。6.2 问题二的求解6.2.1 MATLAB编程求解数独“链式推导方法”解数独定义所谓链式推导方法就是根据数独题中候选数的出现关系或分布规律来推导，形成一条或多条推导链，

13、最后证明某个或某些候选数是真或是假的解数独题的方法。现在能想到的链式推导方法有：1、由A证明B为假（由一个格子的候选数假设推导证明另一个格子里的某个候选数是假的方法）2、由A证明B为真（由一个格子的候选数假设证明另一个格子的某个候选数是真的方法）3、由A证明A为假（由某个候选数推导而出现错误证明本身假设是错的方法）4、与成名方法结合的链式推导5、还有如何推导，先定义一下，所说的A、B、C、a、b、c等等，都是候选数在某格子位置的代号。箭头“-”是“导致”或“因此”的意思；“二”是等于，“”是不等于的意思；A=1-B=2-C=3的意思是：当A是1时，导致B等于2,B等于2因此C就等于3，余下类推

14、；A=1-B1-的意思就是当A是1时，B就不是1,余类推；“同一单元”的概念是指同一行或同一列或同一九宫格。6.3 问题三的求解由于数独规则要求每行、每列和每宫的数字不重复，所以已出现的数字可以排除掉同行、同列、同宫中的其他单元格内再填入该数字的可能性，以下我们用两个截图解释。比较排除法流程图如下：排除法的模型优点是步步为营,谨慎小心，出错率不大。但其推算过程较复杂，编程水平要求很高，所以不适合解答本题。当某行已填数字的宫格达到8个，那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为行唯一解。当某列已填数字的宫格达到8个，那么该列剩余宫格能填的数字就只剩下那个还没出现过的数字了，成

15、为列唯一解。当某九宫格已填数字的宫格达到8个,那么该九宫格剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为九宫格唯一解。以下我们用一个例子来简单的介绍这种算法：A行已经添入8个数字,A行只有数字3没有出现过,所以A9=3,这是行唯一解第1列已经添入8个数字，第1列只有数字5没有出现过，所以E1=5,这是列唯一解在A8所在九宫格区域已经添入8个数字,只有数字9没有出现过，所以A8=9,这是九宫格唯一解唯一解法实施起来比较简单，但就是因为简单所以只能应用于较简单的数独游戏中或者是用于较难数独游戏题型中的最后阶段，所以唯一解法的模型也不适合解答本题。我们借鉴了数独游戏算法中几种算法的思想，进行

16、归纳最后定义为综合法，其算法的步骤如下：1、将所有未确定的格子的可能性定义为0xFFFF（即所有数字都可能），可能数目为9。2、寻找所有确定的格子A（可能数目为0）,在所有与A同行、同列和同区域的未确定的格子的可能性中减去与A相同的可能性。例如：A确定为9,则与A同行、同列和同区域（区域标志相同）的未确定的格子的可能性与0xFEFF按位与（除去可能性9）,并将其可能性数目减少。在除去可能性的过程中如果发现某个格子B的可能性数目由1减小为0,说明B和A只能取相同的数字，这可能是题目本身无解引起，也肯能是由于步骤3中搜索方向不对引起的，可认为此方向的搜索无解，退出这一方向的搜索。定义这个检查为唯一

17、性检查。3、寻找所有未确定格子中可能性数目最少的格子M如果M的可能性数目为1,则确定M将M的可能性数目定义为0,并把确定数量加1,如果此时确定数量达到81,则报告找到解，否则，在所有与M同行、同列和同区域的未确定的格子的可能性中减去与M相同的可能性，并进行唯一性检查。然后重复步骤3。如果M的可能性大于1,则把M假设为所有M的可能性，分多个方向进行搜索，在每一个搜索方向重复步骤3（这个可以用递归来实现）。6.4 问题四的求解在比较排除法、唯一解法的基础上，我们对模型进行深化，提出了循环回溯模型。其回溯法求解数独步骤如下：1）按下标sp由小到大的顺序逐个获取空白位置；2）对空白位置sp试图填数，填

18、数的规律为从1-9依次由小到大选择（有序）；3）若找到一个可以填入的数据，将数据填入数独sp,并将sp入栈push否则转5）;4）获取下一个空白位置，若有空白位置则转2）,否则转6）;5)因为check(sp)返回1),找不到合适数据填入该位置，进行回溯，即pop得到上一次填数的位置sp,重新对该位置试图填数，且为了递推的高效性，此时可以仅从当前sp存放的数字大于1开始试图填充，转3);6)填数结束。回溯法流程图如下：第一个候选值给a(i,j)更新a结束循环，输出a模型的整个函数体在while(isempty1(a)的循环体中，只有当a得所有点全部确定下来后，该循环才终止。我们是从矩阵的第一个

19、元素开始循环的，首先判断a(i,j)是否确定，如果确定，则判断下一个点，如果a(i,j)没有确定，则把a(i,j)的第一个候选值赋给它，并用firstsolve()更新a100次，如果出现矛盾，即isright(a)=0,则说明第一个候选值错误，此时要把下一个候选值赋值给a(i,j),由于不同的a(i,j)的候选值下标是不同的，为此，需要指针表达这种关系，于是我们定义了一个新的细胞数组t=cell(9,9),用ti,j表示a(i,j)的候选值下标，并用语句：forii=1:9forjj=1:9t=iijj=1;endend把ti,j的值初始化为1,以后循环中依次加1即可。当a(i,j)的所有候

20、选值都尝试过后依然出现矛盾(isright(a)=0),则应该回溯到上一点，让上一点取下一个候选值，同时让当前点清空。回溯的时候容易出现的问题是发生越界，最容易发生的越界的点为每一彳T的第一个点和矩阵的第一个点a(1,1),为解决回溯越界问题，我们用一系列的ifelse语句进行约束：j=j-1elseifj=1j=9;i=i-1ifi=0i=9endend需要注意的是，程序回溯的是上一个未确定的点，而不是上一个点，因此，在回溯过程中需要进行判断上一点是否已经是确定的点。如果a(i,j)确定下来了，则应继续寻找下一点，此时又遇到越界问题，容易越界的点是矩阵的最后一个点a(9,9)和每一行的最后一

21、个点，我们依然用一系列的ifelse语句进行限制：j=j+1;ifj=10i=i+1;i=1;ifi=10&j=10i=1;j=1;endend这样，通过循环回溯，直到所有的点都已经确定下来，结束程序，可得出正确的解。如下表所小：表8数独游戏终盘结果8127536499436821756754912831：542317819P6369845721287169534512197436r8438526917796318452七、模型优缺点7.1模型优点：(1)难度等级模型引入空格自由度的概念，是模型的创新点；(2)模型对数独的难度的分类较为直观；(3)难度等级的模型可操作性强；(4)难度模型计算的

22、难度等级符合现实的等级划分。7.2模型缺点：(1)模型所划分难度等级的区域过大，在实际题目中，数独的空格数往往较为集中在20-40中，研究的范围较大，划分的难度等级准确性低，主观成分过强；(2)实验数据分析过程中，默认数独书籍对难度等级的划分为合理，这个前提存在不准确的可能，因为书籍中的难度等级划分，可能渗入编者个人的主观意识，笔者在研究过程中，没有剔除该种可能，也存在着不足；(3)模型建立忽视数独题目所提供的数字不同，导致数独题目难度不一致的可能。参考文献1刘彬，刘丹彤，王倩倩.数学软件(2)课程设计.百度文库.2012-07-212MonkeyDove.数学建模与数学实验计算机模拟.百度文

23、库.2012-07-21附录针对问题二编写的Matlab程序：functioninitialA=zeros(9,9);%t灰级A(1,1268)=2458;A(2,1358)=8935;A(3,7)=3;A(4,3689)=4915;A(6,1247)=3982;A(7,3)=1;A(8,2579)=2973;A(9,2489)=3762;disp(theinitalconditionis:)A刎示初始值main(A);loadresultdisp(theresultis:)Aend%functionmain(A)ifisempty(find(A=0)=1saveresultAreturn;e

24、ndi,j,P=findmp(A);iflength(P)=0return;elsefork=1:length(P)A(i,j)=P(k);main(A);endendend%、的格子及其可能元素functioni,j,P=findmp(A)temp=zeros(9,9);temp(A0)=10;forrow=1:9forcol=1:9ifA(row,col)=0r=A(row,;r=r(r0);c=A(:,col);c=c(c0);rc1=and_log(r,c);%行列不同元素放在rc中rr=findrc(row);cc=findrc(col);rc2=reshape(A(rr*3+1:r

25、r*3+3,cc*3+1:cc*3+3),1,9);rc2=rc2(rc20);total=and_log(rc1,rc2);temp(row,col)=9-length(total);endendendv,i=min(temp);v,j=min(v);i=i(j);row=i;col=j;%以下找出可能元素r=A(row,;r=r(r0);c=A(:,col);c=c(c0);rc1=and_log(r,c);rr=findrc(row);cc=findrc(col);rc2=reshape(A(rr*3+1:rr*3+3,cc*3+1:cc*3+3),1,9);rc2=rc2(rc20);

26、total=and_log(rc1,rc2);P=;forkkk=9:-1:1ifisempty(find(total=kkk)=1P=P,kkk;endendend%functionc=and_log(a,b)c=a;fori=1:length(b)log=0;forj=1:length(a)ifb(i)=a(j)log=1;break;endendiflog=0c=c,b(i);endendend%的%所在位置functionrr=findrc(row)switchrowcase123rr=0;case456rr=1;otherwiserr=2;end针对问题四用matlab编写数独9*9

27、的程序：functiony=choose1(a)y=cell(9,9);choose=cell(9,9);select=1,2,3,4,5,6,7,8,9;save=cell(9,9);grid=cell(3,3);templ=a(1:3,1:3);grid1,1=temp1(temp10);temp2=a(1:3,4:6);grid1,2=temp2(temp20);temp3=a(1:3,7:9);grid1,3=temp3(temp30);temp4=a(4:6,1:3);grid2,1=temp4(temp40);temp5=a(4:6,4:6);grid2,2=temp5(temp5

28、0);temp6=a(4:6,7:9);grid2,3=temp6(temp60);temp7=a(7:9,1:3);grid3,1=temp7(temp70)，;temp8=a(7:9,4:6);grid3,2=temp8(temo80);temp9=a(7:9,7:9);grid3,3=temp9(temp90);%求出每一点处所在行、歹h九宫格处已有的点fori=1:9fori=1:9ifa(i,j)=0n1=find(a(i,:0);N1=a(I,n1);n2=find(a(:,j)0);N2=a(n2,j);N2=N2;aaa=N1,N2;%ffia(i,j)所在行、歹h九宫格已确定

29、的数字合并ifi=1&i=j&j=1&i=4&j1&i=7&j=4&i=4&j=4&i=7&j=7&i=1&j=7&i=4&j=7&i=7&j1|a(i,j)=0tempp=1;endendendy=tempp;%WU断该矩阵的点是否有解，如果无解，则返回值为0,否则返回值为1functiony=isright(a)choose2=choose1(a);tempp=1;fori=1:9forj=1:9iflength(choose1i,j)=0tempp=0;endendendy=tempp;%functiony=sudu_solve(a)i=1;j=1;choose2=choose1(a);

30、t=cell(9,9);forii=1:9forjj=1:9t=ii,jj=1;endendwhileisempty1(a)ifa(i,j)=0whileti,j=length(choose2i,j)ti,j=length(choose2i,j);enda(i,j)=choose2i,j(ti,j);endendend%ifisright(a)=0a(i,j)=0;ifj1j=j-1;elseifj=1j=9;i=i-1;ifi=0i=9endendendiflength(choose2i,j)=1ifj1j=j-1;elseifj=1j=9;i=i-1;ifi=0i=9;endendendElse%h一点的候选值改变，如果上一点的候选值只有一个，则继续寻找上一点a(i,j)=choose2i,j(ti,j+1)endend喇k出循环后继续寻找下一点j=j+i;ifj=10i=i+1;j=1;ifi=10&j=10i=1;j=1;endend呦口果a(i,j)的值确定，寻找下一点elsej=j+1;ifj=10i=i