数独问题 数学建模

数独问题

摘要

本文是对数独问题进行求解。结合数独生成的特点，立足于题中数独建模和求解的要求，建立了数独难度分析WNF???函数和整数规划模型。

对于问题一，首先研究数独难度的影响因素，通过综合分析数独的特点结构，得出WNF???可以在常数时间内计算出来以衡量数独的难易程度。通过计算可知

WNF????0.04531，根据数独难度的划分得到如下结论： 数独难度系数为4，达到了极难的程度。

对于问题二，我们通过对此数独的分析和讨论，利用穷举法，通过matlab软件编程求解，最终得出答案，如表1所示。

对于问题三，我们利用回溯法思想，建立求解模型，具体算法一般采用如下步骤：

1).在此数独初盘选择一个空单元格； 2).取这个单元格中一个可能的候选数；

3).将这个候选数填入单元格中，迭代完成数独； 4).若这个候选数推导得到一个无效数独终盘，返回此单元格取其他候选数； 对于问题四采用整数规划模型，采用三维0-1 变量的方法，运用lingo软件编程求解。最终得到答案，如表1所示。

表1 数独问题的唯一解 8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 9 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2

关键词：数独 数独难度分析 穷举法 回溯法 整体规划

1

1问题的重述

前段时间芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。该数独如下图所示：

数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，且不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

根据以上描述，试完成以下问题： 1. 分析此数独的难度； 2. 用穷举算法求解数独；

3. 设计此数独求解的较优的算法；

4. 建立数独求解模型并给出此数独的答案。

2模型的基本假设

1该数独问题存在唯一解。

3符号说明

?? 表示空单元格候选数

W?n? 表示候选数数??的加权函数 cn??? 表示数独空单元格中的候选数数目函数

E(p) 表示该数独的空格处

WNF??? 表示该数独难度的函数

xijk 表示数k是否填入数独方中的（i，j）处 cij 表示往空格处填入0后数独方中（i，j）处的数 yij 表示经过求解后数独方中（i，j）处的数

2

4模型的建立与求解

4.1 问题1

4.1.1数独难度的影响因素

通过对数独的分析与研究，数独难度与数独候选数、逻辑推理方法、搜索步数、空格数以及空格的分布情况都有密切的关系。通过大量的计算观察发现，用到的逻辑与推理方法越复杂，那么在数独中出现的候选数越多;反之，在数独题中出现的候选数越多，解决数独题所用到的逻辑推理方法一般也越难。解答一个数独所用到的搜索步数越多，数独中的候选数越多。反之，一般情况下也成立。另外数独中的空格数以及空格的分布情况与候选数也有同样类似的关系。综合这几个影响数独难度的几种因素，分析候选数和空格数为主要影响因素，再根据其构造加权规范函数WNF???，计算数值来衡量数独难度。

4.1.2 WNF???函数的建立

加权规范函数建立在候选数列表的基础上。根据候选数列表，计算出每一个空单元格中的候选数数目，将候选数数目与其相对应的加权函数结合起来，计算加权规范函数WNF。

定义单元格?中的候选数数目函数c???为c??????，这个函数仅适用 于数独P中的空单元格，而数独P中的空单元格可以表示为

?????????|????1,2,3,4,5,6,7,8,9?:????? (1)

有n?1?n?9?个候选数的候选数数目函数

Cn????????|c????n??????|???n? (2)

我们赋予它相应的加权函数W?n?，从而得到加权函数

WF?????W?n?Cn??? (3)

n?19WF???不能准确的反映数独难度，WF???受数独中空单元格数目影响很大，呈正向关系，如在数独中删除单元格，数独空单元格数增加，导致WF???增加，即空格数越多，WF???越大，然而这并不符合所有的数独。为了排除这一影响，将加权函数WF???规范，得到加权规范函数：

3

WNF????W?n?C????W9??n?19???? (4)

根据以上的分析，对于某单元格?，其候选数数??越大，其对应的加权函数W?n?也应越大。我们采用指数函数Wexp?n??2n”计算数独?的WNF???，其中n为某空单元格的候选数数目。计算发现，WNF???与数独难度是正相关的，即WNF???越大，数独的难度越大。

4.1.3 WNF???函数的求解

根据题中给出的数独，按照数独游戏应该满足的条件，可以得到该数独的空

格处的候选数列表，如下表2所示：

表2 空格处候选数列表

8 1246 24569 2347 12357 1234 13569 4579 1345679 12459 124 3 6 12578 1248 1589 45789 14579 1456 7 456 348 9 1348 2 458 13456 123469 5 2469 2389 2368 7 1689 2489 12469 12369 12368 269 2389 4 5 7 289 1269 24679 2468 24679 1 268 2689 5689 3 24569 23457 234 1 23479 237 2349 359 6 8 23467 2346 8 5 2367 23469 39 1 2379 23567 9 2567 2378 123678 12368 4 257 2357

根据表2，把所得变量带入式(3)得：

WF????1392 (5)

