數(shù)獨(dú)問題數(shù)學(xué)建模

1、數(shù)獨(dú)問題摘要本文是對數(shù)獨(dú)問題進(jìn)行求解。結(jié)合數(shù)獨(dú)生成的特點(diǎn)，立足于題中數(shù)獨(dú)建模和 求解的要求，建立了數(shù)獨(dú)難度分析 WNF ?函數(shù)和整數(shù)規(guī)劃模型。對于問題一，首先研究數(shù)獨(dú)難度的影響因素，通過綜合分析數(shù)獨(dú)的特點(diǎn)結(jié)構(gòu)， 得出WNF P可以在常數(shù)時間內(nèi)計算出來以衡量數(shù)獨(dú)的難易程度。 通過計算可知WNF ? =0.04531,根據(jù)數(shù)獨(dú)難度的劃分得到如下結(jié)論：數(shù)獨(dú)難度系數(shù)為4, 達(dá)到了極難的程度對于問題二，我們通過對此數(shù)獨(dú)的分析和討論，利用窮舉法，通過matlab軟件編程求解，最終得出答案，如表 1所示。對于問題三，我們利用回溯法思想，建立求解模型，具體算法一般采用如下 步驟:1) .在此數(shù)獨(dú)初盤選擇一個空

2、單元格；2) .取這個單元格中一個可能的候選數(shù);3) .將這個候選數(shù)填入單元格中，迭代完成數(shù)獨(dú)；4) .若這個候選數(shù)推導(dǎo)得到一個無效數(shù)獨(dú)終盤， 返回此單元格取其他候選數(shù)；對于問題四采用整數(shù)規(guī)劃模型，采用三維0-1變量的方法，運(yùn)用lingo軟件編程求解。最終得到答案，如表1所示。關(guān)鍵詞：數(shù)獨(dú)表1數(shù)獨(dú)問題的唯一解11問題的重述前段時間芬蘭一位數(shù)學(xué)家號稱設(shè)計出全球最難的“數(shù)獨(dú)游戲”，并刊登在報紙上，讓大家去挑戰(zhàn)。該數(shù)獨(dú)如下圖所示：數(shù)獨(dú)是根據(jù)9X9盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個粗線宮內(nèi)的數(shù)字均含1-9，且不重復(fù)。 每一道合格的數(shù)獨(dú)謎題都有且僅有唯一答案，推理方

3、法也以此為基礎(chǔ)，任何無解或多解的題目 都是不合格的。根據(jù)以上描述，試完成以下問題：1. 分析此數(shù)獨(dú)的難度；2. 用窮舉算法求解數(shù)獨(dú)；3. 設(shè)計此數(shù)獨(dú)求解的較優(yōu)的算法；4. 建立數(shù)獨(dú)求解模型并給出此數(shù)獨(dú)的答案。2模型的基本假設(shè)1該數(shù)獨(dú)問題存在唯一解。3符號說明x?表示空單元格候選數(shù)W（n ）表示候選數(shù)數(shù)|X?的加權(quán)函數(shù)5工表示數(shù)獨(dú)空單元格中的候選數(shù)數(shù)目函數(shù)E（p）表示該數(shù)獨(dú)的空格處WNF m表示該數(shù)獨(dú)難度的函數(shù)冷表示數(shù)k是否填入數(shù)獨(dú)方中的（i，j）處q表示往空格處填入0后數(shù)獨(dú)方中（i，j ）處的數(shù)yj表示經(jīng)過求解后數(shù)獨(dú)方中（i，j ）處的數(shù)4模型的建立與求解4.1問題14.1.1數(shù)獨(dú)難度的影響因

4、素通過對數(shù)獨(dú)的分析與研究，數(shù)獨(dú)難度與數(shù)獨(dú)候選數(shù)、邏輯推理方法、搜索步 數(shù)、空格數(shù)以及空格的分布情況都有密切的關(guān)系。通過大量的計算觀察發(fā)現(xiàn)，用 到的邏輯與推理方法越復(fù)雜，那么在數(shù)獨(dú)中出現(xiàn)的候選數(shù)越多 ；反之，在數(shù)獨(dú)題 中出現(xiàn)的候選數(shù)越多，解決數(shù)獨(dú)題所用到的邏輯推理方法一般也越難。 解答一個 數(shù)獨(dú)所用到的搜索步數(shù)越多，數(shù)獨(dú)中的候選數(shù)越多。反之，一般情況下也成立。另外數(shù)獨(dú)中的空格數(shù)以及空格的分布情況與候選數(shù)也有同樣類似的關(guān)系。 綜合這 幾個影響數(shù)獨(dú)難度的幾種因素，分析候選數(shù)和空格數(shù)為主要影響因素， 再根據(jù)其 構(gòu)造加權(quán)規(guī)范函數(shù) WNF m，計算數(shù)值來衡量數(shù)獨(dú)難度。4.1.2 WNF m函數(shù)的建立加權(quán)規(guī)

