1、数独问题 数学建模-本页仅作为预览文档封面，使用时请删除本页-数独问题 数学建模(总15页)数独问题摘要本文是对数独问题进行求解。结合数独生成的特点，立足于题中数独建模和求解的要求，建立了数独难度分析函数和整数规划模型。对于问题一，首先研究数独难度的影响因素，通过综合分析数独的特点结构，得出可以在常数时间内计算出来以衡量数独的难易程度。通过计算可知，根据数独难度的划分得到如下结论： 数独难度系数为4，达到了极难的程度。对于问题二，我们通过对此数独的分析和讨论，利用穷举法，通过matlab软件编程求解，最终得出答案，如表1所示。对于问题三，我们利用回溯法思想，建立求解模型，具体算法一般采用如下步
2、骤：1).在此数独初盘选择一个空单元格；2).取这个单元格中一个可能的候选数；3).将这个候选数填入单元格中，迭代完成数独；4).若这个候选数推导得到一个无效数独终盘，返回此单元格取其他候选数；对于问题四采用整数规划模型，采用三维0-1 变量的方法，运用lingo软件编程求解。最终得到答案，如表1所示。 表1 数独问题的唯一解812753649943682175675491293154237896369845721287169534521974368438526917796318452关键词：数独 数独难度分析 穷举法 回溯法 整体规划 1问题的重述前段时间芬兰一位数学家号称设计出全球最难的“
3、数独游戏”，并刊登在报纸上，让大家去挑战。该数独如下图所示：数独是根据99盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，且不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。根据以上描述，试完成以下问题：1. 分析此数独的难度；2. 用穷举算法求解数独；3. 设计此数独求解的较优的算法；4. 建立数独求解模型并给出此数独的答案。2模型的基本假设1该数独问题存在唯一解。3符号说明 表示空单元格候选数 表示候选数数的加权函数 表示数独空单元格中的候选数数目函数 表示该数独的空格处 表示该数独难
4、度的函数 表示数k是否填入数独方中的（i，j）处 表示往空格处填入0后数独方中（i，j）处的数 表示经过求解后数独方中（i，j）处的数4模型的建立与求解 问题1数独难度的影响因素通过对数独的分析与研究，数独难度与数独候选数、逻辑推理方法、搜索步数、空格数以及空格的分布情况都有密切的关系。通过大量的计算观察发现，用到的逻辑与推理方法越复杂，那么在数独中出现的候选数越多;反之，在数独题中出现的候选数越多，解决数独题所用到的逻辑推理方法一般也越难。解答一个数独所用到的搜索步数越多，数独中的候选数越多。反之，一般情况下也成立。另外数独中的空格数以及空格的分布情况与候选数也有同样类似的关系。综合这几个影
5、响数独难度的几种因素，分析候选数和空格数为主要影响因素，再根据其构造加权规范函数，计算数值来衡量数独难度。 函数的建立加权规范函数建立在候选数列表的基础上。根据候选数列表，计算出每一个空单元格中的候选数数目，将候选数数目与其相对应的加权函数结合起来，计算加权规范函数。定义单元格中的候选数数目函数为，这个函数仅适用于数独P中的空单元格，而数独中的空单元格可以表示为 (1)有个候选数的候选数数目函数 (2)我们赋予它相应的加权函数，从而得到加权函数 (3)不能准确的反映数独难度，受数独中空单元格数目影响很大，呈正向关系，如在数独中删除单元格，数独空单元格数增加，导致增加，即空格数越多，越大，然而这
6、并不符合所有的数独。为了排除这一影响，将加权函数规范，得到加权规范函数： (4)根据以上的分析，对于某单元格，其候选数数越大，其对应的加权函数也应越大。我们采用指数函数”计算数独的，其中为某空单元格的候选数数目。计算发现，与数独难度是正相关的，即越大，数独的难度越大。 函数的求解根据题中给出的数独，按照数独游戏应该满足的条件，可以得到该数独的空格处的候选数列表，如下表2所示：表2 空格处候选数列表8124624569234712357123413569457913456791245912436125781248158945789145791456745634891348245813456123
7、4695246923892368716892489124691236912368269238945728912692467924682467912682689568932456923457234123479237234935968234672346852367234693912379235679256723781236781236842572357根据表2，把所得变量带入式(3)得： (5)由代入式(4)式中得： (6)数独难度的划分根据计算所得大小，我们将数独题难度分为四个区间，分别表示简单、中等、难、极难。为方便表示，我们用1、2、3、4来表示难度系数。1)若，数独简单，有较多候选数的空单
8、元格很少，此时数独题用一些简单的直观法就可以解决，用1表示。2)若，数独有一定难度，要解决此数独要用到候选数法中的一些简单方法，且与直观法结合起来推理，用2表示。3)若，数独比较难，内部逻辑结构复杂，将直观法与候选数法结合起来一般可以解决问题，用3表示。4)若，这个数独很难，内部的逻辑结构相当复杂，将直观法与候选数法结合起来不一定可以解决问题，甚至有时候需要对某些空单元格进行猜测，用4表示。在这里，我们将(0，1)粗略分为四个区间，用来相对表示数独的相对难度。根据数独难度的划分，由式(6)可得此数独难度系数为4，达到了极难的程度。 问题2 算法的介绍本问中需要的是用穷举法对数独问题进行求解，首
9、先介绍一下穷举法：穷举法，或称为暴力破解法，是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的部分条件（约束条件）将所有可能解的情况列举出来，然后通过逐个验证是否符合整个问题的求解要求，而得到问题的解。这样解决问题的方法我们称之为穷举算法。穷举算法特点是算法简单，但运行时所花费的时间量大。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。 求解的思想结合本问中需要用穷举法解决数独问题，最终算出上面所给出的数独问题的解。针对此数独问题，在此先介绍一下我的算法思想：1）建立
10、一个堆栈来存放数据；2）根据每行、每列和一个小九宫中不能出现相同的数字的规则来找出所有空格中的所有可能值；3）从可能值中选取一个可能项最少的并提取一个出来，若还有可能值就将其放入堆栈中去，若提出的值不满足条件则从堆栈中再提取一个值来继续求解直到找到满足条件的解；举个例子吧，对这一数独问题，可以很快找到第八行第七列的可能值为3和9，其它空格的可能值都超过了三个，现取出3出来进行尝试，那么放入堆栈中的是9和其它的可能值，还有a（数独值），然后一直按这种方法进行下去，要是遇到不满足则从堆栈中重新拿出一个值来，直到结果满足结束循环。下面列了一个流程图，如下流程图所示。首先进行对程序中的所用符号进行说明
11、，先将数独中问题的初始值(空格为0)存入数组a，将所有空格中的可能值存入数组y。 问题的求解根据该流程图进行编程，并在matlab中实现，具体程序见附录1。经过2分钟左右求解得到最终结果，如下表4所示：开始数据初始化将a中所有空格（0）找到其可能的值判断是否有解将堆栈中的y和a拿出来判断是否需要将数据堆栈将数据a和y放入堆栈将可能值赋给a判断a是否有0的值结束 否 是 是 否 否 是 利用穷举法编程求解的流程图 问题3根据问题2中处理方法，发现穷举算法的特点是算法简单，但运行时所花费的时间较长。因此，我们在此基础上进行改进，尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。在求解数独
12、的过程中，遍历此数独所有可能的搜索树，直至找到数独的解为止!在这个过程中，我们采用回溯法进行求解。回溯法是一种搜索算法，其基本思路是:在一个问题中，根据题意给出的边界条件划定出所有可能解的范围(称为可能解)，根据题意确定出约束条件。利用程序顺次在所有可能解中，搜索时按照深度搜索的方式进行。即在第一层选定一个满足约束条件的解，然后以该可能解为出发点，搜索第二层的一个可能解(试探)。如果搜索到第二层的一个可能解，则继续搜索第三层的一个可能解。依次类推，直到所有层的可能解都被找到，则得到了该问题的一个完整解。如果第二层所有的可能解都不满足约束条件，则返回第一层，放弃原有的可能解，使用第一层的下一个可
13、能解(回溯)。以此类推，寻找第二层的一个可能解。具体算法一般采用如下步骤：1）在此数独初盘选择一个空单元格；2）取这个单元格中一个可能的候选数；3）将这个候选数填入单元格中，迭代完成数独；4）若这个候选数推导得到一个无效数独终盘，返回此单元格取其他候选数；由于回溯法是在不断地试探和回溯中运算，因此也可以称为试探法或者试探回溯法。从上面的描述中可知，回溯法得到的问题的解只是根据不同的初始条件获得的第一个完全满足所有约束条件的解，因此该解的获得和初始条件有关。如果想要获得该问题的全部解，则需要遍历所有的可能的初始条件，也就是遍历所有的第一层的可能解。回溯法相对于其他穷举的特点在于，不必把问题的每一
14、层的所有的可能解都遍历一遍，只要当前的可能解不满足约束条件就抛弃该解，寻求下一个可能解，而不必求解其余的下层解。当当前层的所有可能解都不满足约束条件，则回溯到上一层，抛弃上一层的当前可能解。从以上分析中结合数独问题的规则，得出数独问题的约束条件为:l)每一格的数值范围仅限于l一9。2)每一格内的数字在当前行不允许重复。3)每一格内的数字在当前列不允许重复。4)每一格内的数字在当前小九宫内不允许重复此算法最坏运行时间是，其中。n为数独中数字未确定的单元格数，k是数字已经确定的单元格数。但是将这个方法稍作修改就可以在线性时间解决一个数独题目，即首先选择数独中候选数个数最少的空单元格，再在其中选择候
15、选数进行试验一检验。虽然回溯法有超多项式的最坏时间，但是这种算法可以判断任何数独是否具有唯一解，进而解决这个数独，难度很大的数独求解经常用到此法。 问题4 问题的分析 根据对数独问题的分析，可知数独是根据99盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不能重复。为了叙述方便，对一个空的 9阶数独方的行、列、区进行重新编码。数独方的行序为从上到下记作19， 列序为从左到右记作19；然后把每一个粗线宫作为一个区，区的行序为从上到下记作13， 列序为从左到右记作13；区行的行序为从上到下记作13， 区列的列序为从左到右记作13。具体的编码方式
16、如下图1所示：模型的建立由于数 要么填入 该9阶数独方矩阵的（i，j）处，要么不填入，只有这两种状态，因而可用三维0和1 变量来表示。又该9 阶数独方的解唯一，可将这唯一解作为目标函数，行、列、区的约束条件可用三维的0和1 变量表出。 决策变量令: 表示数k填入 n 阶数独方矩阵的（i，j）处: 表示数k不填入（i，j）处 目标函数与约束规划问题的目标函数一般都是最大或最小型的，又因根据题意可知该 9 阶数独方的可行解唯一，且该可行解就是最优解，所以确定目标函数为单位数 1。通过对数独这个问题的分析可以得出，所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不能重复
17、。因此可以得到如下约束条件：（1）每一（i，j）处只能填一个数 k；（2）第i 行只有一个 k；（3）第j 列只有一个 k；（4）第一个区只有一个k； 该9 阶数独方的数学模型由上述分析可建立该9阶数独方的整数规划模型如下：注：（7）式表示数独方中每一（i，j）处只能填入一个数k；（8）式表示每一行只能有一个数k；（9）式表示每一列只能有一个数k；（10）式表示每一个区内只能有一个数k；（11）式表示只能取0或1；（12）上所有式中模型的求解要想求解问题中给出的数独问题，首先可将题目中的所有空格处填入同一常数a,不妨取 a=0，如表2所示。记 是表3中（i，j）处的数，是数独求解后（i，j）处
18、的数，是三维的0和1 变量，其含义如上所述。由上分析可知，任意填入（i，j）处的任意数 ，都有，那么表3 往空格填入0后的数独方800000000003600000070090200050007000000045700000100030001000068008500010090000400根据上面建立的关于这个数独问题的整数规划模型，利用lingo软件编程进行求解，可以得到该模型的最优解，也就是这个数独问题的唯一解。具体程序见附录2，求解的最终结果如下表4所示：表4 该数独问题的解812753649943682175675491293154237896369845721287169534521
19、974368438526917796318452模型的检验问题1中采用了一种对数独难度等级的划分方法，首先对问题的进行了综合的分析，然后在多个影响数独难度的因素中选取空格数和空格候选数作为主要影响因素，根据给出的计算方法对该数独进行计算，得出该数独的难度是属于极难的。由于在最后的计算过程中未考虑其他影响因素，因此得到的结果必然存在一定的误差，但这个划分方法还是可取的、有一定道理的。问题2中采用了穷举法对该问题进行求解，由于该方法考虑了所有可能出现的情况，所以在有解的情况下一定可以求解该问题的解；也正因为如此，运用该算法进行求解时会花费较长的时间。问题3中设计了一种更优的求解算法回溯法。它主要是
20、对穷举法进行了一定的改进，缩短了求解该数独问题的的时间。问题4中建立了一个求解数独问题的模型整数规划模型。该模型充分考虑了该数独应该满足的约束条件，并在此基础上编程进行求解，得到最终答案。该模型求解的结果相当准确，并适应于这一类问题的求解。模型的分析与推广1.度量的优劣衡量数独难度的最客观方法就是找到解决这个数独所用时间，根据时间的长短判断数独难易。其次，可以根据解答这个数独所用到的逻辑推理方法难易，量数独难度。但这两种方法都需要具体解答出所给数独后才能做出判断，虽然可以准确反映数独难度，但耗时较多。相比之下，可以在常数时间内计算出以衡量数独难易，对于任意一个数独，我们不必具体解答，只需列出它
21、的候选数列表就可以计算出其相对难度，时间复杂性很低。扫描每个单元格所在的行、列、宫，通过唯一性原则确定其上的候选数，这种方法往往使得每个单元格上的候选数较多，而有些候选数是可以通过一些简单的逻辑推理消除的，从而使得的值可能会偏高，过高估量数独的难度，这也是这种方法的缺陷所在。2.问题2利用穷举法，模型思路比较简单，正适用于解决多维、大规模、复杂问题的通用法，借助matlab软件编程求解，使数独求解更加容易、方便，但它运行时间比较长。3.问题3中介绍的算法回溯法，它通过问题中的约束条件以试探-回溯-试探的筛选方式，将所有解的范围中不符合约束条件的解予以排除，从而达到快速求解的目的，这也是求解这一
22、类问题的较优的算法。4.对于问题4建立新的数独求解模型，我们采用三维0-1 变量，利用lingo软件编程进行求解，使数独问题的数学表述变得简单易懂。同时该模型可用于处理类似的填数问题如幻方，拉丁方等。参考文献1 孟庆铃. 数独问题人工解法的程序实现J. 甘肃科技，2006，22(09):150-151.2 雷 蕾，沈富可. 关于数独问题的算法的设计与实现J. 电脑知识与技术，2007（2）：481-4823 王 琼，邹 晟. 数独问题的求解、评价与生成算法的研究J. 南京师范大学学报：工程技术版,2010,3(1):76-79.4胡英武.数独问题的整数规划模型J. 金华职业技术学院学报:201
23、1,6:86-88.5 刘晓宝. 数独游戏的解题算法J. 电脑编程技巧与维护，2007（5）：64-67.6 程曦，肖华勇.数独谜题难度等级划分的步数法研究J.电子设计工程，2012,3:86-89附录附录1 问题2中matlab软件求解源程序：clearclca=open();a=;sp=0;dui=;while find(a=0)for i=1:3 for j=1:3 b(:,:,3*i+j-3)=a(3*i-2:3*i,3*j-2:3*j); endend for i=1:9 for j=1:9 if a(i,j)=0 clear c k=3*(ceil(i/3)-1)+ceil(j/3
24、); c=b(:,:,k); lg=(c0); c=c(lg); x=setdiff(1:9,c); clear c c=a(i,:); lg=(c0); c=c(lg); x=setdiff(x,c); clear c c=a(:,j); lg=(c0); c=c(lg); x=setdiff(x,c); n=length(x); for ii=1:9-n x(ii+n)=0; end else x=10*ones(1,9); end y(9*(i-1)+j,:)=x; end end d=(y0); d=d; d=sum(d); d=d; if find(d=0) y=dui(:,:,sp
25、); a=dua(:,:,sp); sp=sp-1; d=(y0); d=d; d=sum(d); d=d; end d=find(d=min(d); d=d(1); i=ceil(d/9); j=d-9*i+9; A=y(d,1); y(d,1)=y(d,2); y(d,2)=y(d,3); y(d,3)=0; if sum(y(d,:)0 sp=sp+1; dui(:,:,sp)=y; dua(:,:,sp)=a; end a(i,j)=A;end a附录2 问题4中lingo软件的求解源程序：model: sets: da/1.9/:n; link(da,da):y,c; link1(d
26、a,da,da):x; endsets data: n=1 2 3 4 5 6 7 8 9; c= 8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0 ; enddata min=1; for(da(i):for(da(j):for(link|c(i,j)#ne#0:y(i,j)=c(i,j); for(da(i):for(d
27、a(j):y(i,j)=sum(da(k):k*x(i,j,k); for(da(i):for(da(j):sum(da(k):x(i,j,k)=1); for(da(i):for(da(k):sum(da(j):x(i,j,k)=1); for(da(j):for(da(k):sum(da(i):x(i,j,k)=1); for(da(i)|i#le#3: for(da(j)|j#le#3: for(da(k): x(3*i-2,3*j-2,k)+x(3*i-2,3*j-1,k)+x(3*i-2,3*j,k) +x(3*i-1,3*j-2,k)+x(3*i-1,3*j-1,k)+x(3*i-1,3*j,k) +x(3*i,3*j-2,k)+x(3*i,3*j-1,k)+x(3*i,3*j,k)=1); for(link1(i,j,k):bin(x); end
