如何用回溯算法來(lái)解決數(shù)獨(dú)問(wèn)題

經(jīng)常拿回溯算法來(lái)說(shuō)事兒的，無(wú)非就是八皇后問(wèn)題和數(shù)獨(dú)問(wèn)題了。那我們今天就通過(guò)實(shí)際且有趣的例子來(lái)講一下如何用回溯算法來(lái)解決數(shù)獨(dú)問(wèn)題。

一、直觀感受

說(shuō)實(shí)話我小的時(shí)候也嘗試過(guò)玩數(shù)獨(dú)游戲，但從來(lái)都沒(méi)有完成過(guò)一次。做數(shù)獨(dú)是有技巧的，我記得一些比較專業(yè)的數(shù)獨(dú)游戲軟件，他們會(huì)教你玩數(shù)獨(dú)的技巧，不過(guò)在我看來(lái)這些技巧都太復(fù)雜，我根本就沒(méi)有興趣看下去。

不過(guò)自從我學(xué)習(xí)了算法，多困難的數(shù)獨(dú)問(wèn)題都攔不住我了。下面是我用程序完成數(shù)獨(dú)的一個(gè)例子：

PS：GIF 可能出現(xiàn) bug，若卡住點(diǎn)開查看即可，下同。

這是一個(gè)安卓手機(jī)中的數(shù)獨(dú)游戲，我使用一個(gè)叫做 Auto.js 的腳本引擎，配合回溯算法來(lái)實(shí)現(xiàn)自動(dòng)完成填寫，并且算法記錄了執(zhí)行次數(shù)。

在后文，我會(huì)給出該腳本的實(shí)現(xiàn)思路代碼以及軟件工具的下載，你也可以拿來(lái)裝13用。

可以觀察到前兩次都執(zhí)行了 1 萬(wàn)多次，而最后一次只執(zhí)行了 100 多次就算出了答案，這說(shuō)明對(duì)于不同的局面，回溯算法得到答案的時(shí)間是不相同的。

那么計(jì)算機(jī)如何解決數(shù)獨(dú)問(wèn)題呢？其實(shí)非常的簡(jiǎn)單，就是窮舉嘛，下面我可視化了求解過(guò)程：

算法的核心思路非常非常的簡(jiǎn)單，就是對(duì)每一個(gè)空著的格子窮舉 1 到 9，如果遇到不合法的數(shù)字（在同一行或同一列或同一個(gè) 3×3 的區(qū)域中存在相同的數(shù)字）則跳過(guò)，如果找到一個(gè)合法的數(shù)字，則繼續(xù)窮舉下一個(gè)空格子。

對(duì)于數(shù)獨(dú)游戲，也許我們還會(huì)有另一個(gè)誤區(qū)：就是下意識(shí)地認(rèn)為如果給定的數(shù)字越少那么這個(gè)局面的難度就越大。

這個(gè)結(jié)論對(duì)人來(lái)說(shuō)應(yīng)該沒(méi)毛病，但對(duì)于計(jì)算機(jī)而言，給的數(shù)字越少，反而窮舉的步數(shù)就越少，得到答案的速度越快，至于為什么，我們后面探討代碼實(shí)現(xiàn)的時(shí)候會(huì)講。

上一個(gè) GIF 是最后一關(guān) 70 關(guān)，下圖是第 52 關(guān)，數(shù)字比較多，看起來(lái)似乎不難，但是我們看一下算法執(zhí)行的過(guò)程：

可以看到算法在前兩行窮舉了半天都沒(méi)有走出去，由于時(shí)間原因我就沒(méi)有繼續(xù)錄制了，事實(shí)上，這個(gè)局面窮舉的次數(shù)大概是上一個(gè)局面的 10 倍。

言歸正傳，下面我們就來(lái)具體探討一下如何用算法來(lái)求解數(shù)獨(dú)問(wèn)題，順便說(shuō)說(shuō)我是如何可視化這個(gè)求解過(guò)程的。

二、代碼實(shí)現(xiàn)

首先，我們不用管游戲的 UI，先單純地解決回溯算法，LeetCode 第 37 題就是解數(shù)獨(dú)的問(wèn)題，算法函數(shù)簽名如下：

voidsolveSudoku(char[][]board);

