數(shù)獨中的數(shù)學(xué)模型(共25頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)獨中的數(shù)學(xué)模型摘要現(xiàn)如今數(shù)獨游戲風靡全球，深受人們喜愛。其難度等級多樣，求解數(shù)獨難度等級較高的常常需要花費大量的時間和精力，因此我們試圖用計算機來解決這一問題。在問題一中，我們主要考慮空格數(shù)的多少以及空格自由度與數(shù)獨難度等級的關(guān)系。由一定的案例分析得出數(shù)獨題目的難度等級與空格數(shù)存在正比關(guān)系，接著我們考慮如果只是簡單的按照空格的數(shù)目多少來劃分數(shù)獨題目的難易程度是不全面的，因此繼續(xù)分析，得出空格自由度與數(shù)獨的難度等級存在正比的關(guān)系，最后又以空格數(shù)和空格自由度綜合分析進行驗證，得出此數(shù)獨等級為3級。1 空格自由度法模型如下： 在問題二中，我們運用窮舉法分析大量可能情況，再

2、用MATLAB編寫程序得出此數(shù)獨游戲的終盤。在問題三中，我們運用了比較排除法、唯一解法和綜合法來求解此數(shù)獨游戲，最終選用綜合法作為較優(yōu)方法。1 在問題四中，我們用循環(huán)回溯法進行求解，使用MATLAB編寫程序得出結(jié)果（見表8）。1 關(guān)鍵字：窮舉法 比較排除法 唯一解法 循環(huán)回溯法 數(shù)獨 空格數(shù) 空格自由度一、問題背景 數(shù)獨是一種數(shù)字解謎游戲，英文名叫Sudoku，前身為“九宮格”，當時的算法比現(xiàn)在的更為復(fù)雜，要求縱向、橫向、斜向上的三數(shù)之和等于15，而不只是數(shù)字的不能重復(fù)，儒家典籍易經(jīng)中的“九宮圖”也是來源于此。關(guān)于它的起源一直存有爭議，有人認為最早起源于中國，也有人認為起源于瑞士。1970年由

3、美國一家數(shù)學(xué)邏輯游戲雜志首先發(fā)表，名為Number。后在日本流行，于1984年把Sudoku取名為數(shù)獨。數(shù)獨全面考驗做題者觀察能力和邏輯推理能力，它的玩法邏輯簡單，除了1到9的阿拉伯數(shù)字以外，不必用到任何東西，但數(shù)字的排列方式卻又千變?nèi)f化，不少教育者認為，數(shù)獨是鍛煉大腦的絕佳方式。它不僅具有很強的趣味性，也是一種對智慧和毅力的考驗。二、問題重述 芬蘭一位數(shù)學(xué)家號稱設(shè)計出全球最難的“數(shù)獨游戲”，并刊登在報紙上，讓大家去挑戰(zhàn)。這位數(shù)學(xué)家說，他相信只有“智慧最頂尖”的人才有可能破解這個 “數(shù)獨之謎”。所給數(shù)獨游戲表格如下： 據(jù)介紹，目前，數(shù)獨游戲難度的等級有一到五級，一是入門等級，五則比較難。不過這

4、位數(shù)學(xué)家說，他所設(shè)計的數(shù)獨游戲難度等級是十一，可以說是所有數(shù)獨游戲中，難度最高的等級。數(shù)獨是根據(jù)9×9盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個粗線宮內(nèi)的數(shù)字均含1-9，不重復(fù)。 每一道合格的數(shù)獨謎題都有且僅有唯一答案，推理方法也以此為基礎(chǔ)，任何無解或多解的題目都是不合格的。由此我們要解決以下問題：問題一： 分析此數(shù)獨的難度；問題二： 用窮舉算法求解數(shù)獨；問題三： 設(shè)計此數(shù)獨求解的較優(yōu)的算法；問題四： 建立數(shù)獨求解模型并給出此數(shù)獨的答案。三、問題分析根據(jù)題中所給信息我們知道數(shù)獨是一種數(shù)字解謎游戲，要求游戲者有很好的觀察能力和邏輯推理能力。針對問題一：分析

