導讀：前面幾篇文章分享了一些BFS相關的題目，今天再來一道DFS算法的題目，大家一起來學習吧！
題目描述
編寫一個程序，來解決數獨問題。
一個數獨的解法需遵循如下規則：
- 數字 1-9 在每一行只能出現一次。
- 數字 1-9 在每一列只能出現一次。
- 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。
空白格用 '.' 表示
待解的數獨
解開的數獨
題目來源：leetcode 37. Sudoku Solver
題目分析
這種類型題目，對於學習過算法的粉絲來說，應該不難，很容易想到用深度優先搜索算法來解決（DFS）。DFS算法在運行過程中，我們需要對每個待確定的小方格里的數字逐一嘗試，每個待確定的小方格里的數字，必須和數獨的特性不衝突，所以，我們需要用額外的hash數組來標識哪些數字已經不能使用，針對每一行，每一列，每一個3*3的子宮格都需要hash一下。其實，這種類型DFS雖然說簡單，但是DFS往往涉及比較多的遞歸，回溯的過程，這裡面的狀態要維護好，不然容易出錯，堆棧溢出，或者其他奇奇怪怪的問題！
直接見源碼，代碼是很久以前java寫的，比較粗糙，其實，這個題目有個優化的技巧，後續算法哥再說明！
源碼片段一
源碼片段二
複雜度分析
這個複雜度其實不太好分析，因為與給出的數獨的複雜度相關性很大，極端情況，複雜度會很大！
題目總結
《解數獨》這道題目，是非常經典的DFS的題目，對遞歸，回溯的要求還是蠻高的，不熟悉的話，很容易寫錯！
前面說過這個題目有個優化的技巧，其實，每個待確定的方格里，需要嘗試的數字可能個數是有多少的區別的，我們可以儘量從個數少的方格開始遞歸，這樣會效率更高的，至於為什麼留給讀者自己思考吧！
今天的題目分享完畢，請幫助算法哥上頭條吧，您的關注，轉發，點贊，收藏都是對算法哥最大的鼓勵！
分享到:
閱讀更多 算法哥 的文章
