解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

Note:
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

class Solution {
public:
    // row_used、col_used用来表示每一行、列上面1~9被使用的情况
    // box_used表示每一方块中数字被使用的情况
    bool row_used[9][9], col_used[9][9], box_used[3][3][9];
    void solveSudoku(vector<vector<char>>& board) {
        // 初始化
        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                row_used[i][j] = false;
                col_used[i][j] = false;
            }
        }
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                for(int k = 0; k < 9; ++k) {
                    box_used[i][j][k] = false;
                }
            }
        }
        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                if(board[i][j] != '.') {
                    row_used[i][board[i][j] - '1'] = true;
                    col_used[j][board[i][j] - '1'] = true;
                    box_used[i/3][j/3][board[i][j] - '1'] = true; 
                }
            }
        }
        solve(board, 0);
    }
    // 遍历每一种情况，然后判断该数字的加入是否符合规则，判断在该行和该列、块是否是存在重复
    bool solve(vector<vector<char>>& board, int index) {
        if(index >= 81)
            return true;
        // 计算出行列
        int row = index / 9;
        int col = index % 9;
        if(board[row][col] == '.') {
            // 该位置属于空格，需要填写数字
            for(int i = 0; i < 9; ++i) {
                if(!row_used[row][i] && !col_used[col][i] && !box_used[row/3][col/3][i]) {
                    board[row][col] = i + '1';
                    row_used[row][i] = true;
                    col_used[col][i] = true;
                    box_used[row/3][col/3][i] = true;
                    if(solve(board, index + 1))
                        return true;
                    // 如果这种方案不成功则还原
                    else {
                        row_used[row][i] = false;
                        col_used[col][i] = false;
                        box_used[row/3][col/3][i] = false;
                        board[row][col] = '.';
                    }
                }
            }
        }
        else 
            return solve(board, index + 1);
        // if 里面的for循环可能会遍历完，那么就是所有的方案都不成立
        // 易错点
        return false;
    }
};