5、此數(shù)獨難度，我們認為有兩點因素：一、空格數(shù)的多少，二、空間自由度。因此我們采取例證法進行分析，根據(jù)空格數(shù)來劃分等級，進行一定的數(shù)據(jù)分析求出空格率，進而得出難度系數(shù)與空格數(shù)的關(guān)系。數(shù)獨的難度等級與行、列、宮格內(nèi)的空格數(shù)存在著密切聯(lián)系，所以數(shù)獨難易程度還與空間自由度有關(guān)。數(shù)獨的空格自由度，指除掉空格本身，空格所在行、列、九宮內(nèi)的空格數(shù)總和。除此之外我們可以以玩家完成數(shù)獨題目的時間來判定數(shù)獨題目的難度。針對問題二： “窮舉法”是指當一個問題有幾種可能而一時難以判定時,把幾種可能一一列舉出來,然后逐一嘗試，直到嘗試結(jié)果與給定的條件和結(jié)論相符為止。這種方法一般在計算機中運用，因為計算機計算速度快，可以很

6、快驗證答案是否正確，所以我們就以此來分析所有可能情況得出最終結(jié)果。針對問題三：為了找出更好的數(shù)獨解法，我們運用了三種方法來求解。分別是：比較排除法、唯一解法和綜合法。分析比較，選出較優(yōu)方案。針對問題四：我們選用循環(huán)回溯法進行分析求解，與問題三中所求結(jié)果對比，以此驗證其準確性。四、模型假設(shè)1、假設(shè)每種數(shù)獨游戲都存在一定的聯(lián)系且相互之間的難易程度成一定的比例；2、假設(shè)實驗者水平相同，隨著實驗不斷進行，完成數(shù)獨題目熟練程度不會增加； 3、假設(shè)實驗者數(shù)獨時間與數(shù)獨題目難度無關(guān)。五、符號說明N數(shù)獨的空格數(shù)目F所有空格的自由度的總和S(i,j)數(shù)獨矩陣A(9*9)中i行j列的空格自由度S(i)i行的空格數(shù)

7、目S(j)j行的空格數(shù)目gi除去同行同列的同一宮中的空格數(shù)六、模型建立與求解61問題一的求解6.1.1空格數(shù)與難度等級6.1.1.1難度等級劃分為了更好的區(qū)分難易程度我們將數(shù)獨以空格數(shù)劃分為五個等級，具體劃分如下：空格數(shù)的取值范圍為0-81，以空格數(shù)來平均劃分難度等級，將空格數(shù)平均分成5個類型，空格數(shù)的取值范圍縮小到37-81。劃分等級如下表所示：37-4546-5455-6364-7273-811級2級3級4級5級6.1.1.2實例分析以數(shù)獨為例，我們得到一些數(shù)據(jù)。數(shù)獨題目數(shù)為100道，表格行表示空格的個數(shù)，列表示難度的級別，一星為最容易，二星為容易，三星為難，四星為最難。例如：表一的首格3

8、表示，難度為一星，空格數(shù)為50的題目有3道。表1 統(tǒng)計數(shù)獨空格數(shù)與難度  50 51 52 53 56 57 58 總數(shù) 一星 3 1           4 二星 1 1 21 1 1     25 三星       35 11 46 四星         14 8 325 經(jīng)過多次試驗與分析，我們初步得到，隨著空格數(shù)的增加，數(shù)獨的難度系數(shù)也相應(yīng)的增加。為進一步探討數(shù)獨的難易程度是否還與其他因素有關(guān)，我們對數(shù)獨題目的統(tǒng)計表格進行處理，在同等難度

9、上，將每種空格的題目個數(shù)除以該難度的總題目數(shù)，得到如下表格。表2 計算數(shù)獨空格率與難度   50 51 52 53 56 57 58 一星 0.75 0.25           二星 0.04 0.04 0.84 0.04 0.04     三星         0.76 0.24   四星         0.56 0.32 0.12 表格的數(shù)據(jù)用圖表表示（圖1），由圖可以清晰看出，難度等級遞增，空格數(shù)也不斷增加。難度等級

