思考1、（窮舉方法）為了滿足規(guī)則要求，采用遞歸回溯的方法寫入每個(gè)位置的數(shù)字戒良。也就是說，先寫入一個(gè)數(shù)字冠摄，然后在這一行這一列進(jìn)行查詢對(duì)比糯崎，如果存在相等的數(shù)字就退回到初始位置從1~9中重新選取一個(gè)數(shù)字寫入，繼續(xù)進(jìn)行對(duì)比回溯重復(fù)河泳，直到全部寫入相應(yīng)位置沃呢。這樣做的顯著缺點(diǎn)就是需要大量的回溯步驟和重新寫入，導(dǎo)致時(shí)間復(fù)雜度高拆挥。
思考2薄霜、依據(jù)數(shù)獨(dú)表格的分布狀況可以看出，每一行纸兔，每一列惰瓜，每一個(gè)九個(gè)粗線宮格內(nèi)的九個(gè)小格有且僅有出現(xiàn)1~9數(shù)字中的一個(gè)。所以汉矿，在第一行的1~3列小格寫入數(shù)字x（為1~9中的任一個(gè)）崎坊，在第二行的4~6列小格同樣寫入數(shù)字x，同樣的洲拇，在第三行的7~9列小格也寫入x奈揍。然后重復(fù)上述操作，寫入另一個(gè)數(shù)y赋续。同樣在4~6行同樣進(jìn)行這樣的操作男翰。這樣寫入的方法可以避免回溯次數(shù)。
補(bǔ)充思考1纽乱、將數(shù)獨(dú)游戲構(gòu)成抽象成“樹”數(shù)據(jù)結(jié)構(gòu)類型蛾绎。將數(shù)獨(dú)的中心線當(dāng)做每一組四杈樹的跟節(jié)點(diǎn)，并風(fēng)別將四杈樹迫淹，分成兩組進(jìn)行便利對(duì)比秘通，判斷節(jié)點(diǎn)的值不讓其相同为严，若是相同則修改其值再次進(jìn)行節(jié)點(diǎn)便利比較敛熬。缺點(diǎn)很明顯不僅要在大的九宮格上進(jìn)行樹遍歷比較，還要求在小九宮格中進(jìn)行遍歷比較第股，并且還不一定能夠成功找出正確給出解应民。
補(bǔ)充思考2、將數(shù)獨(dú)類比于求最優(yōu)解的的問題，根據(jù)規(guī)則要求不管如何每一行诲锹，每一列繁仁，每一個(gè)粗框九宮格必定都要滿足1~9這些分別且全部存在。采用深度優(yōu)先遍歷的算法能夠很好的避免過多的回溯归园。甚至有些數(shù)據(jù)不需要回溯黄虱。
### 代碼分析
-確定代碼的IPO模式：
-輸入為需要補(bǔ)充完整的部分?jǐn)?shù)獨(dú)
-輸出為完整的數(shù)獨(dú)組成
1.輸入：已存在數(shù)據(jù)的按照原數(shù)據(jù)輸入，不存在的數(shù)據(jù)以數(shù)字0表示庸诱。直接讀取文件夾完成數(shù)據(jù)輸入捻浦。
2.同時(shí)將數(shù)獨(dú)表示列表的形式，使得用來查找的索引對(duì)應(yīng)每一行每一列桥爽。
3.采用深度優(yōu)先遍歷的方法進(jìn)行數(shù)據(jù)結(jié)構(gòu)造朱灿。創(chuàng)建數(shù)獨(dú)類 soduku （ Object ），定義方法 Check （）用來判斷每一行每一列每一個(gè)粗線框九宮格是否存在相同項(xiàng)钠四。定義方法 Getnext() 用來獲取下一項(xiàng)盗扒。定義主循環(huán) SudokuTry（）
4.輸出：預(yù)測能夠輸出一個(gè)完整的數(shù)獨(dú)
SudokuTry（）//主循環(huán)
if self.b[x][y] == 0:
for i in range(1,10):#從1到9嘗試
self.t+=1
if self.check(x,y,i):#符合 行列宮均無條件 的
self.b[x][y]=i #將符合條件的填入0格
next_x,next_y=self.get_next(x,y)#得到下一個(gè)0格
if next_x == -1: #如果無下一個(gè)0格
return True??#返回True
else:????????#如果有下一個(gè)0格，遞歸判斷下一個(gè)0格直到填滿數(shù)獨(dú)
end=self.try_it(next_x,next_y)
if not end:???#在遞歸過程中存在不符合條件的缀去，即 使try_it函數(shù)返回None的項(xiàng)
self.b[x][y] = 0????#回朔到上一層繼續(xù)
else:
return True
測試數(shù)據(jù)：
0 0 0 0 0 0 0 0 9
9 0 0 0 0 0 0 7 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
3 0 0 0 4 5 7 0 0
0 8 0 0 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
7 0 0 0 1 0 0 0 2
1 4 2 7 5 3 6 8 9
9 6 5 2 8 4 1 7 3
8 7 3 1 9 6 2 5 4
2 5 4 6 3 7 8 9 1
3 1 9 8 4 5 7 2 6
6 8 7 9 2 1 4 3 5
5 3 1 4 7 2 9 6 8
4 2 8 5 6 9 3 1 7
7 9 6 3 1 8 5 4 2
use Time: 0.793530 s
輸入：
sudoku=[
0,0,7,0,0,0,8,2,0,
0,9,0,0,0,1,0,0,0,
0,4,0,9,7,0,0,0,0,
0,0,0,0,0,5,4,0,6,
0,0,3,0,0,0,7,0,0,
5,0,6,7,0,0,0,0,0,
0,0,0,0,8,4,0,5,0,
0,0,0,6,0,0,0,1,0,
0,2,4,0,0,0,6,0,0,
]
預(yù)測輸出：
1 5 7 4 3 6 8 2 9
6 9 8 5 2 1 3 4 7
3 4 2 9 7 8 5 6 1
2 7 9 3 1 5 4 8 6
4 1 3 8 6 2 7 9 5
5 8 6 7 4 9 1 3 2
7 6 1 2 8 4 9 5 3
8 3 5 6 9 7 2 1 4
9 2 4 1 5 3 6 7 8
實(shí)際輸出
1 5 7 4 3 6 8 2 9
6 9 8 5 2 1 3 4 7
3 4 2 9 7 8 5 6 1
2 7 9 3 1 5 4 8 6
4 1 3 8 6 2 7 9 5
5 8 6 7 4 9 1 3 2
7 6 1 2 8 4 9 5 3
8 3 5 6 9 7 2 1 4
9 2 4 1 5 3 6 7 8
use Time: 0.876582 s
python 3.6
