###### tags: `LeetCode` `Recursion` `Hard` `DFS`
# LeetCode #37 [Sudoku Solver](https://leetcode.com/problems/sudoku-solver/)
### (Hard)

編寫一個程式，通過填充空格來解決數獨問題。

數獨的解法需 遵循如下規則：

數字 1-9 在每一行只能出現一次。
數字 1-9 在每一列只能出現一次。
數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。 （請參考示例圖）
數獨部分空格內已填入了數字，空白格用 '.' 表示。

 

---

要點有二:
1. 判斷插入數字的合法性(同行無重複、同列無重複、同九宮格無重複)
2. 如何遍歷每一個點

第1點很好解決, 重點是第2點。

第2點的解決方法是通過類似進位的方式, 每當跑完最後一行時(j==9), 就進位, 改為嘗試下一列的第一行的數(i=i+1, j=0), 而當列數到達9時(0~8共9列), 則代表遍歷完整個數獨, 此時回傳真。

另外, 與其他DFS不同的點在於終止條件, 這題的遞迴函式類別為bool而非void(當整個DFS跑完後, 就必須回傳, 因為答案只有一個而且所有數獨盤共享同一個參考, 若不及時回傳會把正確答案給改掉), 遞迴呼叫下一行(i, j+1), 而回傳條件則是當下一遞迴回傳true時回傳true, 否則回傳false。

若遍歷到的數獨格已存在數字, 則該數字為預先填好的題目數字, 此時直接跳過可以省去時間。

---

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board, 0, 0);
    }
    bool isvalid(vector<vector<char>>& board, int i, int j, char c){
        int ii=i-i%3;
        int jj=j-j%3;
        for(int k=0;k<9;k++)if(board[k][j]==c)return false;
        for(int k=0;k<9;k++)if(board[i][k]==c)return false;
        for(int x=ii;x<ii+3;x++){
            for(int y=jj;y<jj+3;y++){
                if(board[x][y]==c)return false;
            }
        }
        return true;
    }
    bool dfs(vector<vector<char>>& board, int i, int j){
        if(i==9)return true;
        if(j==9)return dfs(board, i+1, 0);
        if(isdigit(board[i][j]))return dfs(board, i, j+1);
        for(char c='1';c<='9';c++){
            if(isvalid(board, i, j, c)){
                board[i][j]=c;
                if(dfs(board, i, j+1))return true;
                board[i][j]='.';
            }
        }
        return false;
    }
};