10、與空格數(shù)存在正比的關(guān)系。圖1 數(shù)獨空格數(shù)與難度 經(jīng)過我們的多次試驗與分析，我們初步得到，隨著空格數(shù)的增加，數(shù)獨的難度系數(shù)也相應(yīng)的增加，當然數(shù)獨題目的難度等級與空格數(shù)存在正比關(guān)系。難度等級的增加，空格數(shù)總體趨勢遞增，不同難度等級的題目空格數(shù)也一樣的情況。6.1.2空格自由度與難度等級6.1.2.1數(shù)獨難度的進一步分析數(shù)獨題目的難度等級與空格數(shù)存在正比關(guān)系。難度等級的增加，空格數(shù)總體趨勢遞增，不同難度等級的題目空格數(shù)也一樣的情況。我們得出初步結(jié)論，簡單按照空格的數(shù)目多少來劃分數(shù)獨題目的難易程度是不全面的。同樣空格數(shù)的數(shù)獨題目，空格數(shù)分布位置的不同對難度等級也造成影響。注:格數(shù)是決定難度等級的因素，

11、但不是唯一的因素。表3 統(tǒng)計數(shù)獨-再露鋒芒空格數(shù)與難度   45 47 49 51 52 53 54 55 56 57 總數(shù) 一星 3 1 1   1 1 2 1     10 二星       1 2 9 3 2 1   18 三星     2 1   22 8 5 2   40 四星       1   4 1 1 1 6 15 五星              

12、1 3 6 10 6.1.2.2空格自由度的計算計算空格自由度的模型如下：6.1.2.3空格自由度模型空格自由度的取值范圍大，當數(shù)獨題目全為0時，空格的數(shù)為 81，空間自由度為2106；數(shù)獨題目只剩1個空格時，空格自由度為0。在0,2106的范圍內(nèi)平均劃分，將難度級別劃分為5個等級，空格自由度0-420難度等級為1；421-841為2；842-1262為3；1263-1683為4；1683-2106為5。這與實際題目的難度劃分不一致?？崭褡杂啥葎澐值膮^(qū)間縮小到700，1300，700，820為1級，820，940為2級，940，1060為3級，1060，1180為4級，1080，1300為5級

13、（圖2）。圖2 空格自由度難度模型6.1.2.4空格自由度模型合理性驗證隨機抽取數(shù)獨書籍不同難度等級的題目，進行空格自由度的計算，驗證空格自由度衡量數(shù)獨題目的難度是否合理，首先抽取4道不同難度的數(shù)獨題目，將題目轉(zhuǎn)換為字符串，計算空格自由度，實驗結(jié)果如下：表4 實驗數(shù)據(jù)  數(shù)獨題目空格自由度難度書難度100008202220001880323050010084340008105444由實驗結(jié)果看出空格自由度與數(shù)獨的難度等級存在正比的關(guān)系，難度系數(shù)的劃分合理，與書中的劃分基本一致。6.1.3難度等級綜合模型6.1.3.1難度等級綜合模型的建立數(shù)獨題目的難度等級由空格數(shù)與空格自由度綜合決定

14、，建立幾何難度等級模型：（1）以數(shù)獨的空格數(shù)來劃分，將空格數(shù)為橫坐標X；（2）將空格自由度的總和劃分等級，將等級數(shù)設(shè)為縱坐標Y；（3）根據(jù)（X，Y）判定難度。將計算好的空格數(shù)和空格自由度劃分等級，兩者結(jié)合，便可得到數(shù)獨題目的難度等級了。難度等級等級為A-I，A為最易，I為最難，隨著字母變大，難度逐次增加。具體劃分的數(shù)據(jù)如下：圖3 難度判定坐標 表5 難度系數(shù)劃分依據(jù) 難度等級 A B C D E F G H I X+Y 2 3 4 5 6 7 8 9 10 6.1.3.2難度等級綜合模型的驗證為了測試難度等級劃分的情況的準確程度，主要做了如下測試：（1）測試的數(shù)獨題目，查找出自數(shù)獨和路途中的數(shù)

15、獨資料表6 測試題目 題號 數(shù)獨題目字符串 難度 1 6097 一星 2 0000 二星 3 0001 二星 4 0500 三星 5 0008 四星 （2）書籍中對數(shù)獨難度等級的劃分，并不一定合理，為了更準確區(qū)分難度等級，我們將的題目由3個人完成，計算每道數(shù)獨題目完成需要的平均時間，完成時間越長，數(shù)獨題目難度越大。測試結(jié)果如下：表7 測試結(jié)果 Test result題號 空格數(shù) 空格自由度 難度 書中難度 完成時間 是否相符 1 45 698 A 一星 16min23s 是 2 53 922 E 二星 18min29s 是 3 52 880 E 二星 17min28s 是 4 56 1008

