Kakuro数独问题

-Kakuro数独问题092260 周扬092312 童思博问题描述：l 在空格中填入数字1-9，数字0不能出现l 带斜线的方格，斜线上方的数字等于该方格右面对应的一组水平空格里的数字之和；斜线下方的数字，等于该方格下面对应一组垂直空格里的数字之和l 同一数字在每组水平（垂直）空格里只能出现一次(右图为一范例)针对Kakuro数独，完成以下问题：l 讨论求解模型或方法,并给出算法复杂性讨论.l 如何对Kakuro数独问题划分为不同级别，并给出一种划分方式，并给出实例.l 如何产生不同级别的Kakuro数独，并保证产生的数独问题为唯一解。l 假定所有kakuro数独都以8*10为标准进行讨论.问题背景：数谜(Kakuro)当大家还在钻研数独Sudoku，究竟填写1至9这几个数字的窍门时，另一个相类的游戏于最近迅速火爆，这就是Kakuro。Kakuro在英美等地人气急升，它的好玩之处在于既有Sudoku的逻辑推理，还多了加数运算。在空格内选添1-9中一个数字，最终目的使那些数字加起来之和与所给的数字相等。说起来简单，实际上想在游戏中过关可不是则容易的。Kakuro相比Sudoku更难玩，除了涉及逻辑推理，更要大家计算加数。与Sudoku一样，是将一串数字加到面板上，大前提是加入的数字是空格旁边数字的总和，还有该总和算式内的数字不能重复。玩Kakuro，会用到在小学时期的加数运算法，如要填入3个方格，单是总和9便已经有3个配搭，包括1+2+6、1+3+5、2+3+4；再者，数字的次序可以不同，这样便有18个组合，究竟哪个才是正确答案，这就是游戏的最困难地方。Kakuro是一款在游戏中需要增加运算(加法)的智力游戏，逻辑推理性很强。与数独玩法相近但趣味更丰富、挑战性更大。Kakuro的玩法与数独相似，有的是由3乘以3的9个方格组成，每个方格又分成3乘以3的9格，在空格内选添1至9中的一个数字，最终目的是使那些数字加起来之和与所给出的数字相等。也有的是8乘10的方格组成，其他刚相同。游戏规则每一道谜题都是实体格和“线索”格的组合，再加上一个个自成一体的空格组。每个空格组，我们称之为一个“回”，游戏的目的就是在空格中填入1到9等数字，每一回里，相同的数字不能重复出现。每一行，列的“回”，会先从灰色的线索格开始，它就位在每一回的左边（就列而言），或上面（就行而言）。每一个回在遇到实体格或线索格就结束了。线索格通常以对角线分成两半，包含一到两个数字，一个数字就是一个“提示码”。斜线上方的提示码代表该列数字的加总总和；相同的，斜线下方的提示码则表示在它以下的行回数字的加总总和。不论在行回或列回里，数字都不能重复。举例来说，4不能拆解成（2，2），只能拆解成（1，3）符号说明 n数独中需要填入的空格总数Xi 空格中填入的数（i=1,2,3，n） m数独中“回”的个数，即一行（列）空格组的组数Yj 每一个“回”的和（j=1,2,3，m） SUMi 用于判断其填入数的重复性，设定的初值为45MULi 作用同上，设定的初值为9!=362880 A 一个二元一唯数组表，作用也是判断其重复性问题分析：a) 若给出一存在可行解的数独，最简单直接的办法就是将其每个空格设为一个未知元Xi（i=1,2,3，n），利用LINGO的线性规划功能求解，同时需加上限制条件（同一数字在每组水平（垂直）空格里只能出现一次），但是这个算法的计算量（忽略数字重复的剪枝）高达9n，如范例给出的就为9401.47*1038，显然我们不能承受如此恐怖的计算量，但这是最为直接、最容易想到的方法。简化计算量势在必行。我们可以确定数独本就为一个搜索类型的题目，当搜索的次数达到一定量时（如9n）必然可以求出答案（若没有答案，则不存在可行解）！因此，我们需要更多的剪枝来优化搜索的次数。1）技巧性的剪枝一：唯一分解方式数和中有些和值只有一种分解方式。2字组的优化：92A223字组的优化：93A33依此类推：9nAnn（n=1,2,3,9）简化效率非常的客观！2字组 3=1+2 4=1+3 16=7+9 17=8+93字组 6=1+2+3 7=1+2+4 23=6+8+9 24=7+8+94字组 10=1+2+3+4 11=1+2+3+5 29=5+7+8+9 30=6+7+8+95字组 15=1+2+3+4+5 16=1+2+3+4+6 34=4+6+7+8+9 35=5+6+7+8+96字组 21=1+2+3+4+5+6 22=1+2+3+4+5+7 38=3+5+6+7+8+9 39=4+5+6+7+8+97字组 28=1+2+3+4+5+6+7 29=1+2+3+4+5+6+8 41=2+4+5+6+7+8+9 42=3+4+5+6+7+8+98字组 36=1+2+3+4+5+6+7+8 37=1+2+3+4+5+6+7+9 38=1+2+3+4+5+6+8+9 39=1+2+3+4+5+7+8+9 40=1+2+3+4+6+7+8+9 41=1+2+3+5+6+7+8+9 42=1+2+4+5+6+7+8+9 43=1+3+4+5+6+7+8+9 44=2+3+4+5+6+7+8+98字组中每一个和值都有唯一解。9字组由于组内数字不能重复，9字组只能是1-9各填一遍，和值只能是45。2）技巧性的剪枝二：重叠组重叠组在数和中有很重要的作用，当重叠的两个组都是唯一解时就更为尤甚。这种情况常常用来做解题的突破口。以上文的题目为例（是第1行第1列）：2316由于23=9+8+6和16=9+7都是唯一解，中就必定填它们的共有数字：9。还有一种情况，两个组中有一个是唯一解，另一个可以通过推理进行排除从而得到唯一解。还以上文的题目为例（是第4行第2列）：3030=9+8+7+6是唯一解。但是与它重叠的组和值为7，不可能填入7或比7大的数，所以中必定填6。 3）重复性的剪枝 首先我们需要建立一唯表A，A中二元分别为SUMt和MULt，t=1,2,3ma*len(A)表示A表的最大长度，每当填入一个数*时，做如下操作：SUMi=SUMi-XMULi=MULiX此时若*没有和规则相违背（即不重复），则SUMi为19中若干个不同数的和，MULi为19中若干个不同数的乘积，两者为一一对应关系，A表就用来存储这种对应关系，SUMt和MULt事先存储好所有可能的情况，出现*后，计算SUMi和MULi与SUMt和MULt比较。如果对应相等，则没有出现重复；反之，则进行下一个可行解的搜索。然而这个t有多大呢. 经计算发现A表的长度 tmax=29 ，可以接受。利用上述三个剪枝，完全可以把原本最高达9n的搜索次数，减少至9!次，甚至更少！这是我们用电脑可以轻松搜索出答案的次数。附求解kakuro数独程序MATLAB：type=;data=;row=;col=;can=;sum=;size=;%设置变量%type 表示每个坐标的类型：0表示待填，1表示不填，2表示限制，3表示已填%data 表示每个坐标的数据值：对限制值，高两位表示列限制，低两位表示行限制；对空格，即表示填写值%row 表示行限制值标号%col 表示列限制值标号%can 表示每个限制下，1.9能否填入，用0-1表示，1表能填，0表不能%sum 表示每个限制的剩余值，即原限制值减去已填数后的值%size 表示每个限制下待填数个数fid=fopen(kakuroin.t*t);A=fscanf(fid,%d,10,8);A=A;for i=1:8, for j=1:10, if A(i,j)=0, type(i,j)=1; data(i,j)=0; elseif A(i,j)0, type(i,j)=0; data(i,j)=1; else type(i,j)=2; data(i,j)=-A(i,j); end endendtype=type ones(8,1);ones(1,11);fclose(fid);%以上为读入kakuro数据，并对type，data置初值n=1;for i=1:8, j=1; while j=10, if type(i,j)=2 j=j+1; else sum(n)=mod(data(i,j),100); size(n)=0; cann=ones(1,9); while type(i,j+1)=0 & j10, j=j+1; size(n)=size(n)+1; row(i,j)=n; end j=j+1; n=n+1; end endendfor j=1:10, i=1; while i=8 if type(i,j)=2, i=i+1; else sum(n)=floor(data(i,j)/100); size(n)=0; cann=ones(1,9); while type(i+1,j)=0 & i8, i=i+1; size(n)=size(n)+1; col(i,j)=n; end i=i+1; n=n+1; end endend%初始化每个限制值的信息，sum，size，cani=1;j=1;while i=8 & j=10, if type(i,j)=0, place=1; else ama*=min(9,sum(row(i,j),sum(col(i,j); while data(i,j)ama*, place=0; else canrow(i,j)(data(i,j)=0; cancol(i,j)(data(i,j)=0; size(row(i,j)=size(row(i,j)-1; size(col(i,j)=size(col(i,j)-1; sum(row(i,j)=sum(row(i,j)-data(i,j); sum(col(i,j)=sum(col(i,j)-data(i,j); type(i,j)=3; place=1; end end%place，在空格内填数，并减小size和sum的值 if place, while type(i,j)=0, if j=10, i=i+1; j=1; if i=9 return; end; continue; end; j=j+1; end data(i,j)=1; else while type(i,j)=3, if j=1, i=i-1; j=10; continue; end; j=j-1; end canrow(i,j)(data(i,j)=1; cancol(i,j)(data(i,j)=1; size(row(i,j)=size(row(i,j)+1; size(col(i,j)=size(col(i,j)+1; sum(row(i,j)=sum(row(i,j)+data(i,j); sum(col(i,j)=sum(col(i,j)+data(i,j); type(i,j)=0; %reset，清空*空格中已填数的状态，增加size和sum的值 data(i,j)=data(i,j)+1; endend%程序主体，完成回溯算法b) 划分数独的等级 划分等级的方式多种多样。在此，我们设计的等级方式，与上面提到的剪枝技巧相联系，并且加入空格数n与“回”数m，来共同影响数独的等级变化。先考虑单一变量发生变化：一般我们知道当n增大时，未知的空格多了，数独的难度变大了；当m增大时，已知的条件限制增加了，数独反而变的容易了；此时整合一下n、m，认定一个平均每“回”中填入的个数量p，即 p=nm当p增大，说明每“回”中填入的空格数增多了，难度也随之提升(近似值)时，难度较为适中于是，设定：1.57 难度设为easy1.62 难度设为normal1.69 难度设为hard但是，如果数独中出现了如同剪枝一和剪枝二中的情况时，数独的难度也就降低了。于是，又规定：如果出现类似“回”中的和数只有唯一分解的情况时 p=p-0.05；如果出现两个交叉“回”中的数字可以唯一确定的情况时 p=p-0.1；以上为难度等级的划分c）产生唯一解数独的建模有一种比较大众化的思想，就是先产生一个有可行解的数独，再次搜索除该可行解外的其他解，如果有则不是唯一解的数独，这种方法虽然简单，但极为可行，不过缺乏针对性，并且有一定的偶然性，缺乏目的性。这样，我们将从另一方面去考虑生成的问题：当数独具有唯一解等价于由填入的数所构成的一次线性方程组的解唯一，因此考虑能否构建一个唯一解的一次线性方程组。填入空格中的数位Xi（i=1,2,3，,n）与每一“回”的和Yj(j=1,2,3,m)构成了一次线性方程组：a11X1 + a12X2 + + a1nXn = Y1a21X1 + a22X2 + + a2nXn = Y2 aj1X1 + aj2X2 + + ajnXn = Yj其中aj i=0或1（i=1,2,3，,n；j=1,2,3,m），并且Xi=1,2,3,4,5,6,7,8,9，此时我们需要知道n，m，Yj，随机生成n，m（40n60，20m80-n, 随机的范围为估计值），此时可以生成Yj，限制条件为 min（nm）6j=1mYjmax（nm）24（估算值）生成的基础完成；生成ai j也为一个随机过程，优先级比上面三个变量略低，为0或1；接下来判断生成的方程组存在解和唯一解：用Lingo判断其解的存在非常简单；利用线性代数解线性方程组的思想，判断方程组的解是否唯一。 还需判断这个方程组是否符合数独表（8*10）的容量，即i=1naj i9（j=1,2,3,m）（9得于需要一个格子放置Yj若满足以上条件，所需的方程组就构建完毕；ajpXpajqXq然后，将每个方程看成一个或ajpXpajqXq进行比对，若存在一个相同的数Xi，则构建如下图ajp2Xp2ajp1Xp1Xiajq1Xq1ajq2Xq2依次将方程组所构建的矩形方格放入数独中，如果全部包含，并将Yj放入 中，满足数独的所有条件，则我们的生成数独完成。模型评价及其改进：关于数独的解而言很难做到人脑的思维方式，以致可以从最简单情况入手分析，我们只能尽可能去优化程序思考数独的方式及其恰当的切入点，才能使速度更快，因此我们需要加入更多类人化的思考方式于电脑，建立多种情况的分析；数独的唯一解生成只能算是一种相对可行的思想，因本小组程序调试问题，建立唯一解的一次线性方程组时还存在一些考虑不周，使得生成的数独有所欠缺（所生成的难度一般较小），对玩家而言没有挑战，希望寻求一种优化方法，将产生的方程组的交叉解的个数相对减少，从而产生多种情况，加大数独的难度. z.