1、Kakuro數獨問題092260 周揚092312 童思博問題描述：l 在空格中填入數字1-9，數字0不能出現l 帶斜線的方格，斜線上方的數字等于該方格右面對應的一組水平空格里的數字之和；斜線下方的數字，等于該方格下面對應一組垂直空格里的數字之和l 同一數字在每組水平（垂直）空格里只能出現一次(右圖為一范例)針對Kakuro數獨，完成以下問題：l 討論求解模型或方法,并給出算法復雜性討論.l 如何對Kakuro數獨問題劃分為不同級別，并給出一種劃分方式，并給出實例.l 如何產生不同級別的Kakuro數獨，并保證產生的數獨問題為唯一解。l 假定所有kakuro數獨都以8x10為標準進行討論.問題

2、背景：數謎(Kakuro)   當大家還在鉆研數獨Sudoku，究竟填寫1至9這幾個數字的竅門時，另一個相類的游戲于最近迅速火爆，這就是Kakuro。Kakuro在英美等地人氣急升，它的好玩之處在于既有Sudoku的邏輯推理，還多了加數運算。在空格內選添1-9中一個數字，最終目的使那些數字加起來之和與所給的數字相等。說起來簡單，實際上想在游戲中過關可不是那么容易的。Kakuro相比Sudoku更難玩，除了涉及邏輯推理，更要大家計算加數。與Sudoku一樣，是將一串數字加到面板上，大前提是加入的數字是空格旁邊數字的總和，還有該總和算式內的數字不能重復。玩Kakuro，會用到在

3、小學時期的加數運算法，如要填入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的方格組成，其他剛相同。游戲規則每一道謎題都是實體格和“線索”格的組合，再加上一個個自成一體的

4、空格組。每個空格組，我們稱之為一個“回”，游戲的目的就是在空格中填入1到9等數字，每一回里，相同的數字不能重復出現。 每一行，列的“回”，會先從灰色的線索格開始，它就位在每一回的左邊（就列而言），或上面（就行而言）。每一個回在遇到實體格或線索格就結束了。線索格通常以對角線分成兩半，包含一到兩個數字，一個數字就是一個“提示碼”。斜線上方的提示碼代表該列數字的加總總和；相同的，斜線下方的提示碼則表示在它以下的行回數字的加總總和。不論在行回或列回里，數字都不能重復。舉例來說，4不能拆解成（2，2），只能拆解成（1，3）符號說明 n數獨中需要填入的空格總數 Xi 空格中填入的數（i=1,2,3，n）

5、m數獨中“回”的個數，即一行（列）空格組的組數 Yj 每一個“回”的和（j=1,2,3，m） SUMi 用于判斷其填入數的重復性，設定的初值為45 MULi 作用同上，設定的初值為9!=362880 A 一個二元一唯數組表，作用也是判斷其重復性問題分析：a) 若給出一存在可行解的數獨，最簡單直接的辦法就是將其每個空格設為一個未知元Xi（i=1,2,3，n），利用LINGO的線性規劃功能求解，同時需加上限制條件（同一數字在每組水平（垂直）空格里只能出現一次），但是這個算法的計算量（忽略數字重復的剪枝）高達9n，如范例給出的就為9401.47*1038，顯然我們不能承受如此恐怖的計算量，但這是最為

6、直接、最容易想到的方法。簡化計算量勢在必行。我們可以確定數獨本就為一個搜索類型的題目，當搜索的次數達到一定量時（如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、=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· 4

8、1=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字組只能

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,3max

10、len(A)表示A表的最大長度，每當填入一個數X時，做如下操作： SUMi=SUMi-X MULi=MULi÷X此時若X沒有和規則相違背（即不重復），則SUMi為19中若干個不同數的和，MULi為19中若干個不同數的乘積，兩者為一一對應關系，A表就用來存儲這種對應關系，SUMt和MULt事先存儲好所有可能的情況，出現X后，計算SUMi和MULi與SUMt和MULt比較。如果對應相等，則沒有出現重復；反之，則進行下一個可行解的搜索。然而這個t有多大呢？ 經計算發現A表的長度 tmax=29 ，可以接受。利用上述三個剪枝，完全可以把原本最高達9n的搜索次數，減少至9!次，甚至更少！這是我

11、們用電腦可以輕松搜索出答案的次數。附求解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('kakuro

12、in.txt');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;

13、 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 && j<10, 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)=

14、0; cann=ones(1,9); while type(i+1,j)=0 && i<8, 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 amax=min(9,sum(row(i,j),sum(col(i,j); while data(i,j)<=amax, if canrow(i,j

15、)(data(i,j) | cancol(i,j)(data(i,j), data(i,j)=data(i,j)+1; continue; end if size(row(i,j)=1 && sum(row(i,j)=data(i,j), data(i,j)=data(i,j)+1; continue; end if size(col(i,j)=1 && sum(col(i,j)=data(i,j), data(i,j)=data(i,j)+1; continue; end break; end if data(i,j)>amax, place=0; el

16、se 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

17、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

18、)+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=n÷m當p增大，說明每“回”中填

19、入的空格數增多了，難度也隨之提升經資料和一些數獨的模擬成果，我們計算出當p的平均值約為1.60(近似值)時，難度較為適中于是，設定： p=1.511.57 難度設為easy p=1.581.62 難度設為normal p=1.631.69 難度設為hard但是，如果數獨中出現了如同剪枝一和剪枝二中的情況時，數獨的難度也就降低了。于是，又規定：如果出現類似“回”中的和數只有唯一分解的情況時 p=p-0.05； 如果出現兩個交叉“回”中的數字可以唯一確定的情況時 p=p-0.1；以上為難度等級的劃分c）產生唯一解數獨的建模有一種比較大眾化的思想，就是先產生一個有可行解的數獨，再次搜索除該可行解外的

20、其他解，如果有則不是唯一解的數獨，這種方法雖然簡單，但極為可行，不過缺乏針對性，并且有一定的偶然性，缺乏目的性。這樣，我們將從另一方面去考慮生成的問題：當數獨具有唯一解等價于由填入的數所構成的一次線性方程組的解唯一，因此考慮能否構建一個唯一解的一次線性方程組。填入空格中的數位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（40<n<60，20&