16、G 三星 20min39s 是 5 57 1054 G 四星 29min57s 否 （3）實驗結(jié)果表明，劃分的難度與書中所劃分的難度基本一致。以玩家完成數(shù)獨題目的時間來判定數(shù)獨題目的難度的話，那么此種劃分難度等級的方法也合理。6.2問題二的求解6.2.1 MATLAB編程求解數(shù)獨6.2.1.1“鏈式推導(dǎo)方法”解數(shù)獨定義 所謂鏈式推導(dǎo)方法就是根據(jù)數(shù)獨題中候選數(shù)的出現(xiàn)關(guān)系或分布規(guī)律來推導(dǎo)，形成一條或多條推導(dǎo)鏈，最后證明某個或某些候選數(shù)是真或是假的解數(shù)獨題的方法。 現(xiàn)在能想到的鏈式推導(dǎo)方法有： 1、由A證明B為假（由一個格子的候選數(shù)假設(shè)推導(dǎo)證明另一個格子里的某個候選數(shù)是假的方法） 2、由A證明B為真

17、（由一個格子的候選數(shù)假設(shè)證明另一個格子的某個候選數(shù)是真的方法） 3、由A證明A為假（由某個候選數(shù)推導(dǎo)而出現(xiàn)錯誤證明本身假設(shè)是錯的方法） 4、與成名方法結(jié)合的鏈式推導(dǎo) 5、還有 如何推導(dǎo)，先定義一下，所說的A、B、C、a、b、c等等，都是候選數(shù)在某格子位置的代號。箭頭“->”是“導(dǎo)致”或“因此”的意思；“=”是等于，“<>”是不等于的意思；A=1->B=2->C=3的意思是：當A是1時，導(dǎo)致B等于2，B等于2因此C就等于3，余下類推；A=1->B<>1->的意思就是當A是1時，B就不是1，余類推；“同一單元”的概念是指同一行或同一列或同一九宮

18、格。6.3問題三的求解6.3.1排除法原理求解數(shù)獨由于數(shù)獨規(guī)則要求每行、每列和每宮的數(shù)字不重復(fù)，所以已出現(xiàn)的數(shù)字可以排除掉同行、同列、同宮中的其他單元格內(nèi)再填入該數(shù)字的可能性，以下我們用兩個截圖解釋。比較排除法流程圖如下：與所在小九宮格已知量比較，排除取值域與之重疊的值 與所在小九宮格已知量比較，排除取值域與之重疊的值 與所在小九宮格已知量比較，排除取值域與之重疊的值 取值域可能值的個數(shù)=1？ 所有格完成？ 判斷所在格是否為空？ 賦值 下一格 Y n n Y n 正確結(jié)果排除法的模型優(yōu)點是步步為營，謹慎小心，出錯率不大。但其推算過程較復(fù)雜，編程水平要求很高，所以不適合解答本題。6.3.2唯一解

19、法當某行已填數(shù)字的宮格達到8個,那么該行剩余宮格能填的數(shù)字就只剩下那個還沒出現(xiàn)過的數(shù)字了，成為行唯一解。 當某列已填數(shù)字的宮格達到8個,那么該列剩余宮格能填的數(shù)字就只剩下那個還沒出現(xiàn)過的數(shù)字了，成為列唯一解。 當某九宮格已填數(shù)字的宮格達到8個,那么該九宮格剩余宮格能填的數(shù)字就只剩下那個還沒出現(xiàn)過的數(shù)字了，成為九宮格唯一解。以下我們用一個例子來簡單的介紹這種算法：A行已經(jīng)添入8個數(shù)字,A行只有數(shù)字3沒有出現(xiàn)過,所以A9=3,這是行唯一解第1列已經(jīng)添入8個數(shù)字,第1列只有數(shù)字5沒有出現(xiàn)過,所以E1=5,這是列唯一解在A8所在九宮格區(qū)域已經(jīng)添入8個數(shù)字,只有數(shù)字9沒有出現(xiàn)過,所以A8=9,這是九宮格