輸入是一個(gè)9x9的棋盤，空白格子用點(diǎn)號(hào)字符.表示，算法需要在原地修改棋盤，將空白格子填上數(shù)字，得到一個(gè)可行解。

至于數(shù)獨(dú)的要求，大家想必都很熟悉了，每行，每列以及每一個(gè) 3×3 的小方格都不能有相同的數(shù)字出現(xiàn)。那么，現(xiàn)在我們直接套回溯框架即可求解。

前文回溯算法詳解，已經(jīng)寫過(guò)了回溯算法的套路框架，如果還沒(méi)看過(guò)那篇文章的，建議先看看。

回憶剛才的 GIF 圖片，我們求解數(shù)獨(dú)的思路很簡(jiǎn)單粗暴，就是對(duì)每一個(gè)格子所有可能的數(shù)字進(jìn)行窮舉。對(duì)于每個(gè)位置，應(yīng)該如何窮舉，有幾個(gè)選擇呢？

很簡(jiǎn)單啊，從 1 到 9 就是選擇，全部試一遍不就行了：

//對(duì)board[i][j]進(jìn)行窮舉嘗試
voidbacktrack(char[][]board,inti,intj){
intm=9,n=9;
for(charch='1';ch<=?'9';ch++){
//做選擇
board[i][j]=ch;
//繼續(xù)窮舉下一個(gè)
backtrack(board,i,j+1);
//撤銷選擇
board[i][j]='.';
}
}

emmm，再繼續(xù)細(xì)化，并不是 1 到 9 都可以取到的，有的數(shù)字不是不滿足數(shù)獨(dú)的合法條件嗎？而且現(xiàn)在只是給j加一，那如果j加到最后一列了，怎么辦？

很簡(jiǎn)單，當(dāng)j到達(dá)超過(guò)每一行的最后一個(gè)索引時(shí)，轉(zhuǎn)為增加i開始窮舉下一行，并且在窮舉之前添加一個(gè)判斷，跳過(guò)不滿足條件的數(shù)字：

voidbacktrack(char[][]board,inti,intj){
intm=9,n=9;
if(j==n){
//窮舉到最后一列的話就換到下一行重新開始。
backtrack(board,i+1,0);
return;
}

//如果該位置是預(yù)設(shè)的數(shù)字，不用我們操心
if(board[i][j]!='.'){
backtrack(board,i,j+1);
return;
}

for(charch='1';ch<=?'9';ch++){
//如果遇到不合法的數(shù)字，就跳過(guò)
if(!isValid(board,i,j,ch))
continue;

board[i][j]=ch;
backtrack(board,i,j+1);
board[i][j]='.';
}
}

//判斷board[r][c]是否可以填入n
booleanisValid(char[][]board,intr,intc,charn){
for(inti=0;i9;i++){
//判斷行是否存在重復(fù)
if(board[r][i]==n)returnfalse;
//判斷列是否存在重復(fù)
if(board[i][c]==n)returnfalse;
//判斷3x3方框是否存在重復(fù)
if(board[(r/3)*3+i/3][(c/3)*3+i%3]==n)
returnfalse;
}
returntrue;
}

emmm，現(xiàn)在基本上差不多了，還剩最后一個(gè)問(wèn)題：這個(gè)算法沒(méi)有 base case，永遠(yuǎn)不會(huì)停止遞歸。這個(gè)好辦，什么時(shí)候結(jié)束遞歸？顯然r == m的時(shí)候就說(shuō)明窮舉完了最后一行，完成了所有的窮舉，就是 base case。

另外，前文也提到過(guò)，為了減少?gòu)?fù)雜度，我們可以讓backtrack函數(shù)返回值為boolean，如果找到一個(gè)可行解就返回 true，這樣就可以阻止后續(xù)的遞歸。只找一個(gè)可行解，也是題目的本意。

最終代碼修改如下：

booleanbacktrack(char[][]board,inti,intj){
intm=9,n=9;
if(j==n){
//窮舉到最后一列的話就換到下一行重新開始。
returnbacktrack(board,i+1,0);
}
if(i==m){
//找到一個(gè)可行解，觸發(fā)basecase
returntrue;
}

if(board[i][j]!='.'){
//如果有預(yù)設(shè)數(shù)字，不用我們窮舉
returnbacktrack(board,i,j+1);
}

for(charch='1';ch<=?'9';ch++){
//如果遇到不合法的數(shù)字，就跳過(guò)
if(!isValid(board,i,j,ch))
continue;

board[i][j]=ch;
//如果找到一個(gè)可行解，立即結(jié)束
if(backtrack(board,i,j+1)){
returntrue;
}
board[i][j]='.';
}
//窮舉完1~9，依然沒(méi)有找到可行解，此路不通
returnfalse;
}

