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

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

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

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

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

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

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

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

8、表示，難度為一星，空格數(shù)為50的題目有3道。表1 統(tǒng)計(jì)數(shù)獨(dú)空格數(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)過多次試驗(yàn)與分析，我們初步得到，隨著空格數(shù)的增加，數(shù)獨(dú)的難度系數(shù)也相應(yīng)的增加。為進(jìn)一步探討數(shù)獨(dú)的難易程度是否還與其他因素有關(guān)，我們對(duì)數(shù)獨(dú)題目的統(tǒng)計(jì)表格進(jìn)行處理，在同等難度

9、上，將每種空格的題目個(gè)數(shù)除以該難度的總題目數(shù)，得到如下表格。表2 計(jì)算數(shù)獨(dú)空格率與難度   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），由圖可以清晰看出，難度等級(jí)遞增，空格數(shù)也不斷增加。難度等級(jí)

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

11、但不是唯一的因素。表3 統(tǒng)計(jì)數(shù)獨(dú)-再露鋒芒空格數(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空格自由度的計(jì)算計(jì)算空格自由度的模型如下：6.1.2.3空格自由度模型空格自由度的取值范圍大，當(dāng)數(shù)獨(dú)題目全為0時(shí)，空格的數(shù)為 81，空間自由度為2106；數(shù)獨(dú)題目只剩1個(gè)空格時(shí)，空格自由度為0。在0,2106的范圍內(nèi)平均劃分，將難度級(jí)別劃分為5個(gè)等級(jí)，空格自由度0-420難度等級(jí)為1；421-841為2；842-1262為3；1263-1683為4；1683-2106為5。這與實(shí)際題目的難度劃分不一致?？崭褡杂啥葎澐值膮^(qū)間縮小到700，1300，700，820為1級(jí)，820，940為2級(jí)，940，1060為3級(jí)，1060，1180為4級(jí)，1080，1300為5級(jí)

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

14、，建立幾何難度等級(jí)模型：（1）以數(shù)獨(dú)的空格數(shù)來劃分，將空格數(shù)為橫坐標(biāo)X；（2）將空格自由度的總和劃分等級(jí)，將等級(jí)數(shù)設(shè)為縱坐標(biāo)Y；（3）根據(jù)（X，Y）判定難度。將計(jì)算好的空格數(shù)和空格自由度劃分等級(jí)，兩者結(jié)合，便可得到數(shù)獨(dú)題目的難度等級(jí)了。難度等級(jí)等級(jí)為A-I，A為最易，I為最難，隨著字母變大，難度逐次增加。具體劃分的數(shù)據(jù)如下：圖3 難度判定坐標(biāo) 表5 難度系數(shù)劃分依據(jù) 難度等級(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難度等級(jí)綜合模型的驗(yàn)證為了測(cè)試難度等級(jí)劃分的情況的準(zhǔn)確程度，主要做了如下測(cè)試：（1）測(cè)試的數(shù)獨(dú)題目，查找出自數(shù)獨(dú)和路途中的數(shù)

15、獨(dú)資料表6 測(cè)試題目 題號(hào) 數(shù)獨(dú)題目字符串 難度 1 6097 一星 2 0000 二星 3 0001 二星 4 0500 三星 5 0008 四星 （2）書籍中對(duì)數(shù)獨(dú)難度等級(jí)的劃分，并不一定合理，為了更準(zhǔn)確區(qū)分難度等級(jí)，我們將的題目由3個(gè)人完成，計(jì)算每道數(shù)獨(dú)題目完成需要的平均時(shí)間，完成時(shí)間越長(zhǎng)，數(shù)獨(dú)題目難度越大。測(cè)試結(jié)果如下：表7 測(cè)試結(jié)果 Test result題號(hào) 空格數(shù) 空格自由度 難度 書中難度 完成時(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）實(shí)驗(yàn)結(jié)果表明，劃分的難度與書中所劃分的難度基本一致。以玩家完成數(shù)獨(dú)題目的時(shí)間來判定數(shù)獨(dú)題目的難度的話，那么此種劃分難度等級(jí)的方法也合理。6.2問題二的求解6.2.1 MATLAB編程求解數(shù)獨(dú)6.2.1.1“鏈?zhǔn)酵茖?dǎo)方法”解數(shù)獨(dú)定義 所謂鏈?zhǔn)酵茖?dǎo)方法就是根據(jù)數(shù)獨(dú)題中候選數(shù)的出現(xiàn)關(guān)系或分布規(guī)律來推導(dǎo)，形成一條或多條推導(dǎo)鏈，最后證明某個(gè)或某些候選數(shù)是真或是假的解數(shù)獨(dú)題的方法。 現(xiàn)在能想到的鏈?zhǔn)酵茖?dǎo)方法有： 1、由A證明B為假（由一個(gè)格子的候選數(shù)假設(shè)推導(dǎo)證明另一個(gè)格子里的某個(gè)候選數(shù)是假的方法） 2、由A證明B為真

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

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

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

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

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

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

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

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

25、點(diǎn)a（1,1），為解決回溯越界問題，我們用一系列的if else 語句進(jìn)行約束： j=j-1 else if j=1 j=9; i=i-1 if i=0 i=9 end end需要注意的是，程序回溯的是上一個(gè)未確定的點(diǎn)，而不是上一個(gè)點(diǎn)，因此，在回溯過程中需要進(jìn)行判斷上一點(diǎn)是否已經(jīng)是確定的點(diǎn)。如果a（i,j）確定下來了，則應(yīng)繼續(xù)尋找下一點(diǎn)，此時(shí)又遇到越界問題，容易越界的點(diǎn)是矩陣的最后一個(gè)點(diǎn)a（9，9）和每一行的最后一個(gè)點(diǎn)，我們依然用一系列的if else 語句進(jìn)行限制： 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)回溯，直到所有的點(diǎn)都已經(jīng)確定下來，結(jié)束程序，可得出正確的解。如下表所示：表8 數(shù)獨(dú)游戲終盤結(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)缺點(diǎn)7.1模型優(yōu)點(diǎn)：（1）難度等級(jí)模型引入空格自由度的概念，是模型的創(chuàng)新點(diǎn)；（2）模型對(duì)數(shù)獨(dú)的難度的分類較為直觀；（3）難度等級(jí)的模型可操作性強(qiáng)；（4）難度

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

28、擬.百度文庫.2012-07-21附錄針對(duì)問題二編寫的Matlab程序：function initialA=zeros(9,9);%骨灰級(jí)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%找出九個(gè)小方格所在位置function rr=findrc(row)switch rowcase 1 2 3rr=0;case 4 5 6rr=1;otherwiserr=2;end針對(duì)問題四用matlab編寫數(shù)獨(dú)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);%求出每一點(diǎn)處所在行、列、九宮格處已有的點(diǎn)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(bǔ)(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; %找出一次性能確定的點(diǎn)，不用回溯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;%判斷該矩陣的點(diǎn)是否有解，如果無解，則返回值為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%上一點(diǎn)的候選值改變，如果上一點(diǎn)的候選值只有一個(gè)，則繼續(xù)尋找上一點(diǎn) a(i,j)=choose2i,j(ti,j+1)endend%跳出循環(huán)后繼續(xù)尋找下一點(diǎn) j=j+1;