20、唯一解唯一解法實施起來比較簡單，但就是因為簡單所以只能應(yīng)用于較簡單的數(shù)獨游戲中或者是用于較難數(shù)獨游戲題型中的最后階段，所以唯一解法的模型也不適合解答本題。6.3.3綜合法我們借鑒了數(shù)獨游戲算法中幾種算法的思想，進行歸納最后定義為綜合法，其算法的步驟如下：1、將所有未確定的格子的可能性定義為0xFFFF（即所有數(shù)字都可能），可能數(shù)目為9。2、尋找所有確定的格子A（可能數(shù)目為0），在所有與A同行、同列和同區(qū)域的未確定的格子的可能性中減去與A相同的可能性。例如：A確定為9，則與A同行、同列和同區(qū)域（區(qū)域標志相同）的未確定的格子的可能性與0xFEFF按位與（除去可能性9），并將其可能性數(shù)目減少。在除去

21、可能性的過程中如果發(fā)現(xiàn)某個格子B的可能性數(shù)目由1減小為0，說明B和A只能取相同的數(shù)字，這可能是題目本身無解引起，也肯能是由于步驟3中搜索方向不對引起的，可認為此方向的搜索無解，退出這一方向的搜索。定義這個檢查為唯一性檢查。3、尋找所有未確定格子中可能性數(shù)目最少的格子M，如果M的可能性數(shù)目為1，則確定M：將M的可能性數(shù)目定義為0，并把確定數(shù)量加1，如果此時確定數(shù)量達到81，則報告找到解，否則，在所有與M同行、同列和同區(qū)域的未確定的格子的可能性中減去與M相同的可能性，并進行唯一性檢查。然后重復(fù)步驟3。如果M的可能性大于1，則把M假設(shè)為所有M的可能性，分多個方向進行搜索，在每一個搜索方向重復(fù)步驟3（

22、這個可以用遞歸來實現(xiàn)）。6.4問題四的求解在比較排除法、唯一解法的基礎(chǔ)上，我們對模型進行深化，提出了循環(huán)回溯模型。其回溯法求解數(shù)獨步驟如下：1） 按下標sp由小到大的順序逐個獲取空白位置；2） 對空白位置sp試圖填數(shù)，填數(shù)的規(guī)律為從1-9依次由小到大選擇（有序）；3） 若找到一個可以填入的數(shù)據(jù)，將數(shù)據(jù)填入數(shù)獨sp，并將sp入棧push否則轉(zhuǎn)5）；4） 獲取下一個空白位置，若有空白位置則轉(zhuǎn)2），否則轉(zhuǎn)6）；5） 因為check(sp)返回1），找不到合適數(shù)據(jù)填入該位置，進行回溯，即pop得到上一次填數(shù)的位置sp,重新對該位置試圖填數(shù)，且為了遞推的高效性，此時可以僅從當前sp存放的數(shù)字大于1開始試

