嗚嗚嗚，代碼隨想錄，算法不迷路 強推！

思路

棋盤搜索問題可以使用回溯法暴力搜索，只不過這次我們要做的是「二維遞歸」。

怎么做二維遞歸呢？

N皇后問題是因為每一行每一列只放一個皇后，只需要一層for循環(huán)遍歷行，遞歸來遍歷列，然后一行一列確定皇后的唯一位置。

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

因為這個樹形結(jié)構(gòu)太大了，我抽取一部分，如圖所示：

回溯三部曲

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

因為解數(shù)獨找到一個符合的條件（就在樹的葉子節(jié)點上）立刻就返回，相當于找從根節(jié)點到葉子節(jié)點一條唯一路徑，所以需要使用bool返回值。

bool backtracking(vector<vector<char>>& board)

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

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

遞歸的下一層的棋盤一定比上一層的棋盤多一個數(shù)，等數(shù)填滿了棋盤自然就終止（填滿當然好了，說明找到結(jié)果了），所以不需要終止條件！

「那么有沒有永遠填不滿的情況呢？」

這個問題我在遞歸單層搜索邏輯里在來講！

遞歸單層搜索邏輯

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

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

bool backtracking(vector<vector<char>>& board) {for (int i = 0; i < board.size(); i++) { // 遍歷行for (int j = 0; j < board[0].size(); j++) { // 遍歷列if (board[i][j] != '.') continue;for (char k = '1'; k <= '9'; k++) { // (i, j) 這個位置放k是否合適if (isValid(i, j, k, board)) { board[i][j] = k; // 放置kif (backtracking(board)) return true; // 如果找到合適一組立刻返回board[i][j] = '.'; // 回溯，撤銷k}}return false; // 9個數(shù)都試完了，都不行，那么就返回false}}return true; // 遍歷完沒有返回false，說明找到了合適棋盤位置了 }

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

因為如果一行一列確定下來了，這里嘗試了9個數(shù)都不行，說明這個棋盤找不到解決數(shù)獨問題的解！

那么會直接返回， 「這也就是為什么沒有終止條件也不會永遠填不滿棋盤而無限遞歸下去！」

判斷棋盤是否合法

bool isValid(int row, int col, char val, vector<vector<char>>& board) {for (int i = 0; i < 9; i++) { // 判斷行里是否重復(fù)if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判斷列里是否重復(fù)if (board[j][col] == val) {return false;}}//結(jié)合圖中方格推算int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判斷9方格里是否重復(fù)for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true; }

int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
這兩行代碼可能會難想一些，簡單來看，圖中給定了3x3宮格的規(guī)定。那么我們可以看出，當判斷一個位要放置的數(shù)是否合法時，我們傳入當前行和列。那么根據(jù)圖我們可以看出，當傳入行為0_{2之中的某個時，映射都是從0行開始。當傳入行在3}5之中的某個時，映射都是從3行開始，以此類推，對于列也是如此。所以加上一點數(shù)學知識，row/3實際是將某行映射到對應(yīng)宮格的首部，*3則是準確確定是哪一行。

整體代碼

class Solution { private: bool backtracking(vector<vector<char>>& board) {for (int i = 0; i < board.size(); i++) { // 遍歷行for (int j = 0; j < board[0].size(); j++) { // 遍歷列if (board[i][j] != '.') continue;for (char k = '1'; k <= '9'; k++) { // (i, j) 這個位置放k是否合適if (isValid(i, j, k, board)) { board[i][j] = k; // 放置kif (backtracking(board)) return true; // 如果找到合適一組立刻返回board[i][j] = '.'; // 回溯，撤銷k}}return false; // 9個數(shù)都試完了，都不行，那么就返回false}}return true; // 遍歷完沒有返回false，說明找到了合適棋盤位置了 } bool isValid(int row, int col, char val, vector<vector<char>>& board) {for (int i = 0; i < 9; i++) { // 判斷行里是否重復(fù)if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判斷列里是否重復(fù)if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判斷9方格里是否重復(fù)for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true; } public:void solveSudoku(vector<vector<char>>& board) {backtracking(board);} };

總結(jié)

以上是生活随笔為你收集整理的解数独-难哭了的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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