5、范函數(shù)建立在候選數(shù)列表的基礎(chǔ)上。根據(jù)候選數(shù)列表，計算出每一個 空單元格中的候選數(shù)數(shù)目，將候選數(shù)數(shù)目與其相對應(yīng)的加權(quán)函數(shù)結(jié)合起來， 計算 加權(quán)規(guī)范函數(shù)WNF 。定義單元格X中的候選數(shù)數(shù)目函數(shù)c(X )為c(X) = |X?，這個函數(shù)僅適用于數(shù)獨(dú)P中的空單元格，而數(shù)獨(dú)P中的空單元格可以表示為卜-汽|- .“23,4,5,6,7,8,91有n 1汕.9個候選數(shù)的候選數(shù)數(shù)目函數(shù)Cn(X)=|XEP |c(X )=n =|'xep |x? = n(2)我們賦予它相應(yīng)的加權(quán)函數(shù)W n，從而得到加權(quán)函數(shù)WF P不能準(zhǔn)確的反映數(shù)獨(dú)難度， WF P受數(shù)獨(dú)中空單元格數(shù)目影響很大，呈 正向關(guān)系，如在數(shù)獨(dú)中刪

6、除單元格，數(shù)獨(dú)空單元格數(shù)增加，導(dǎo)致wf m增加,即空格數(shù)越多，WF P越大，然而這并不符合所有的數(shù)獨(dú)。為了排除這一影響， 將加權(quán)函數(shù)WF P規(guī)范，得到加權(quán)規(guī)范函數(shù)：WNF ?=-W n C P nW 9|E(P根據(jù)以上的分析，對于某單元格 工，其候選數(shù)數(shù)X?越大，其對應(yīng)的加權(quán)函數(shù)W n也應(yīng)越大。我們采用指數(shù)函數(shù) Wexp n =2n”計算數(shù)獨(dú)？的WNF ?，其中n為某空單元格的候選數(shù)數(shù)目。計算發(fā)現(xiàn)，WNF ?與數(shù)獨(dú)難度是正相關(guān)的,即WNF ?越大，數(shù)獨(dú)的難度越大4.1.3 WNF ?函數(shù)的求解根據(jù)題中給出的數(shù)獨(dú)，按照數(shù)獨(dú)游戲應(yīng)該滿足的條件，可以得到該數(shù)獨(dú)的空 格處的候選數(shù)列表，如下表2所示：表

7、2 空格處候選數(shù)列表81246245692347123571234135694579134567912459124361257812481589457891457914567456348913482458134561234695246923892368716892489124691236912368269238945728912692467924682467912682689568932456923457234123479237234935968234672346852367234693912379235679256723781236781236842572357根據(jù)表2,把所得變量帶入式(3

8、)得：WF m =1392(5)由|E(pj =60代入式式中得：WNF P =0.04531(6)4.1.4數(shù)獨(dú)難度的劃分根據(jù)計算所得WNF P大小，我們將數(shù)獨(dú)題難度分為四個區(qū)間，分別表示簡 單、中等、難、極難。為方便表示，我們用1、2、3、4來表示難度系數(shù)。1) 若WNF盧0,0.012，數(shù)獨(dú)簡單，有較多候選數(shù)的空單元格很少，此時數(shù)獨(dú)題用一些簡單的直觀法就可以解決，用 1表示。2）若WNF 卜盧0.012,0.035，數(shù)獨(dú)有一定難度，要解決此數(shù)獨(dú)要用到候選數(shù)法中的一些簡單方法，且與直觀法結(jié)合起來推理，用2表示。3）若WNF 卜盧0.035,0.045，數(shù)獨(dú)比較難，內(nèi)部邏輯結(jié)構(gòu)復(fù)雜，將直觀法

9、與候選數(shù)法結(jié)合起來一般可以解決問題，用3表示。4）若WNF盧0.045,1 ,這個數(shù)獨(dú)很難，內(nèi)部的邏輯結(jié)構(gòu)相當(dāng)復(fù)雜，將直觀法與候選數(shù)法結(jié)合起來不一定可以解決問題，甚至有時候需要對某些空單元格進(jìn)行猜測，用4表示。在這里，我們將（0，1）粗略分為四個區(qū)間，用來相對表示數(shù)獨(dú)的相對難度。 根據(jù)數(shù)獨(dú)難度的劃分，由式（6）可得此數(shù)獨(dú)難度系數(shù)為4,達(dá)到了極難的程度。4.2問題24.2.1 算法的介紹本問中需要的是用窮舉法對數(shù)獨(dú)問題進(jìn)行求解，首先介紹一下窮舉法：窮舉法，或稱為暴力破解法 ，是基于計算機(jī)特點(diǎn)而進(jìn)行解題的思維方法。一般是在 一時找不出解決問題的更好途徑 （即從數(shù)學(xué)上找不到求解的公式或規(guī)則）時，可以

10、根據(jù)問題中的部分條件（約束條件）將所有可能解的情況列舉出來，然后通過 逐個驗證是否符合整個問題的求解要求，而得到問題的解。這樣解決問題的方法 我們稱之為窮舉算法。窮舉算法特點(diǎn)是算法簡單，但運(yùn)行時所花費(fèi)的時間量大。 因此，我們在用窮舉方法解決問題時，應(yīng)盡可能將明顯的不符合條件的情況排除 在外，以盡快取得問題的解。4.2.2求解的思想結(jié)合本問中需要用窮舉法解決數(shù)獨(dú)問題，最終算出上面所給出的數(shù)獨(dú)問題的 解。針對此數(shù)獨(dú)問題，在此先介紹一下我的算法思想：1）建立一個堆棧來存放數(shù)據(jù)；2）根據(jù)每行、每列和一個小九宮中不能出現(xiàn)相同的數(shù)字的規(guī)則來找出所有 空格中的所有可能值；3）從可能值中選取一個可能項最少的并

11、提取一個出來，若還有可能值就將 其放入堆棧中去，若提出的值不滿足條件則從堆棧中再提取一個值來繼續(xù)求解直 到找到滿足條件的解；舉個例子吧，對這一數(shù)獨(dú)問題，可以很快找到第八行第七列的可能值為 3和9, 其它空格的可能值都超過了三個， 現(xiàn)取出3出來進(jìn)行嘗試，那么放入堆棧中的是9 和其它的可能值，還有a （數(shù)獨(dú)值），然后一直按這種方法進(jìn)行下去，要是遇到不 滿足則從堆棧中重新拿出一個值來， 直到結(jié)果滿足結(jié)束循環(huán)。下面列了一個流程 圖，如下流程圖所示。首先進(jìn)行對程序中的所用符號進(jìn)行說明，先將數(shù)獨(dú)中問題的初始值（空格為0）存入數(shù)組a,將所有空格中的可能值存入數(shù)組y。4.2.3問題的求解根據(jù)該流程圖進(jìn)行編程，

12、并在matlab中實現(xiàn)，具體程序見附錄1。經(jīng)過2分鐘 左右求解得到最終結(jié)果，如下表4所示：4.3問題3根據(jù)問題2中處理方法，發(fā)現(xiàn)窮舉算法的特點(diǎn)是算法簡單，但運(yùn)行時所花費(fèi) 的時間較長。因此，我們在此基礎(chǔ)上進(jìn)行改進(jìn)，盡可能將明顯的不符合條件的情 況排除在外，以盡快取得問題的解。在求解數(shù)獨(dú)的過程中，遍歷此數(shù)獨(dú)所有可能 的搜索樹，直至找到數(shù)獨(dú)的解為止！在這個過程中，我們采用回溯法進(jìn)行求解。回溯法是一種搜索算法，其基本思路是：在一個問題中，根據(jù)題意給出的邊 界條件劃定出所有可能解的范圍（稱為可能解），根據(jù)題意確定出約束條件。利用程序順次在所有可能解中，搜索時按照深度搜索的方式進(jìn)行。即在第一層選定一 個滿

13、足約束條件的解，然后以該可能解為出發(fā)點(diǎn)，搜索第二層的一個可能解（試探）。如果搜索到第二層的一個可能解，則繼續(xù)搜索第三層的一個可能解。依次 類推，直到所有層的可能解都被找到，貝U得到了該問題的一個完整解。如果第二 層所有的可能解都不滿足約束條件， 則返回第一層，放棄原有的可能解，使用第 一層的下一個可能解（回溯）。以此類推，尋找第二層的一個可能解。具體算法一 般采用如下步驟：1）在此數(shù)獨(dú)初盤選擇一個空單元格；2）取這個單元格中一個可能的候選數(shù)；3）將這個候選數(shù)填入單元格中，迭代完成數(shù)獨(dú)；4）若這個候選數(shù)推導(dǎo)得到一個無效數(shù)獨(dú)終盤， 返回此單元格取其他候選數(shù)； 由于回溯法是在不斷地試探和回溯中運(yùn)算，

14、因此也可以稱為試探法或者試探回溯法。從上面的描述中可知，回溯法得到的問題的解只是根據(jù)不同的初始條 件獲得的第一個完全滿足所有約束條件的解，因此該解的獲得和初始條件有關(guān)。如果想要獲得該問題的全部解，則需要遍歷所有的可能的初始條件，也就是遍歷 所有的第一層的可能解。回溯法相對于其他窮舉的特點(diǎn)在于，不必把問題的每一層的所有的可能解都 遍歷一遍，只要當(dāng)前的可能解不滿足約束條件就拋棄該解，尋求下一個可能解， 而不必求解其余的下層解。當(dāng)當(dāng)前層的所有可能解都不滿足約束條件，則回溯到上一層，拋棄上一層的當(dāng)前可能解。從以上分析中結(jié)合數(shù)獨(dú)問題的規(guī)則， 得出 數(shù)獨(dú)問題的約束條件為：1）每一格的數(shù)值范圍僅限于I 一

15、9。2）每一格內(nèi)的數(shù)字在當(dāng)前行不允許重復(fù)。3）每一格內(nèi)的數(shù)字在當(dāng)前列不允許重復(fù)。4）每一格內(nèi)的數(shù)字在當(dāng)前小九宮內(nèi)不允許重復(fù)此算法最壞運(yùn)行時間是 門nn上，其中。n為數(shù)獨(dú)中數(shù)字未確定的單元格數(shù),k是數(shù)字已經(jīng)確定的單元格數(shù)。但是將這個方法稍作修改就可以在線性時間解決 一個數(shù)獨(dú)題目，即首先選擇數(shù)獨(dú)中候選數(shù)個數(shù)最少的空單元格， 再在其中選擇候 選數(shù)進(jìn)行試驗一檢驗。雖然回溯法有超多項式的最壞時間， 但是這種算法可以判 斷任何數(shù)獨(dú)是否具有唯一解，進(jìn)而解決這個數(shù)獨(dú)，難度很大的數(shù)獨(dú)求解經(jīng)常用到 此法。4.4問題4441問題的分析根據(jù)對數(shù)獨(dú)問題的分析，可知數(shù)獨(dú)是根據(jù) 9X9盤面上的已知數(shù)字，推理出 所有剩余空格

16、的數(shù)字，并滿足每一行、每一列、每一個粗線宮內(nèi)的數(shù)字均含1-9， 并且不能重復(fù)。為了敘述方便，對一個空的9階數(shù)獨(dú)方的行、列、區(qū)進(jìn)行重新編碼。數(shù)獨(dú) 方的行序為從上到下記作19，列序為從左到右記作19;然后把每一個粗線 宮作為一個區(qū)，區(qū)的行序為從上到下記作13，列序為從左到右記作13；區(qū) 行的行序為從上到下記作13，區(qū)列的列序為從左到右記作13。具體的編碼 方式如下圖1所示：算 ffi 1 9階數(shù)獨(dú)方及行、列.區(qū)的組成442模型的建立由于數(shù)k1,2,，9要么填入該9階數(shù)獨(dú)方矩陣的（i , j ）處，要么不填入，只有這兩種狀態(tài)，因而可用三維 0和1變量來表示。又該9階數(shù)獨(dú)方的解 唯一，可將這唯一解作為

17、目標(biāo)函數(shù)，行、列、區(qū)的約束條件可用三維的0和1變 量表出。4.4.2.1 決策變量令Xijk =1:表示數(shù)k填入n階數(shù)獨(dú)方矩陣的（i，j）處Xjk =0:表示數(shù)k不填入（i ， j ）處442.2 目標(biāo)函數(shù)與約束規(guī)劃問題的目標(biāo)函數(shù)一般都是最大或最小型的，又因根據(jù)題意可知該9階數(shù)獨(dú)方的可行解唯一，且該可行解就是最優(yōu)解，所以確定目標(biāo)函數(shù)為單位數(shù)1。通過對數(shù)獨(dú)這個問題的分析可以得出，所有剩余空格的數(shù)字，并滿足每一行、每 一列、每一個粗線宮內(nèi)的數(shù)字均含1-9，并且不能重復(fù)。因此可以得到如下約束 條件：（1）每一（i , j ）處只能填一個數(shù)k ；（2）第i行只有一個k ；（3）第j列只有一個k ；（4

18、）第一個區(qū)只有一個k ；4.4.2.3 該9階數(shù)獨(dú)方的數(shù)學(xué)模型 由上述分析可建立該9階數(shù)獨(dú)方的整數(shù)規(guī)劃模型如下：min z = 1XXjk = 1k 49xjk - 1j=1s.t9乞Xijk= 1i 43j 3i xmnk = 1m=3j -2n Ji _2Xjk =0或 17891011注：（7）式表示數(shù)獨(dú)方中每一（i , j）處只能填入一個數(shù)k；（8）式表示每一行只能有一個數(shù)k；（9）式表示每一列只能有一個數(shù) k ；（10）式表示每一個區(qū)內(nèi)只能有一個數(shù) k； （11）式表示Xjk只能取0或1；(12) 上所有式中 i, j,k =1,2,94.4.3模型的求解要想求解問題中給出的數(shù)獨(dú)問題

19、，首先可將題目中的所有空格處填入同一常數(shù)a,不妨取a=0，如表2所示。記q是表3中（i , j ）處的數(shù)，y0是數(shù)獨(dú)求 解后（i , j ）處的數(shù)，冷是三維的0和1變量，其含義如上所述。由上分析可99知，任意填入（i ,j ）處的任意數(shù)k k =1,2,9，都有a xijk =1，那么y0kxijk表3往空格填入0后的數(shù)獨(dú)方k=1kT根據(jù)上面建立的關(guān)于這個數(shù)獨(dú)問題的整數(shù)規(guī)劃模型， 利用lingo軟件編程進(jìn) 行求解，可以得到該模型的最優(yōu)解，也就是這個數(shù)獨(dú)問題的唯一解。具體程序見 附錄2，求解的最終結(jié)果如下表4所示：表4該數(shù)獨(dú)問題的解模型的檢驗問題1中采用了一種對數(shù)獨(dú)難度等級的劃分方法， 首先對問

20、題的進(jìn)行了綜合 的分析，然后在多個影響數(shù)獨(dú)難度的因素中選取空格數(shù)和空格候選數(shù)作為主要影 響因素，根據(jù)給出的計算方法對該數(shù)獨(dú)進(jìn)行計算， 得出該數(shù)獨(dú)的難度是屬于極難 的。由于在最后的計算過程中未考慮其他影響因素，因此得到的結(jié)果必然存在一定的誤差，但這個劃分方法還是可取的、有一定道理的。問題2中采用了窮舉法對該問題進(jìn)行求解，由于該方法考慮了所有可能出現(xiàn) 的情況，所以在有解的情況下一定可以求解該問題的解；也正因為如此，運(yùn)用該算法進(jìn)行求解時會花費(fèi)較長的時間。問題3中設(shè)計了一種更優(yōu)的求解算法一一回溯法。 它主要是對窮舉法進(jìn)行了 一定的改進(jìn)，縮短了求解該數(shù)獨(dú)問題的的時間。問題4中建立了一個求解數(shù)獨(dú)問題的模型

21、一一整數(shù)規(guī)劃模型。該模型充分考慮了該數(shù)獨(dú)應(yīng)該滿足的約束條件，并在此基礎(chǔ)上編程進(jìn)行求解，得到最終答案。 該模型求解的結(jié)果相當(dāng)準(zhǔn)確，并適應(yīng)于這一類問題的求解。模型的分析與推廣1.WNF P度量的優(yōu)劣衡量數(shù)獨(dú)難度的最客觀方法就是找到解決這個數(shù)獨(dú)所用時間，根據(jù)時間的長短判斷數(shù)獨(dú)難易。其次，可以根據(jù)解答這個數(shù)獨(dú)所用到的邏輯推理方法難易，量數(shù)獨(dú)難度。但這兩種方法都需要具體解答出所給數(shù)獨(dú)后才能做出判斷，雖然可以準(zhǔn)確反映數(shù)獨(dú)難度，但耗時較多。相比之下， WNF ?可以在常數(shù)時間內(nèi)計算出 以衡量數(shù)獨(dú)難易，對于任意一個數(shù)獨(dú)，我們不必具體解答，只需列出它的候選數(shù) 列表就可以計算出其相對難度，時間復(fù)雜性很低。掃描每個

22、單元格所在的行、列、 宮，通過唯一性原則確定其上的候選數(shù)，這種方法往往使得每個單元格上的候選 數(shù)較多，而有些候選數(shù)是可以通過一些簡單的邏輯推理消除的，從而使得WNF ?的值可能會偏高，過高估量數(shù)獨(dú)的難度，這也是這種方法的缺陷所在。2問題2利用窮舉法，模型思路比較簡單，正適用于解決多維、大規(guī)模、復(fù)-雜問題的通用法，借助matlab軟件編程求解，使數(shù)獨(dú)求解更加容易、方便，但它運(yùn)行時間比較長。3. 問題3中介紹的算法一一回溯法，它通過問題中的約束條件以試探 -回溯- 試探的篩選方式，將所有解的范圍中不符合約束條件的解予以排除， 從而達(dá)到快 速求解的目的，這也是求解這一類問題的較優(yōu)的算法。對于問題4建

23、立新的數(shù)獨(dú)求解模型，我們采用三維 0-1變量，利用lingo 軟件編程進(jìn)行求解，使數(shù)獨(dú)問題的數(shù)學(xué)表述變得簡單易懂。 同時該模型可用于處 理類似的填數(shù)問題如幻方，拉丁方等。14參考文獻(xiàn)1 孟 慶鈴 . 數(shù)獨(dú)問題人工 解 法的 程序?qū)崿F(xiàn) J. 甘肅 科技，2006， 22(09):150-151.2 雷 蕾，沈富可 . 關(guān)于數(shù)獨(dú)問題的算法的設(shè)計與實現(xiàn) J. 電腦知識與技術(shù)， 2007(2)：481-4823 王 瓊，鄒 晟. 數(shù)獨(dú)問題的求解、評價與生成算法的研究 J. 南京師范大 學(xué)學(xué)報：工程技術(shù)版 ,2010,3(1):76-79.4 胡 英 武 . 數(shù) 獨(dú) 問 題 的 整 數(shù) 規(guī) 劃 模 型