23、圖填充，轉(zhuǎn)3）；6） 填數(shù)結(jié)束?；厮莘鞒虉D如下：判斷a是否全部確定 a(i,j)是 否確定 第一個候選值給a(i,j) 更新a 是否 矛盾 是否是最后候選值 下一個候選值 回溯到上一點 尋找下一點 結(jié)束循環(huán)，輸出a 否 是 否 是 否 是 否 是 模型的整個函數(shù)體在while(isempty 1(a)的循環(huán)體中，只有當a得所有點全部確定下來后，該循環(huán)才終止。我們是從矩陣的第一個元素開始循環(huán)的，首先判斷a（i,j）是否確定，如果確定，則判斷下一個點，如果a（i,j）沒有確定，則把a（i,j）的第一個候選值賦給它，并用firstsolve()更新a100次，如果出現(xiàn)矛盾，即isright（a）=

24、0，則說明第一個候選值錯誤，此時要把下一個候選值賦值給a（i,j），由于不同的a（i,j）的候選值下標是不同的，為此，需要指針表達這種關(guān)系，于是我們定義了一個新的細胞數(shù)組t=cell（9，9），用ti,j表示a（i,j）的候選值下標，并用語句：for ii=1:9 for jj=1:9 t=ii,jj=1; endend把ti,j的值初始化為1，以后循環(huán)中依次加1即可。當a（i,j）的所有候選值都嘗試過后依然出現(xiàn)矛盾（isright（a）=0），則應(yīng)該回溯到上一點，讓上一點取下一個候選值，同時讓當前點清空?；厮莸臅r候容易出現(xiàn)的問題是發(fā)生越界，最容易發(fā)生的越界的點為每一行的第一個點和矩陣的第一個

25、點a（1,1），為解決回溯越界問題，我們用一系列的if else 語句進行約束： j=j-1 else if j=1 j=9; i=i-1 if i=0 i=9 end end需要注意的是，程序回溯的是上一個未確定的點，而不是上一個點，因此，在回溯過程中需要進行判斷上一點是否已經(jīng)是確定的點。如果a（i,j）確定下來了，則應(yīng)繼續(xù)尋找下一點，此時又遇到越界問題，容易越界的點是矩陣的最后一個點a（9，9）和每一行的最后一個點，我們依然用一系列的if else 語句進行限制： j=j+1;if j=10 i=i+1; i=1; if i=10&&j=10 i=1; j=1; enden

26、d這樣，通過循環(huán)回溯，直到所有的點都已經(jīng)確定下來，結(jié)束程序，可得出正確的解。如下表所示：表8 數(shù)獨游戲終盤結(jié)果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 8 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 七、模型優(yōu)缺點7.1模型優(yōu)點：（1）難度等級模型引入空格自由度的概念，是模型的創(chuàng)新點；（2）模型對數(shù)獨的難度的分類較為直觀；（3）難度等級的模型可操作性強；（4）難度

27、模型計算的難度等級符合現(xiàn)實的等級劃分。7.2模型缺點：（1）模型所劃分難度等級的區(qū)域過大，在實際題目中，數(shù)獨的空格數(shù)往往較為集中在20-40中，研究的范圍較大，劃分的難度等級準確性低，主觀成分過強；（2）實驗數(shù)據(jù)分析過程中，默認數(shù)獨書籍對難度等級的劃分為合理，這個前提存在不準確的可能，因為書籍中的難度等級劃分，可能滲入編者個人的主觀意識，筆者在研究過程中，沒有剔除該種可能，也存在著不足；（3）模型建立忽視數(shù)獨題目所提供的數(shù)字不同，導(dǎo)致數(shù)獨題目難度不一致的可能。參考文獻1劉彬，劉丹彤，王倩倩.數(shù)學(xué)軟件（2）課程設(shè)計.百度文庫.2012-07-212MonkeyDove.數(shù)學(xué)建模與數(shù)學(xué)實驗計算機模

28、擬.百度文庫.2012-07-21附錄針對問題二編寫的Matlab程序：function initialA=zeros(9,9);%骨灰級A(1,1 2 6 8)=2 4 5 8;A(2,1 3 5 8)=8 9 3 5;A(3,7)=3;A(4,3 6 8 9)=4 9 1 5;A(6,1 2 4 7)=3 9 8 2;A(7,3)=1;A(8,2 5 7 9)=2 9 7 3; A(9,2 4 8 9)=3 7 6 2;disp('the inital condition is : ')A %顯示初始值 main(A);load result disp('the r

29、esult is : ')Aend%function main(A)if isempty(find(A=0)=1save result Areturn;endi,j,P=findmp(A);if length(P)=0return;elsefor k=1:length(P)A(i,j)=P(k);main(A);endendend%找出可能元素最小的格子及其可能元素function i,j,P=findmp(A)temp=zeros(9,9);temp(A>0)=10;for row=1:9for col=1:9if A(row,col)=0r=A(row,; r=r(r>

30、0); c=A(:,col); c=c(c>0);rc1=and_log(r,c);%行列不同元素放在rc中rr=findrc(row);cc=findrc(col);rc2=reshape(A(rr*3+1:rr*3+3,cc*3+1:cc*3+3),1,9);rc2=rc2(rc2>0);total=and_log(rc1,rc2);temp(row,col)=9-length(total); endendendv,i=min(temp);v,j=min(v);i=i(j);row=i;col=j; %以下找出可能元素r=A(row,; r=r(r>0); c=A(:,c

31、ol); c=c(c>0);rc1=and_log(r,c);rr=findrc(row);cc=findrc(col);rc2=reshape(A(rr*3+1:rr*3+3,cc*3+1:cc*3+3),1,9);rc2=rc2(rc2>0);total=and_log(rc1,rc2);P=;for kkk=9:-1:1if isempty(find(total=kkk)=1P=P,kkk;endendend%集合AB求和function c=and_log(a,b)c=a;for i=1:length(b)log=0;for j=1:length(a)if b(i)=a(j

32、)log=1;break;endendif log=0c=c,b(i);endendend%找出九個小方格所在位置function rr=findrc(row)switch rowcase 1 2 3rr=0;case 4 5 6rr=1;otherwiserr=2;end針對問題四用matlab編寫數(shù)獨9*9的程序：function y=choose1(a)y=cell(9,9);choose=cell(9,9);select=1,2,3,4,5,6,7,8,9;save=cell(9,9);grid=cell(3,3);templ=a (1:3,1:3);grid1,1=temp1(tem

33、p1>0);temp2=a(1:3,4:6);grid1,2=temp2(temp2>0);temp3=a(1:3,7:9);grid1,3=temp3(temp3>0);temp4=a(4:6,1:3);grid2,1=temp4(temp4>0);temp5=a(4:6,4:6);grid2,2=temp5(temp5>0);temp6=a(4:6,7:9);grid2,3=temp6(temp6>0);temp7=a(7:9,1:3);grid3,1=temp7(temp7>0);temp8=a(7:9,4:6);grid3,2=temp8(te

34、mo8>0);temp9=a(7:9,7:9);grid3,3=temp9(temp9>0);%求出每一點處所在行、列、九宮格處已有的點for i=1:9 for i=1:9 if a(i,j)=0 n1=find(a(i,:>0); N1=a(I,n1); n2=find(a(:,j)>0); N2=a(n2，j);N2=N2;aaa=N1,N2;%把a(i,j)所在行、列、九宮格已確定的數(shù)字合并 if i>=1&&i<=j&&j<=3 aaa=aaa,grid1,1; else if i>=1&&

35、;i<=3&&j>=4&&j<=6 aaa=aaa,grid1,2; else if i>1&&i<=3&&j>=7&&j<=9 aaa=aaa,grid2,1; else if i>=4&&i<=6&&j>=4&&j<=6 aaa=aaa,grid2,2; else if i>=4&&i<=6&&j>=7&&j<=9 aaa=aa

36、a,grid2,3; else if i>=7&&i<=9&&j>=1&&j<=3 aaa=aaa,grid3,1; else if i>=7&&i<=9&&j>=4&&j<=6 aaa=aaa,grid3,2; else if i>=7&&i<=9&&j>=7&&j<=9 aaa=aaa,grid3,3; endendendendendendendendend aaa=uniqu

37、e(aaa); savei,j=aaa; endendend%求出每一處的候選數(shù)字for i=1:9 for j=1:9 n=; if a(i,j)=0 choosei,j=a(i,j); else if a(i,j)=0 temp=select; for t=1:length(save:i,j) n(t)=find(temp=savei,j(t); temp(n(t)=; end choosei,j=temp; endendendendy=choose; %找出一次性能確定的點，不用回溯function y=firstsolve(a)choose2=choose1(a);a1=;for i=

38、1:9 for j=1:9 if length(choose2i,j)=1; a1(i,j)=choose2i,j; else contine end endenda=a1;y=a;%判斷舉證元素是否全部確定，如果確定，返回0，否則返回1function y=isempty1(a)choose2=choose1(a);tempp=0;for i=1:9 for j=1:9 if length(choose2i,j)>1|a(i,j)=0 tempp=1; end endendy=tempp;%判斷該矩陣的點是否有解，如果無解，則返回值為0，否則返回值為1function y=isrigh

39、t(a)choose2=choose1(a);tempp=1;for i=1:9 for j=1:9 if length(choose1i,j)=0 tempp=0; endendendy=tempp;%function y=sudu_solve(a)i=1;j=1;choose2=choose1(a);t=cell(9,9);for ii=1:9 for jj=1:9 t=ii,jj=1; endendwhile isempty1(a) if a(i,j)=0while ti,j<=length(choose2i,j) a(i,j)=choose2i,j(ti,j);for isrig

40、ht(a)=1 breakelse if isright(a)=0 ti,j=ti,j+1; if ti,j>=length(choose2i,j) ti,j= length(choose2i,j);end a(i,j)=choose2i,j(ti,j); endendend%if isright(a)=0 a(i,j)=0; if j>1 j=j-1; else if j=1 j=9; i=i-1; if i=0 i=9 endendendif length(choose2i,j)=1 if j>1 j=j-1;else if j=1 j=9; i=i-1; if i=0 i=9;endendendElse%上一點的候選值改變，如果上一點的候選值只有一個，則繼續(xù)尋找上一點 a(i,j)=choose2i,j(ti,j+1)endend%跳出循環(huán)后繼續(xù)尋找下一點 j=j+1;