37. 解数独

题目链接

解题思路：整体思路是一个回溯，一行一行填。然后填的过程中可以剪枝，也就是我们可以添加一些约束条件，不能填的时候，就没必要去尝试了（还有一种填法，全部填完之后，再检查是否合规，这样复杂度太大了）。具体细节看代码。

代码

class Solution {
public:
    //   0～8行，0～8列，一行一行填
    // 现在来到i行，j列，row[x][y]是行限制，若为true，则说明第x行，y这个数字已经填过了
    // col[x][y]是列限制，若为true，则说明第x列，y这个数字已经填过了
    // blk[x][y]是块限制，若为true，则说明第x块，y这个数字已经填过了，对于[i,j]是 i / 3 * 3 + j / 3块
    bool process(vector<vector<char>>& board, int i, int j, vector<vector<bool>> &row, vector<vector<bool>> &col
    , vector<vector<bool>> &blk) {
        if (i == 9) {    // 全部填完了
            return true;
        }
        int nexti = j == 8? i + 1 : i;    // 下一个要填的行
        int nextj = j == 8 ? 0 : j + 1;   // 下一个要填的列
        if (board[i][j] != '.') {     // 如果不需要填，则填下一个位置
            
            return process(board, nexti, nextj, row, col, blk);
        }
        // 该位置需要填，填什么？循环遍历1～9
        for (int num = 1; num <= 9; ++num) {
            bool next = false;
            if (row[i][num] || col[j][num] || blk[i / 3 * 3 + j / 3][num]) {     // 不能填
                continue;
            }
            // 目前可以填
            board[i][j] = num + '0';
            // 添加约束
            row[i][num] = true;
            col[j][num] = true;
            blk[i / 3 * 3 + j / 3][num] = true;
            next = process(board, nexti, nextj, row, col, blk);
            if (next) {    // 如果填好了  直接返回了
                return true;
            }
            board[i][j] = '.';     // 恢复现场
            row[i][num] = false;
            col[j][num] = false;
            blk[i / 3 * 3 + j / 3][num] = false;
        }
        // 都没有满足
        return false;

    }

    void solveSudoku(vector<vector<char>>& board) {
    
        vector<vector<bool>> row(9, vector<bool>(10, false));
        vector<vector<bool>> col(9, vector<bool>(10, false));
        vector<vector<bool>> blk(9, vector<bool>(10, false));
        // 添加约束
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    continue;
                }
                row[i][board[i][j] - '0'] = true;
                col[j][board[i][j] - '0'] = true;
                blk[i / 3 * 3 + j / 3][board[i][j] - '0'] = true;
            }
        }
        process(board, 0, 0, row, col, blk);
    }
};