37. 解数独

从树形结构看，每次先遍历行再遍历列，是一个二维的递归（两个for循环嵌套递归）
一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！

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;                // 放置k
                    if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                    board[i][j] = '.';              // 回溯，撤销k
                }
            }
            return false;                           // 9个数都试完了，都不行，那么就返回false
        }
    }
    return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}

注意这里return false的地方，这里放return false 是有讲究的。
因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！
判断是否合法：

完整代码:

class Solution {
public:
    bool backtracking(vector<vector<char>>& board) {
        for (int i = 0; i < board.size(); i++) {//直接写9写行
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] != '.') continue; // 如果已经放置数字，则跳过
                for (char k = '1'; k <= '9'; k++) { // 尝试放置1~9
                    if (isValid(i, j, k, board)) {
                        board[i][j] = k;
                        if(backtracking(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false; // 1~9都不行，那么这个解法不对，返回false
            }
        }
        return true;
    }
    bool isValid(int row, int col, char val, vector<vector<char>>& board) {
        // 行
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == val) return false;
        }
        // 列
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == val) return false;
        }
        // 九宫格里不能有重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val ) {
                    return false;
                }
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};