芬蘭數學家因卡拉，花費3個月時間設計出了世界上迄今難度最大的數獨遊戲，而且它隻有一個答案。因卡拉說隻有思考能力最快、頭腦最聰明的人才能破解這個遊戲

寫在前面

今天來點幹貨，結合深度優先搜索算法，對數獨進行求解。以下代碼純屬手工編寫，每個步驟都附加詳細說明。

環境配置

python版本： 3.6.0

編輯器： pycharm

第一步：導入相關的python包

# encoding:utf-8 import copy

copy： 主要用于數組（矩陣）的深拷貝，有深拷貝就有淺拷貝。可以這麼理解，深拷貝就是新開辟一個内存，修改原數據，拷貝後的數據不會被影響。而淺拷貝隻是給數組取了個别名，實際上是同一個内容的數據，修改原數據，拷貝後的數據會跟着修改。

如果不特别聲明，數組的拷貝一般是淺拷貝，例如函數傳參。後面遞歸的參數數組，用的是淺拷貝，所以同一個數組共用一塊内存。

第二步：判斷矩陣是否填滿

"""判斷矩陣是否填滿了""" def is_full(in_sd_matrix): for i in range(len(in_sd_matrix)): for j in range(len(in_sd_matrix[i])): if in_sd_matrix[i][j] == 0: return False return True

這裡作了個前提，如果矩陣中數值為0，說明該位置還未填入數字。

第三步：數獨的規則

"""判斷當前位置能否填指定數字""" def can_fit(in_sd_matrix, row_index:int, col_index:int, num): # 判斷當前行是否出現重複的非零數字 for k in range(len(in_sd_matrix[row_index])): if k != col_index and in_sd_matrix[row_index][k] == num: return False # 判斷當前列是否出現重複的非零數字 for k in range(len(in_sd_matrix)): if k != row_index and in_sd_matrix[k][col_index] == num: return False # 判斷當前矩陣是否出現重複的非零數字 cube_i, cube_j = int(row_index / 3), int(col_index / 3) for k in range(cube_i * 3, (cube_i 1) * 3): for p in range(cube_j * 3, (cube_j 1) * 3): if k != row_index and p != col_index and in_sd_matrix[k][p] == num: return False return Tru

利用了數獨的規則，每個數字滿足三個條件：

1. 該數字所在的當前行不會重複，

2. 該數字所在的當前列不會重複，

3. 該數字所在的小九宮格數字不會重複。

第四步：遞歸-深度優先搜索

"""遞歸填數字""" def depth_fit_num(in_sd_matrix): # 遞歸結束條件， 已經填滿了 if is_full(in_sd_matrix): return True for i in range(0, 9): for j in range(0, 9): if in_sd_matrix[i][j] != 0: continue # 嘗試填 1 ~ 9 數字 fail_cnt = 0 for t_num in range(1, 10): # 判斷當前位置是否可以填數字num if can_fit(in_sd_matrix, i, j, t_num): in_sd_matrix[i][j] = t_num # 嘗試填數字 flag = depth_fit_num(in_sd_matrix) # 遞歸 if flag is False: fail_cnt = 1 # 這裡也代表不能填數字 else: fail_cnt = 1 # 不能填的數字個數 # 如果該空格 1~ 9都不能填，說明該路徑行不通 if 9 == fail_cnt: in_sd_matrix[i][j] = 0 # 回溯 return False return True

depth_fit_num() 遞歸填數字，參數 in_sd_matrix 是一個數組（淺拷貝），也就是說，每一次遞歸，都是在原數組上進行操作。這是一個非常典型的遞歸的函數。我們假設輸入的數獨一定存在一個或多個解。該遞歸滿足五個步驟：

1. 遞歸結束條件。在開頭 is_full() 函數，一旦數組填滿，就結束遞歸；

2. 遞歸主體1，雙重for循環對9X9宮格進行遍曆，對每個空格進行1~9的數字填入

3. 遞歸主體2，depth_fit_num(), 對矩陣進行深度優先搜索

4. 遞歸主體3，回溯，如果發現當層遞歸中，該空格1~9都不能填入，說明上層遞歸嘗試的的數字不對，則當前位置數字回溯重置為0，并 return False 結束當層遞歸；

5. 遞歸結束條件，當前層遞歸循環體全部完成，return True, 結束當層遞歸。

（ps: 可以使用單步調試，查看每次遞歸，in_sd_matrix 矩陣的數值變化）

換一種方式說，就是該遞歸函數，在這個9X9的宮格中，不斷去嘗試每個位置1~9數字的逐個逐個填入，并判斷是否滿足數獨要求。一旦發現某個位置不滿足，就不會繼續嘗試下去，而是倒回前一個位置嘗試其他數字。如此反複。

第五步：規則打印

"""打印矩陣""" def print_sd(in_sd_matrix, out_sd_matrix, question_type, answer_type): """ 打印矩陣 :param in_sd_matrix: 輸入矩陣 :param out_sd_matrix: 輸出矩陣 :param question_type: 問題顔色 :param answer_type: 答案顔色 :return: """ head_line = (" " " =====" * 3) * 3 " " mid_line = (" " " -----" * 3) * 3 " " for i in range(len(in_sd_matrix)): new_line = '' for j in range(len(in_sd_matrix[i])): if j == 0: new_line = "||" if in_sd_matrix[i][j] != 0: new_line = " %s " % (question_type % str(in_sd_matrix[i][j])) else: new_line = " %s " % (answer_type % (str(out_sd_matrix[i][j]) if out_sd_matrix[i][j] != 0 else ' ')) if (j 1) % 3 != 0: new_line = "|" elif (j 1) % 3 == 0: new_line = "||" if i == 0: print(head_line) print(new_line) if (i 1) % 3 != 0: print(mid_line) elif (i 1) % 3 == 0: print(head_line)

設計好了基礎算法，還需要設計輸出展示“UI”。這裡隻是對輸出的矩陣進行美化，使得更加可觀。同時區分數獨題目，和數獨求解後的答案。題目是紅色标注，填的答案用綠色标注。

第六步：主函數

if __name__ == '__main__': sd_matrix = [[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, 8, 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]] red_type = "\033[031m%s\033[0m" green_type = "\033[036m%s\033[0m" out_sd_matrix = copy.deepcopy(sd_matrix) # 深複制 print_sd(sd_matrix, out_sd_matrix, red_type, green_type) depth_fit_num(out_sd_matrix) print_sd(sd_matrix, out_sd_matrix, red_type, green_type) print(

主函數，對輸入的矩陣進行深拷貝（主要用于對比題目和答案）。調用之前寫好的數獨求解的算法。

輸入輸出：

最後，給一點點學習建議，不懂的時候，先弄明白它的功能以及會使用它，讓代碼先運行起來。等有時間就一個一個細節去攻破它，編程和寫文章一樣，需要慢慢積累，加油。

---

如果有疑問想獲取源碼，可以關注後，在後台私信我，回複：python數獨。 我把源碼發你。最後，感謝大家的閱讀，祝大家工作生活愉快！

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部