24、J. 金 華 職 業(yè) 技 術(shù) 學(xué) 院 學(xué) 報:2011,6:86-88.5 劉曉寶 . 數(shù)獨(dú)游戲的解題算法 J. 電腦編程技巧與維護(hù)， 2007(5)：64-67.程曦，肖華勇 . 數(shù)獨(dú)謎題難度等級劃分的步數(shù)法研究 J. 電子設(shè)計工程， 2012,3:86-8915附錄 附錄 1 問題 2 中 matlab 軟件求解源程序： clear clc a=open('qiujie.mat' ); a=a.a; sp=0; dui=;while find(a=0)for i=1:3for j=1:3 b(:,:,3*i+j-3)=a(3*i-2:3*i,3*j-2:3*j);enden

25、dfor i=1:9for j=1:9if a(i,j)=0 clear c k=3*(ceil(i/3)-1)+ceil(j/3); c=b(:,:,k); lg=(c>0); c=c(lg);x=setdiff(1:9,c); clear c c=a(i,:); lg=(c>0); c=c(lg); x=setdiff(x,c); clear c c=a(:,j); lg=(c>0); c=c(lg); x=setdiff(x,c); n=length(x);for ii=1:9-nx(ii+n)=0;endelse x=10*ones(1,9);endy(9*(i-1)+j,:)=x;endendd=(y>0);d=d' d=sum(d);d=d'if fin d(d=0) y=dui(:,:,sp); a=dua(:，:,sp); sp=sp-1; d=(y>0); d=d' d=sum(d); d=d'endd=fi nd(d=min( d); d=d(1);i=ceil(d/9); j=d-9*i+9;A=y(d,1)； y(d,1)=y(d,2