Kakuro數(shù)獨(dú)問題

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

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

3、小學(xué)時(shí)期的加數(shù)運(yùn)算法，如要填入3個(gè)方格，單是總和9便已經(jīng)有3個(gè)配搭，包括1+2+6、1+3+5、2+3+4；再者，數(shù)字的次序可以不同，這樣便有18個(gè)組合，究竟哪個(gè)才是正確答案，這就是游戲的最困難地方。Kakuro是一款在游戲中需要增加運(yùn)算(加法)的智力游戲，邏輯推理性很強(qiáng)。與數(shù)獨(dú)玩法相近但趣味更豐富、挑戰(zhàn)性更大。Kakuro的玩法與數(shù)獨(dú)相似，有的是由3乘以3的9個(gè)方格組成，每個(gè)方格又分成3乘以3的9格，在空格內(nèi)選添1至9中的一個(gè)數(shù)字，最終目的是使那些數(shù)字加起來(lái)之和與所給出的數(shù)字相等。 也有的是8乘10的方格組成，其他剛相同。游戲規(guī)則每一道謎題都是實(shí)體格和“線索”格的組合，再加上一個(gè)個(gè)自成一體的

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

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

6、直接、最容易想到的方法。簡(jiǎn)化計(jì)算量勢(shì)在必行。我們可以確定數(shù)獨(dú)本就為一個(gè)搜索類型的題目，當(dāng)搜索的次數(shù)達(dá)到一定量時(shí)（如9n）必然可以求出答案（若沒有答案，則不存在可行解）！因此，我們需要更多的剪枝來(lái)優(yōu)化搜索的次數(shù)。1）技巧性的剪枝一：唯一分解方式數(shù)和中有些和值只有一種分解方式。2字組的優(yōu)化：92A223字組的優(yōu)化：93A33依此類推：9nAnn（n=1,2,3,9）簡(jiǎn)化效率非常的客觀！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字組中每一個(gè)和值都有唯一解。9字組由于組內(nèi)數(shù)字不能重復(fù)，9字組只能

9、是1-9各填一遍，和值只能是45。2）技巧性的剪枝二：重疊組重疊組在數(shù)和中有很重要的作用，當(dāng)重疊的兩個(gè)組都是唯一解時(shí)就更為尤甚。這種情況常常用來(lái)做解題的突破口。以上文的題目為例（是第1行第1列）：2316由于23=9+8+6和16=9+7都是唯一解，中就必定填它們的共有數(shù)字：9。還有一種情況，兩個(gè)組中有一個(gè)是唯一解，另一個(gè)可以通過(guò)推理進(jìn)行排除從而得到唯一解。還以上文的題目為例（是第4行第2列）：3030=9+8+7+6是唯一解。但是與它重疊的組和值為7，不可能填入7或比7大的數(shù)，所以中必定填6。 3）重復(fù)性的剪枝 首先我們需要建立一唯表A，A中二元分別為SUMt和MULt，t=1,2,3max

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

11、們用電腦可以輕松搜索出答案的次數(shù)。附求解kakuro數(shù)獨(dú)程序MATLAB：type=;data=;row=;col=;can=;sum=;size=;%設(shè)置變量%type 表示每個(gè)坐標(biāo)的類型：0表示待填，1表示不填，2表示限制，3表示已填%data 表示每個(gè)坐標(biāo)的數(shù)據(jù)值：對(duì)限制值，高兩位表示列限制，低兩位表示行限制；對(duì)空格，即表示填寫值%row 表示行限制值標(biāo)號(hào)%col 表示列限制值標(biāo)號(hào)%can 表示每個(gè)限制下，1.9能否填入，用0-1表示，1表能填，0表不能%sum 表示每個(gè)限制的剩余值，即原限制值減去已填數(shù)后的值%size 表示每個(gè)限制下待填數(shù)個(gè)數(shù)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數(shù)據(jù)，并對(duì)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 %初始化每個(gè)限制值的信息，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，在空格內(nèi)填數(shù)，并減小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，清空某空格中已填數(shù)的狀態(tài)，增加size和sum的值 data(i,j)=data(i,j)+1; endend%程序主體，完成回溯算法b) 劃分?jǐn)?shù)獨(dú)的等級(jí) 劃分等級(jí)的方式多種多樣。在此，我們?cè)O(shè)計(jì)的等級(jí)方式，與上面提到的剪枝技巧相聯(lián)系，并且加入空格數(shù)n與“回”數(shù)m，來(lái)共同影響數(shù)獨(dú)的等級(jí)變化。先考慮單一變量發(fā)生變化：一般我們知道當(dāng)n增大時(shí)，未知的空格多了，數(shù)獨(dú)的難度變大了；當(dāng)m增大時(shí)，已知的條件限制增加了，數(shù)獨(dú)反而變的容易了；此時(shí)整合一下n、m，認(rèn)定一個(gè)平均每“回”中填入的個(gè)數(shù)量p，即 p=n÷m當(dāng)p增大，說(shuō)明每“回”中填

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

20、其他解，如果有則不是唯一解的數(shù)獨(dú)，這種方法雖然簡(jiǎn)單，但極為可行，不過(guò)缺乏針對(duì)性，并且有一定的偶然性，缺乏目的性。這樣，我們將從另一方面去考慮生成的問題：當(dāng)數(shù)獨(dú)具有唯一解等價(jià)于由填入的數(shù)所構(gòu)成的一次線性方程組的解唯一，因此考慮能否構(gòu)建一個(gè)唯一解的一次線性方程組。填入空格中的數(shù)位Xi（i=1,2,3，,n）與每一“回”的和Yj(j=1,2,3,m)構(gòu)成了一次線性方程組：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，此時(shí)我們需要知道n，m，Yj，隨機(jī)生成n，m（40<n<60，20&