booleanisValid(char[][]board,intr,intc,charn){
//見上文
}

現(xiàn)在可以回答一下之前的問(wèn)題，為什么有時(shí)候算法執(zhí)行的次數(shù)多，有時(shí)候少？為什么對(duì)于計(jì)算機(jī)而言，確定的數(shù)字越少，反而算出答案的速度越快？

我們已經(jīng)實(shí)現(xiàn)了一遍算法，掌握了其原理，回溯就是從 1 開始對(duì)每個(gè)格子窮舉，最后只要試出一個(gè)可行解，就會(huì)立即停止后續(xù)的遞歸窮舉。所以暴力試出答案的次數(shù)和隨機(jī)生成的棋盤關(guān)系很大，這個(gè)是說(shuō)不準(zhǔn)的。

那么你可能問(wèn)，既然運(yùn)行次數(shù)說(shuō)不準(zhǔn)，那么這個(gè)算法的時(shí)間復(fù)雜度是多少呢？

對(duì)于這種時(shí)間復(fù)雜度的計(jì)算，我們只能給出一個(gè)最壞情況，也就是 O(9^M)，其中M是棋盤中空著的格子數(shù)量。你想嘛，對(duì)每個(gè)空格子窮舉 9 個(gè)數(shù)，結(jié)果就是指數(shù)級(jí)的。

這個(gè)復(fù)雜度非常高，但稍作思考就能發(fā)現(xiàn)，實(shí)際上我們并沒(méi)有真的對(duì)每個(gè)空格都窮舉 9 次，有的數(shù)字會(huì)跳過(guò)，有的數(shù)字根本就沒(méi)有窮舉，因?yàn)楫?dāng)我們找到一個(gè)可行解的時(shí)候就立即結(jié)束了，后續(xù)的遞歸都沒(méi)有展開。

這個(gè) O(9^M) 的復(fù)雜度實(shí)際上是完全窮舉，或者說(shuō)是找到所有可行解的時(shí)間復(fù)雜度。

如果給定的數(shù)字越少，相當(dāng)于給出的約束條件越少，對(duì)于計(jì)算機(jī)這種窮舉策略來(lái)說(shuō)，是更容易進(jìn)行下去，而不容易走回頭路進(jìn)行回溯的，所以說(shuō)如果僅僅找出一個(gè)可行解，這種情況下窮舉的速度反而比較快。

至此，回溯算法就完成了，你可以用以上代碼通過(guò) LeetCode 的判題系統(tǒng)，下面我們來(lái)簡(jiǎn)單說(shuō)下我是如何把這個(gè)回溯過(guò)程可視化出來(lái)的。

三、算法可視化

讓算法幫我玩游戲的核心是算法，如果你理解了這個(gè)算法，剩下就是借助安卓腳本引擎 Auto.js 調(diào) API 操作手機(jī)了，工具我都放在后臺(tái)了，你等會(huì)兒就可以下載。

用偽碼簡(jiǎn)單說(shuō)下思路，我可以寫兩個(gè)函數(shù)：

voidsetNum(Buttonb,charn){
//輸入一個(gè)方格，將該方格設(shè)置為數(shù)字n
}

voidcancelNum(Buttonb){
//輸入一個(gè)方格，將該方格上的數(shù)字撤銷
}

回溯算法的核心框架如下，只要在框架對(duì)應(yīng)的位置加上對(duì)應(yīng)的操作，即可將算法做選擇、撤銷選擇的過(guò)程完全展示出來(lái)，也許這就是套路框架的魅力所在：

for(charch='1';ch<=?'9';ch++){
Buttonb=newButton(r,c);
//做選擇
setNum(b,ch);
board[i][j]=ch;
//繼續(xù)窮舉下一個(gè)
backtrack(board,i,j+1);
//撤銷選擇
cancelNum(b);
board[i][j]='.';
}

以上思路就可以模擬出算法窮舉的過(guò)程：