由?????60代入式(4)式中得：

WNF????0.04531 (6)

4.1.4数独难度的划分

根据计算所得WNF???大小，我们将数独题难度分为四个区间，分别表示简单、中等、难、极难。为方便表示，我们用1、2、3、4来表示难度系数。

1)若WNF?????0,0.012?，数独简单，有较多候选数的空单元格很少，此时数独题用一些简单的直观法就可以解决，用1表示。

4

2)若WNF?????0.012,0.035?，数独有一定难度，要解决此数独要用到候选数法中的一些简单方法，且与直观法结合起来推理，用2表示。

3)若WNF?????0.035,0.045?，数独比较难，内部逻辑结构复杂，将直观法与候选数法结合起来一般可以解决问题，用3表示。

4)若WNF?????0.045,1?，这个数独很难，内部的逻辑结构相当复杂，将直观法与候选数法结合起来不一定可以解决问题，甚至有时候需要对某些空单元格进行猜测，用4表示。

在这里，我们将(0，1)粗略分为四个区间，用来相对表示数独的相对难度。根据数独难度的划分，由式(6)可得此数独难度系数为4，达到了极难的程度。

4.2 问题2

4.2.1算法的介绍

本问中需要的是用穷举法对数独问题进行求解，首先介绍一下穷举法：穷举法，或称为暴力破解法，是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的部分条件（约束条件）将所有可能解的情况列举出来，然后通过逐个验证是否符合整个问题的求解要求，而得到问题的解。这样解决问题的方法我们称之为穷举算法。穷举算法特点是算法简单，但运行时所花费的时间量大。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。

4.2.2 求解的思想

结合本问中需要用穷举法解决数独问题，最终算出上面所给出的数独问题的解。针对此数独问题，在此先介绍一下我的算法思想：

1）建立一个堆栈来存放数据；

2）根据每行、每列和一个小九宫中不能出现相同的数字的规则来找出所有空格中的所有可能值；

3）从可能值中选取一个可能项最少的并提取一个出来，若还有可能值就将其放入堆栈中去，若提出的值不满足条件则从堆栈中再提取一个值来继续求解直到找到满足条件的解；

举个例子吧，对这一数独问题，可以很快找到第八行第七列的可能值为3和9，其它空格的可能值都超过了三个，现取出3出来进行尝试，那么放入堆栈中的是9和其它的可能值，还有a（数独值），然后一直按这种方法进行下去，要是遇到不满足则从堆栈中重新拿出一个值来，直到结果满足结束循环。下面列了一个流程图，如下流程图所示。首先进行对程序中的所用符号进行说明，先将数独中问题的初始值(空格为0)存入数组a，将所有空格中的可能值存入数组y。

4.2.3 问题的求解

根据该流程图进行编程，并在matlab中实现，具体程序见附录1。经过2分钟左右求解得到最终结果，如下表4所示：

5

运行时间比较长。

3.问题3中介绍的算法——回溯法，它通过问题中的约束条件以试探-回溯-试探的筛选方式，将所有解的范围中不符合约束条件的解予以排除，从而达到快速求解的目的，这也是求解这一类问题的较优的算法。

4.对于问题4建立新的数独求解模型，我们采用三维0-1 变量，利用lingo软件编程进行求解，使数独问题的数学表述变得简单易懂。同时该模型可用于处理类似的填数问题如幻方，拉丁方等。

11

参考文献

[1] 孟庆铃. 数独问题人工解法的程序实现[J]. 甘肃科技，2006，

22(09):150-151.

[2] 雷 蕾，沈富可. 关于数独问题的算法的设计与实现[J]. 电脑知识与技术，

2007（2）：481-482．

[3] 王 琼，邹 晟. 数独问题的求解、评价与生成算法的研究[J]. 南京师范大

学学报：工程技术版,2010,3(1):76-79.

[4]胡英武.数独问题的整数规划模型[J]. 金华职业技术学院学

报:2011,6:86-88.

[5] 刘晓宝. 数独游戏的解题算法[J]. 电脑编程技巧与维护，2007（5）：64-67. [6] 程曦，肖华勇.数独谜题难度等级划分的步数法研究[J].电子设计工程，

2012,3:86-89

12

附录

附录1 问题2中matlab软件求解源程序： clear clc

a=open('qiujie.mat'); a=a.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); end end

for i=1:9

for j=1:9

if a(i,j)==0 clear c

k=3*(ceil(i/3)-1)+ceil(j/3); c=b(:,:,k); lg=(c>0); c=c(lg);

x=setdiff(1:9,c); clear c c=a(i,:); lg=(c>0); c=c(lg);

x=setdiff(x,c); clear c c=a(:,j); lg=(c>0); 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

13

d=(y>0); d=d'; d=sum(d); d=d'; if find(d==0) y=dui(:,:,sp); a=dua(:,:,sp); sp=sp-1; d=(y>0); 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(da,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

14

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(da(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

15

本文来源：https://www.bwwdw.com/article/j9no.html