4.3　數(shù)獨(dú)游戲

題目描述（第37題）

編寫一個程序，通過已填充的空格來解決數(shù)獨(dú)問題。

一個數(shù)獨(dú)的解法須遵循如下規(guī)則。

●　數(shù)字1～9在每一行只能出現(xiàn)一次。

●　數(shù)字1～9在每一列只能出現(xiàn)一次。

●　數(shù)字1～9在每一個以粗實線分隔的3×3宮格內(nèi)只能出現(xiàn)一次?？崭裼?'.' 表示。

如下圖所示為一個數(shù)獨(dú)。

答案為下圖陰影部分的數(shù)字。

注意事項：

●　給定的數(shù)獨(dú)序列只包含數(shù)字1～9和字符'.'。

●　可以假設(shè)給定的數(shù)獨(dú)只有唯一解。

●　給定數(shù)獨(dú)永遠(yuǎn)是9×9形式的。

解法一　回溯解法

思路

讀者對數(shù)獨(dú)游戲應(yīng)該不陌生，在紙質(zhì)媒體發(fā)達(dá)的年代，很多報紙會提供一個專門的版面印上數(shù)獨(dú)游戲供讀者打發(fā)時間。規(guī)則簡單易懂是其成為大眾游戲的一大原因，解數(shù)獨(dú)的要求用一句話即可概括：填空格使每行、每列和每個九宮格都恰好由1到9這9個數(shù)字組成。

在只有唯一解的限定條件下，空格越多數(shù)獨(dú)越難解，用算法語言來講就是求解的時間復(fù)雜度越高。假設(shè)不使用任何策略，對n個空格采用暴力法窮舉求解，時間復(fù)雜度會接近9的n次方階。這樣的效率顯然是不可接受的，但枚舉思路基本正確，需要做的是利用規(guī)則并結(jié)合棋盤上已有的數(shù)字降低枚舉值的數(shù)量級；盲目的嘗試會產(chǎn)生很多無效的計算，利用回溯算法進(jìn)行有規(guī)律的遍歷是一種更可取的方法。

記錄狀態(tài)

首先定義row_state、column_state和box_state 存儲當(dāng)前每一行、每一列和九宮格中數(shù)字的使用狀態(tài)，如row[0][3]表示第1行中數(shù)字3的使用情況。對于九宮格，用行號對3的整除乘以3加上列號對3的整除，即(i // 3)＊ 3+j // 3，其中 i 和j 分別表示行號和列號（從0開始）。將二維坐標(biāo)的表示降為一維的，每一個九宮格的坐標(biāo)分布如下圖所示。

順序遍歷

完成3個狀態(tài)的初始化后，解數(shù)獨(dú)的遍歷過程從board[0][0]開始，根據(jù)規(guī)則的限定選取數(shù)字放入空格，定義place_number方法執(zhí)行此操作；每完成一格的填寫或遇到已填有數(shù)字的格子時，遍歷坐標(biāo)向右移動，當(dāng)列下標(biāo)變?yōu)?時（第1個格子從0開始）意味著本行處理完畢，換行并從下一行的最左側(cè)繼續(xù)遍歷；重復(fù)上面的過程，當(dāng)填好最后一個格子，即右下角的board[8][8]后，將換行至第9行這一條件作為判定停止的標(biāo)準(zhǔn)。

回退重試

不妨把數(shù)獨(dú)的盤面當(dāng)作棋盤，假如棋盤布局設(shè)定比較簡單，尤其是在空格較少的情況下，上述遍歷方法是有可能一次性走到最后的，但在大多數(shù)情況下并不這樣理想。在游戲過程中，一些格子在判定條件有限的情況下會有多個解，即存在多個可填的數(shù)字，而我們的遍歷過程只能選取其中一個。當(dāng)遇到某個格子沒有任何數(shù)字可填時，說明前方某處選取的數(shù)字并不正確，這時應(yīng)進(jìn)行回退。將遍歷坐標(biāo)回退到上一個有其他解的格子，繼續(xù)嘗試其他解，當(dāng)然不要忘記回退時將路徑上已經(jīng)填上的數(shù)字清除，定義方法undo_number_placement實現(xiàn)此操作。

完成數(shù)獨(dú)

持續(xù)進(jìn)行順序遍歷和失敗重試的過程，最終完成所有格子的遍歷意味著我們得到了數(shù)獨(dú)的解，如果在此之前耗盡了所有可選數(shù)字，則說明此數(shù)獨(dú)無解。當(dāng)然，根據(jù)題目設(shè)定，這種情況不會出現(xiàn)。

跟隨上述思路，我們可以一步一步實現(xiàn)下面的Python代碼。

代碼

復(fù)雜度分析

