37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

> 我的解法

class Solution {
private:
    bool isValid(int tuple,int column,char val,vector<vector<char>>& board){
        //get the top-left location
        int x = tuple - tuple % 3;  
        int y = column - column % 3;
        for(int i = 0;i < 3;i++){
            for(int j = 0;j < 3;j++){
                if(board[x+i][y+j] == val){
                    return false;
                }
            }
        }
        for(int i =0;i < 9;i++){
            if(board[tuple][i] == val){
                return false;
            }
        }
        for(int i =0;i < 9;i++){
            if(board[i][column] == val){
                return false;
            }
        }
        return true;
    }
    bool backtracking(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {        // 遍历行
            for (int j = 0; j < 9; 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;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};