37. 解数独

Introduction

Question：37. 解数独

Analysis

又是一道回溯的题目。

回溯的套路其实还是挺明显的，先是把解空间定义好（这道题已经定义好了），然后在递归的逐个去求解（尝试）每个解，再通过一些限定条件去剪枝即可。

这道题剪枝条件也很明显，就是题目给出的规则。然后如果剪枝时直接暴力求解的话，还是会出问题的。由于频繁的调用，所以剪枝的判定时间复杂度一定要低。

为了加快判断：

1. 每次填入数字时，只判断其所在行，所在列，所在9宫格中是否已经存在该数字了，而不是进行全局的判断。
2. 用bitset加快判断数字是否存在。

Implement

vector<bitset<9>> rows;
vector<bitset<9>> cols;
vector<vector<bitset<9>>> spaces;
Solution(): rows(9, bitset<9>()), cols(9, bitset<9>()){
    for(int i = 0;i < 3;i++) {
        spaces.push_back({});
        for(int j = 0;j < 3;j++) {
            spaces[i].push_back({});
        }
    }
}

inline bool check(int i, int j, int v) {
    return !rows[i][v] && !cols[j][v] && !spaces[i/3][j/3][v];
}
inline void set(int i, int j, int v) {
    rows[i].set(v);
    cols[j].set(v);
    spaces[i/3][j/3].set(v);
}
inline void reset(int i, int j, int v) {
    rows[i].reset(v);
    cols[j].reset(v);
    spaces[i/3][j/3].reset(v);
}
void solveSudoku(vector<vector<char>>& board) {

    for(int i = 0;i < 9;i++) {
        for(int j = 0;j < 9;j++) {
            if (board[i][j] == '.') continue;
            set(i, j, board[i][j] - '1');
        }
    }
    solveSudoku(board, 0, 0);
}
bool solveSudoku(vector<vector<char>>& board, int i, int j) {
    if (j == 9) return solveSudoku(board, i + 1, 0);
    if (i == 9) return true;

    if (board[i][j] != '.') return solveSudoku(board, i, j + 1);

    for(char v = '1'; v <= '9';v++) {
        if (!check(i, j, v - '1')) continue;

        board[i][j] = v;
        set(i, j, v - '1');

        if (solveSudoku(board, i, j + 1))
            return true;

        board[i][j] = '.';
        reset(i, j, v - '1');
    }
    return false;
}

One More Thing