經常拿回溯算法來說事兒的，無非就是八皇後問題和數獨問題了。那我們今天就通過
實際且有趣的例子來講一下如何用回溯算法來解決數獨問題。
一、直覺感受
說實話我小的時候也嘗試過玩數獨遊戲，但從來都沒有完成過一次。做數獨是有技巧的，我記得一些比較專業的數獨遊戲軟體，他們會教你玩數獨的技巧，不過在我看來這些技巧都太複雜，我根本就沒有興趣看下去。
不過自從我學習了算法，多困難的數獨問題都攔不住我了。下面是我用程式完成數獨的一個例子：
PS：GIF 可能出現 bug，若卡住點開檢視即可，下同。
這是一個安卓手機中的數獨遊戲，我使用一個叫做 Auto.js 的腳本引擎，配合回溯算法來實作自動完成填寫，并且算法記錄了執行次數。
在後文，我會給出該腳本的實作思路代碼以及軟體工具的下載下傳，你也可以拿來裝逼用。
可以觀察到前兩次都執行了 1 萬多次，而最後一次隻執行了 100 多次就算出了答案，這說明對于不同的局面，回溯算法得到答案的時間是不相同的。
那麼計算機如何解決數獨問題呢？其實非常的簡單，就是窮舉嘛，下面我可視化了求解過程：
。
對于數獨遊戲，也許我們還會有另一個誤區：就是下意識地認為如果給定的數字越少那麼這個局面的難度就越大。
這個結論對人來說應該沒毛病，但對于計算機而言，給的數字越少，反而窮舉的步數就越少，得到答案的速度越快，至于為什麼，我們後面探讨代碼實作的時候會講。
上一個 GIF 是最後一關 70 關，下圖是第 52 關，數字比較多，看起來似乎不難，但是我們看一下算法執行的過程：
可以看到算法在前兩行窮舉了半天都沒有走出去，由于時間原因我就沒有繼續錄制了，事實上，這個局面窮舉的次數大概是上一個局面的 10 倍。
言歸正傳，下面我們就來具體探讨一下如何用算法來求解數獨問題，順便說說我是如何可視化這個求解過程的。
二、代碼實作
首先，我們不用管遊戲的 UI，先單純地解決回溯算法，LeetCode 第 37 題就是解數獨的問題，算法函數簽名如下：
void solveSudoku(char[][] board);
輸入是一個9x9的棋盤，空白格子用點号字元
.
表示，算法需要在原地修改棋盤，将空白格子填上數字，得到一個可行解。
至于數獨的要求，大家想必都很熟悉了，每行，每列以及每一個 3×3 的小方格都不能有相同的數字出現。那麼，現在我們直接套回溯架構即可求解。
前文回溯算法詳解，已經寫過了回溯算法的套路架構，如果還沒看過那篇文章的，建議先看看。
回憶剛才的 GIF 圖檔，我們求解數獨的思路很簡單粗暴，就是對每一個格子所有可能的數字進行窮舉。對于每個位置，應該如何窮舉，有幾個選擇呢？
很簡單啊，從 1 到 9 就是選擇，全部試一遍不就行了：
// 對 board[i][j] 進行窮舉嘗試
void backtrack(char[][] board, int i, int j) {
int m = 9, n = 9;
for (char ch = '1'; ch <= '9'; ch++) {
// 做選擇
board[i][j] = ch;
// 繼續窮舉下一個
backtrack(board, i, j + 1);
// 撤銷選擇
board[i][j] = '.';
}
}
emmm，再繼續細化，并不是 1 到 9 都可以取到的，有的數字不是不滿足數獨的合法條件嗎？而且現在隻是給
j
加一，那如果
j
加到最後一列了，怎麼辦？
很簡單，當j
i
：
void backtrack(char[][] board, int i, int j) {
int m = 9, n = 9;
if (j == n) {
// 窮舉到最後一列的話就換到下一行重新開始。
backtrack(board, i + 1, 0);
return;
}
// 如果該位置是預設的數字，不用我們操心
if (board[i][j] != '.') {
backtrack(board, i, j + 1);
return;
}
for (char ch = '1'; ch <= '9'; ch++) {
// 如果遇到不合法的數字，就跳過
if (!isValid(board, i, j, ch))
continue;
board[i][j] = ch;
backtrack(board, i, j + 1);
board[i][j] = '.';
}
}
// 判斷 board[i][j] 是否可以填入 n
boolean isValid(char[][] board, int r, int c, char n) {
for (int i = 0; i < 9; i++) {
// 判斷行是否存在重複
if (board[r][i] == n) return false;
// 判斷列是否存在重複
if (board[i][c] == n) return false;
// 判斷 3 x 3 方框是否存在重複
if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
return false;
}
return true;
}
emmm，現在基本上差不多了，還剩最後一個問題：這個算法沒有 base case，永遠不會停止遞歸。這個好辦，什麼時候結束遞歸？
顯然r == m
。
另外，前文也提到過，為了減少複雜度，我們可以讓
backtrack
函數傳回值為
boolean
，如果找到一個可行解就傳回 true，這樣就可以阻止後續的遞歸。隻找一個可行解，也是題目的本意。
最終代碼修改如下：
boolean backtrack(char[][] board, int i, int j) {
int m = 9, n = 9;
if (j == n) {
// 窮舉到最後一列的話就換到下一行重新開始。
return backtrack(board, i + 1, 0);
}
if (i == m) {
// 找到一個可行解，觸發 base case
return true;
}
if (board[i][j] != '.') {
// 如果有預設數字，不用我們窮舉
return backtrack(board, i, j + 1);
}
for (char ch = '1'; ch <= '9'; ch++) {
// 如果遇到不合法的數字，就跳過
if (!isValid(board, i, j, ch))
continue;
board[i][j] = ch;
// 如果找到一個可行解，立即結束
if (backtrack(board, i, j + 1)) {
return true;
}
board[i][j] = '.';
}
// 窮舉完 1~9，依然沒有找到可行解，此路不通
return false;
}
boolean isValid(char[][] board, int r, int c, char n) {
// 見上文
}
？
我們已經實作了一遍算法，掌握了其原理，回溯就是從 1 開始對每個格子窮舉，最後隻要試出一個可行解，就會立即停止後續的遞歸窮舉。是以暴力試出答案的次數和随機生成的棋盤關系很大，這個是說不準的。
那麼你可能問，
既然運作次數說不準，那麼這個算法的時間複雜度是多少呢？
對于這種時間複雜度的計算，我們隻能給出一個最壞情況，也就是 O(9^M)，其中
M
是棋盤中空着的格子數量。你想嘛，對每個空格子窮舉 9 個數，結果就是指數級的。
這個複雜度非常高，但稍作思考就能發現，實際上我們并沒有真的對每個空格都窮舉 9 次，有的數字會跳過，有的數字根本就沒有窮舉，因為當我們找到一個可行解的時候就立即結束了，後續的遞歸都沒有展開。
這個 O(9^M) 的複雜度實際上是完全窮舉，或者說是找到
所有可行解的時間複雜度。
如果給定的數字越少，相當于給出的限制條件越少，對于計算機這種窮舉政策來說，是更容易進行下去，而不容易走回頭路進行回溯的，是以說
如果僅僅找出一個可行解，這種情況下窮舉的速度反而比較快。
至此，回溯算法就完成了，你可以用以上代碼通過 LeetCode 的判題系統，下面我們來簡單說下我是如何把這個回溯過程可視化出來的。
三、算法可視化
讓算法幫我玩遊戲的核心是算法，如果你了解了這個算法，剩下就是借助安卓腳本引擎 Auto.js 調 API 操作手機了，工具我都放在背景了，你等會兒就可以下載下傳。
用僞碼簡單說下思路，我可以寫兩個函數：
void setNum(Button b, char n) {
// 輸入一個方格，将該方格設定為數字 n
}
void cancelNum(Button b) {
// 輸入一個方格，将該方格上的數字撤銷
}
回溯算法的核心架構如下，
隻要在架構對應的位置加上對應的操作，即可将算法做選擇、撤銷選擇的過程完全展示出來，也許這就是套路架構的魅力所在：
for (char ch = '1'; ch <= '9'; ch++) {
Button b = new Button(r, c);
// 做選擇
setNum(b, ch);
board[i][j] = ch;
// 繼續窮舉下一個
backtrack(board, i, j + 1)
// 撤銷選擇
cancelNum(b);
board[i][j] = '.';
}
以上思路就可以模拟出算法窮舉的過程：