算法比較暴力，直接用窮舉的方式一個一個去試，所以程序運行時間會比較長，運行時間視數獨而定。
不過從一開始到運行成功，整個過程卻是一波三折，設計算法就花了不少時間，然后就是不斷地去調試，找bug。剛開始的時候為了省事直接在sudoku類中遞歸調用blank，但是老哥還是too young too simple，sometimes navie，計算量實在是太大了，后面編譯器直接拋出 “recursionerror: maximum recursion depth exceeded while calling a python object” 超過最大遞歸深度的錯誤。在把遞歸深度改到100000之后，又出現了堆棧溢出問題。當然，解決辦法也是相當地暴力：把遞歸放入while循環中，一旦符合條件就直接exit(0)，整個程序直接gg，然后退出結束。
當然，算法還可以再優化一下，可以不用那么暴力，先列出可能的值然后再填入，這樣可以大大縮小整個程序的運行時間，但是……懶得優化了，就這樣吧，又不是不能用（笑~）。
運行結果：
再試一個其他的數獨：
這回就快得多了，11秒就完成了，比第一個數獨不知高到哪里去了
代碼如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
import copyimport timet1=time.time()origin = [[8, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 6, 0, 0, 0, 0, 0], [0, 7, 0, 0, 9, 0, 2, 0, 0], [0, 5, 0, 0, 0, 7, 0, 0, 0], [0, 0, 0, 0, 4, 5, 7, 0, 0], [0, 0, 0, 1, 0, 0, 0, 3, 0], [0, 0, 1, 0, 0, 0, 0, 6, 8], [0, 0, 8, 5, 0, 0, 0, 1, 0], [0, 9, 0, 0, 0, 0, 4, 0, 0]]class sudoku: def debug(self): # 調試 for list in origin: print(list) print("\n") def check_repetition(self,list):#判斷表中是否有重復值，0除外 flag=0 for i in range(1,10): if list.count(i)>=2: return 1 else: flag=flag+1 if flag==9: return 0 def check_row(self,row):#檢測橫向是否有重復值，無則為返回0，有則返回1 list = origin[row] # 橫向 r1 = self.check_repetition(list) if r1 == 0: return 0 else : return 1 def check_column(self,column):#檢測縱向是否重復值，無則為返回0，有則返回1 list = [] # 縱向 for num in origin: list.append(num[column]) r2 = self.check_repetition(list) if r2==0: return 0 else: return 1 def check_square(self,x,y):#檢測九宮格是否有重復值，無則為返回0，有則返回1 x,y=y,x if x>=9 or y>=9: return square = []#九宮格 for i in range(0+y//3*3, 3+y//3*3): for j in range(0+x//3*3, 3+x//3*3): square.append(origin[i][j]) r3 = self.check_repetition(square) if r3==0: return 0 else: return 1 def check(self,x,y):#檢測是否有重復值，無則為0，有則不為0 r1 = self.check_row(x) r2 = self.check_column(y) r3 = self.check_square(x, y) result=r1+r2+r3 return result def get_next(self): # 獲得下一個空值，返回row,column值 i = 0 for list in origin: try: # 當0不在列表中時，跳過 column = list.index(0) row = origin.index(list) res = (row, column) return res except valueerror: i = i + 1 if i == 9: t2=time.time() print("總用時={}".format(t2 - t1)) exit(0) def poi(self,row, column): # 位置修正 if row == 0 and column == -1: return if row == 8 and column == 9: return if column == -1: column = 8 row = row - 1 if column == 9: column = 0 row = row - 1 return (row, column) def get_last(self,row, column): origin[row].insert(column, 0) origin[row].pop(column + 1) column = column - 1 # 獲得上一個已填值的行、列位置 row, column = self.poi(row, column)#位置修正 r = origin[row][column] * compare[row][column] while r != 0: column = column - 1 row, column = self.poi(row, column) r = origin[row][column] * compare[row][column] return (row, column) def blank(self): try: row,column=self.get_next() except typeerror:#已填完 exit(0) j=0 flag=0 for i in range(1,10): origin[row].insert(column,i) origin[row].pop(column+1) self.debug() r = self.check(row, column) if r==0:#無重復值 return else: j = j + 1 if j==9: flag=1 break if flag==1: row, column = self.get_last(row, column) value=origin[row][column] self.debug() while value == 9: row, column = self.get_last(row, column) value = origin[row][column] self.debug() while value<9: for k in range(value+1,10): origin[row].insert(column, k) origin[row].pop(column + 1) self.debug() r=self.check(row,column) if r!=0:#有重復 if k==9: row, column = self.get_last(row, column) value=origin[row][column] self.debug() while value==9: row, column = self.get_last(row, column) value = origin[row][column] self.debug() break else: returnif __name__=="__main__": compare = copy.deepcopy(origin) sudoku = sudoku() while 1: sudoku.blank() |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/Jayshon_Jaa/article/details/83040821