通常用大O表示法來展示算法的漸進(jìn)時間復(fù)雜度（asymptotic time complexity），它衡量的是算法的執(zhí)行時間隨著輸入規(guī)模增長而變化的趨勢；因為格子數(shù)量有限，問題的規(guī)模不會一直變大，數(shù)獨(dú)問題不滿足求漸進(jìn)時間復(fù)雜度的前提。

不過這樣的結(jié)論應(yīng)該不能滿足你的期望，與了解并掌握算法相比，所謂的標(biāo)準(zhǔn)答案并沒有那么重要。忽略規(guī)模增長的上限，我們的算法與空格數(shù)n相關(guān)的復(fù)雜度是多少呢？

●　時間復(fù)雜度：假設(shè)每個空格可能填入的數(shù)字個數(shù)都是m，算法的最差時間復(fù)雜度為O(mn)；在實際情況下，每個格子的m應(yīng)介于1到9之間，且并不一定相同，具體的最長的執(zhí)行時間為所有m值的乘積。

●　空間復(fù)雜度：解題過程中所使用的中間變量與棋盤的大小有關(guān)，在大小固定的棋盤上，算法的空間復(fù)雜度為O(1)。

解法二　回溯法優(yōu)化

思路

基于上面對時間復(fù)雜度的分析，我們可以從m的值，即每個空格可填數(shù)字的個數(shù)入手優(yōu)化我們的算法。

數(shù)獨(dú)中格子之間有很強(qiáng)的關(guān)聯(lián)，對于任意空格，隨著同一行、同一列或同一個九宮格中某一格放入的數(shù)字被確認(rèn)，空格可填的數(shù)字個數(shù)會隨之減少。我們應(yīng)當(dāng)從把握最大的格子填起，即如果最壞的可能是一系列m值的乘積，應(yīng)當(dāng)從最小的m值乘起，使后續(xù)m值隨之降低，理想狀態(tài)下每個m值都是1，即一次回退也不會出現(xiàn)。把可能的回退次數(shù)降到最少，這樣的解法與人們玩數(shù)獨(dú)游戲時的思路十分相近。

定義函數(shù)get_max_possible_coordinate，讓它根據(jù)當(dāng)前棋盤的情況計算填數(shù)正確性最大的空格并返回其坐標(biāo)。我們知道可以填入的數(shù)字個數(shù)越少意味著正確性越大，當(dāng)可以填入的數(shù)字只有一個時正確率為100%，直接返回這個空格的坐標(biāo)即可；若沒有這樣的理想候選項，則返回遍歷過程中可填數(shù)字最少的那個空格的坐標(biāo)。

使用get_max_possible_coordinate函數(shù)取代上一節(jié)解法中的順序遍歷法，我們實現(xiàn)了一個更優(yōu)化的解法。

代碼

復(fù)雜度分析

●　時間復(fù)雜度：假設(shè)每個空格可能填入的數(shù)字個數(shù)都是m，算法的最差時間復(fù)雜度為O(mn)；在實際情況下，每個格子的m應(yīng)介于1到9之間，且并不一定相同，因此最差的情況需要執(zhí)行所有m值的乘積次的操作。

●　空間復(fù)雜度：解題過程中所使用的中間變量與棋盤的大小有關(guān)，即與空格數(shù)無關(guān)，因此算法的空間復(fù)雜度為O(1)。

思考

解法二在尋找填數(shù)正確率最高空格的過程中，需再次遍歷棋盤，與直接嘗試下一格相比，似乎多執(zhí)行了許多操作，它的解題效率真的比解法一強(qiáng)么？帶著這樣的疑問我們來做個實驗，以力扣（LeetCode）題目中的默認(rèn)測試用例為例，棋盤中有空格51個，超過半數(shù)。

定義變量undo_count記錄兩種解法對undo_number_placement方法的調(diào)用次數(shù)，這樣我們就可以比較完成時兩者分別進(jìn)行的回退次數(shù)了。

執(zhí)行后的結(jié)果顯示：解法一回退了4157次，而解法二只回退了7次，即解法一最終嘗試填數(shù)4208次才完成數(shù)獨(dú)，而解法二只用了58次！這不得不讓人感嘆合理算法的神奇與美妙。

在大多數(shù)情況下，解法二效率更高，因為這樣的遍歷法會顯著提高回退效率。前面分析過，隨著越來越多的空格被正確地填上，問題的復(fù)雜度會隨之降低。

首先它保證了存在唯一選項可選，即在存在正確答案的情況下不去做無謂的猜測。

其次參考前面做出的時間復(fù)雜度為O(mn)的分析，即便不得不進(jìn)行猜測，這樣的方法也能夠非常有效地控制m值的大小。

解法二在回溯法的思路上做了優(yōu)化。而在實際解題的過程中，還可以通過優(yōu)化數(shù)據(jù)結(jié)構(gòu)等方法進(jìn)一步提高執(zhí)行效率，你不妨自己動手試試看。