目錄

• • 題目
  • 核心思路的不斷細化
  • • 1、核心框架
    • 2、考慮到每個位置的工作
    • 3、考慮到到達最后一列、該位置的數已經預置的情況
    • 4、判斷是否符合規則的函數
    • 5、確定遞歸終止條件+確定函數返回值
  • AC代碼

題目

編寫一個程序，通過填充空格來解決數獨問題。
一個數獨的解法需遵循如下規則：

1、數字 1-9 在每一行只能出現一次。
2、數字 1-9 在每一列只能出現一次。
3、數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

空白格用 ‘.’ 表示。

一個數獨。

答案被標成紅色。

提示：

給定的數獨序列只包含數字 1-9 和字符 ‘.’ 。
你可以假設給定的數獨只有唯一解。
給定數獨永遠是 9x9 形式的。

核心思路的不斷細化

算法的核心思路就是對每一個空著的格子窮舉 1 到 9，如果遇到不合法的數字（在同一行或同一列或同一個 3×3 的區域中存在相同的數字）則跳過，如果找到一個合法的數字，則繼續窮舉下一個空格子。
寫出核心框架：

1、核心框架

void solveSudoku(vector<vector<char>>& board) {backtrack(board, 0, 0);
}void backtrack(vector<vector<char>>& board, int hang, int lie) {// 就是對棋盤的每個位置進行窮舉for (int i = hang; i < 9; i++) {for (int j = lie; j < 9; j++) {// 做選擇backtrack(board, i, j);// 撤銷選擇}}
}

2、考慮到每個位置的工作

對于每個位置有1~9的選擇，這樣就變成了3重嵌套循環。

void backtrack(vector<vector<char>>& board, int hang, int lie) {// 就是對每個位置進行窮舉for (int i = hang; i < 9; i++) {for (int j = lie; j < 9; j++) {for (char ch = '1'; ch <= '9'; ch++) {// 做選擇board[i][j] = ch;// 繼續窮舉下一列，backtrack(board, i, j + 1);// 撤銷選擇board[i][j] = '.';}}}
}

3、考慮到到達最后一列、該位置的數已經預置的情況

1、當lie到達超過最后一個索引時，轉為增加hang開始窮舉下一行。
2、如果當前位置元素不為“.”，那么跳過即可。
3、窮舉的時候如果遇到符合規則的數字，填入，否則跳過。

void backtrack(vector<vector<char>>& board, int hang, int lie) {if(lie==9){backtrack(board, hang+1, 0);}// 就是對每個位置進行窮舉for (int i = hang; i < 9; i++) {for (int j = lie; j < 9; j++) {// 如果該位置是預設的數字，不用我們操心if (board[i][j] != '.') {backtrack(board, i, j + 1);return;} //如果不是預置的數字for (char ch = '1'; ch <= '9'; ch++) {// 如果遇到符合規則的數字，填入if (isValid(board, i, j, ch)){// 做選擇board[i][j] = ch;// 繼續窮舉下一列，backtrack(board, i, j + 1);// 撤銷選擇board[i][j] = '.';}}}}
}

4、判斷是否符合規則的函數

規則如下：

1、數字 1-9 在每一行只能出現一次。
2、數字 1-9 在每一列只能出現一次。
3、數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

翻譯成函數：
注意這里對第3個規則的描述：

// 判斷 board[i][j] 是否可以填入 n
bool isValid(vector<vector<char>>& board, int hang, int lie, char n) {for (int i = 0; i < 9; i++) {// 判斷行是否存在重復if (board[hang][i] == n) return false;// 判斷列是否存在重復if (board[i][lie] == n) return false;// 判斷 3 x 3 方框是否存在重復if (board[(hang/3)*3 + i/3][(lie/3)*3 + i%3] == n)return false;}return true;
}

下面是這個式子的含義，并且將i=0~8模擬了一下：

5、確定遞歸終止條件+確定函數返回值

如果遞歸完最后一行，那么我們就可以返回我們的結果了。
如果找到一個解我們的任務就結束了，本題并沒有要求找到所有解。
如果一個位置遍歷完所有數字，都不符合，這說明此路不通，應該及時返回false。
如果每個位置都遍歷過了，結果都沒有返回true，說明，這個數獨棋盤沒有解，返回false。
所以使用bool類型的值作為返回值：

if(hang == 9) return true;

完整的回溯函數代碼應該如下：

bool backtrack(vector<vector<char>>& board, int hang, int lie) {//遍歷完這一行最后一列，轉而遍歷下一行if(lie==9){return backtrack(board, hang+1, 0);}//找到一個解，返回if(hang == 9) return true;// 就是對每個位置進行窮舉for (int i = hang; i < 9; i++) {for (int j = lie; j < 9; j++) {// 如果該位置是預設的數字，不用我們操心if (board[i][j] != '.') {return backtrack(board, i, j + 1);} //如果不是預置的數字for (char ch = '1'; ch <= '9'; ch++) {// 如果遇到符合規則的數字，填入if (isValid(board, i, j, ch)){// 做選擇board[i][j] = ch;// 繼續窮舉下一列，如果找到了一個解，立即結束if(backtrack(board, i, j + 1) == true) return true;// 撤銷選擇board[i][j] = '.';}}// 窮舉完 1~9，依然沒有找到可行解，此路不通return false;}}return false;
}

AC代碼

class Solution {
public:// 判斷 board[i][j] 是否可以填入 nbool isValid(vector<vector<char>>& board, int hang, int lie, char n) {for (int i = 0; i < 9; i++) {// 判斷行是否存在重復if (board[hang][i] == n) return false;// 判斷列是否存在重復if (board[i][lie] == n) return false;// 判斷 3 x 3 方框是否存在重復if (board[(hang/3)*3 + i/3][(lie/3)*3 + i%3] == n)return false;}return true;}bool backtrack(vector<vector<char>>& board, int hang, int lie) {//遍歷完這一行最后一列，轉而遍歷下一行if(lie==9){return backtrack(board, hang+1, 0);}//找到一個解，返回if(hang == 9) return true;// 就是對每個位置進行窮舉for (int i = hang; i < 9; i++) {for (int j = lie; j < 9; j++) {// 如果該位置是預設的數字，不用我們操心if (board[i][j] != '.') {return backtrack(board, i, j + 1);} //如果不是預置的數字for (char ch = '1'; ch <= '9'; ch++) {// 如果遇到符合規則的數字，填入if (isValid(board, i, j, ch)){// 做選擇board[i][j] = ch;// 繼續窮舉下一列，如果找到了一個解，立即結束if(backtrack(board, i, j + 1) == true) return true;// 撤銷選擇board[i][j] = '.';}}// 窮舉完 1~9，依然沒有找到可行解，此路不通return false;}}return false;}void solveSudoku(vector<vector<char>>& board) {backtrack(board, 0, 0);return;}
};