解數(shù)獨(dú)，理解二維遞歸是關(guān)鍵！

通知：我將公眾號(hào)文章和學(xué)習(xí)相關(guān)的資料整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在電腦上學(xué)習(xí)，可以fork到自己倉(cāng)庫(kù)，順便也給個(gè)star支持一波吧！

37. 解數(shù)獨(dú)

題目地址：https://leetcode-cn.com/problems/sudoku-solver/

編寫(xiě)一個(gè)程序，通過(guò)填充空格來(lái)解決數(shù)獨(dú)問(wèn)題。

一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則：
數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。
空白格用 '.' 表示。

一個(gè)數(shù)獨(dú)。

答案被標(biāo)成紅色。

提示：

• 給定的數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 。
• 你可以假設(shè)給定的數(shù)獨(dú)只有唯一解。
• 給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。

思路

棋盤(pán)搜索問(wèn)題可以使用回溯法暴力搜索，只不過(guò)這次我們要做的是「二維遞歸」。

怎么做二維遞歸呢？

大家已經(jīng)跟著「代碼隨想錄」刷過(guò)了如下回溯法題目，例如：77.組合(組合問(wèn)題)，131.分割回文串(分割問(wèn)題)，78.子集(子集問(wèn)題)，46.全排列(排列問(wèn)題)，以及51.N皇后(N皇后問(wèn)題)，其實(shí)這些題目都是一維遞歸。

經(jīng)典面試題目「回溯算法」N皇后問(wèn)題 是因?yàn)槊恳恍忻恳涣兄环乓粋€(gè)皇后，只需要一層for循環(huán)遍歷一行，遞歸來(lái)來(lái)遍歷列，然后一行一列確定皇后的唯一位置。

本題就不一樣了，「本題中棋盤(pán)的每一個(gè)位置都要放一個(gè)數(shù)字，并檢查數(shù)字是否合法，解數(shù)獨(dú)的樹(shù)形結(jié)構(gòu)要比N皇后更寬更深」。

因?yàn)檫@個(gè)樹(shù)形結(jié)構(gòu)太大了，我抽取一部分，如圖所示：

回溯三部曲

• 遞歸函數(shù)以及參數(shù)

「遞歸函數(shù)的返回值需要是bool類型，為什么呢？」

因?yàn)榻鈹?shù)獨(dú)找到一個(gè)符合的條件(就在樹(shù)的葉子節(jié)點(diǎn)上)立刻就返回，相當(dāng)于找從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)一條唯一路徑，所以需要使用bool返回值，這一點(diǎn)在回溯算法：N皇后問(wèn)題中已經(jīng)介紹過(guò)了，一樣的道理。

代碼如下：

bool?backtracking(vector>&?board)

• 遞歸終止條件

本題遞歸不用終止條件，解數(shù)獨(dú)是要遍歷整個(gè)樹(shù)形結(jié)構(gòu)尋找可能的葉子節(jié)點(diǎn)就立刻返回。

「不用終止條件會(huì)不會(huì)死循環(huán)？」

遞歸的下一層的棋盤(pán)一定比上一層的棋盤(pán)多一個(gè)數(shù)，等數(shù)填滿了棋盤(pán)自然就終止(填滿當(dāng)然好了，說(shuō)明找到結(jié)果了)，所以不需要終止條件！

「那么有沒(méi)有永遠(yuǎn)填不滿的情況呢？」

這個(gè)問(wèn)題我在遞歸單層搜索邏輯里在來(lái)講！

• 遞歸單層搜索邏輯

在樹(shù)形圖中可以看出我們需要的是一個(gè)二維遞歸(也就是兩個(gè)for循環(huán)嵌套著遞歸)

「一個(gè)for循環(huán)遍歷棋盤(pán)的行，一個(gè)for循環(huán)遍歷棋盤(pán)的列，一行一列確定下來(lái)之后，遞歸遍歷這個(gè)位置放9個(gè)數(shù)字的可能性！」

代碼如下：(「詳細(xì)看注釋」)

bool?backtracking(vector>&?board)?{????for?(int?i?=?0;?i?

「注意這里return false的地方，這里放return false 是有講究的」。

因?yàn)槿绻恍幸涣写_定下來(lái)了，這里嘗試了9個(gè)數(shù)都不行，說(shuō)明這個(gè)棋盤(pán)找不到解決數(shù)獨(dú)問(wèn)題的解！

那么會(huì)直接返回， 「這也就是為什么沒(méi)有終止條件也不會(huì)永遠(yuǎn)填不滿棋盤(pán)而無(wú)限遞歸下去！」

判斷棋盤(pán)是否合法

判斷棋盤(pán)是否合法有如下三個(gè)維度：

• 同行是否重復(fù)
• 同列是否重復(fù)
• 9宮格里是否重復(fù)

代碼如下：

bool?isValid(int?row,?int?col,?char?val,?vector>&?board)?{????for?(int?i?=?0;?i?

最后整體代碼如下：

C++代碼

class?Solution?{private:bool?backtracking(vector>&?board)?{????for?(int?i?=?0;?i?>&?board)?{????for?(int?i?=?0;?i?>&?board)?{????????backtracking(board);????}};

總結(jié)

解數(shù)獨(dú)可以說(shuō)是非常難的題目了，如果還一直停留在單層遞歸的邏輯中，這道題目可以讓大家瞬間崩潰。

所以我在開(kāi)篇就提到了「二維遞歸」，這也是我自創(chuàng)詞匯，希望可以幫助大家理解解數(shù)獨(dú)的搜索過(guò)程。

一波分析之后，在看代碼會(huì)發(fā)現(xiàn)其實(shí)也不難，唯一難點(diǎn)就是理解「二維遞歸」的思維邏輯。

「這樣，解數(shù)獨(dú)這么難的問(wèn)題，也被我們攻克了」。

「恭喜一路上堅(jiān)持打卡的錄友們，回溯算法已經(jīng)接近尾聲了，接下來(lái)就是要一波總結(jié)了」。

更多精彩點(diǎn)擊下方了解更多！

總結(jié)

以上是生活随笔為你收集整理的面试题目_经典面试题目「回溯算法」解数独的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。