题解 | #数独#

class Solution {
  public:
    bool valid = false;
    void solveSudoku(vector<vector<char>>& board) {

        int n = board.size();
        vector<vector<bool>> line(n, vector(n,
                                            false)); // line[i][j] 表示在第i行上j是否存在!
        vector<vector<bool>> col(n, vector(n,
                                           false)); // col[i][j] 表示第i列上j是否存在！
        vector<vector<bool>> cell(n, vector(n,
                                            false)); // cell[i][j] 表示在 第i个3*3 的方阵上j是否存在
        vector<pair<int, int>> spaces;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                } else {
                    int val = (board[i][j] - '0') - 1;

                    int k = i / 3 * 3 + j / 3; // 当前位置所在的方阵编号！

                    line[i][val] = col[j][val] = cell[k][val] = true;
                }
            }
        }
        back_track(board, spaces, 0, line, col, cell);
    }

    void back_track(vector<vector<char>>& board, vector<pair<int, int>>& spaces,
                    int step, vector<vector<bool>>& line, vector<vector<bool>>& col,
                    vector<vector<bool>>& cell) {
        if (step == spaces.size()) {
            valid = true;
            return ;
        }

        int x = spaces[step].first, y = spaces[step].second;

        for (int val = 0; val < 9 && !valid; val++) { 
            int k = x / 3 * 3 + y / 3;
            if (!line[x][val] && !col[y][val] && !cell[k][val] ) { // 数字可以填充!
                line[x][val] = col[y][val] = cell[k][val] = true;
                board[x][y] = (val + 1 + '0'); // 尝试填充
                back_track(board, spaces, step + 1, line, col, cell); 
                line[x][val] = col[y][val] = cell[k][val] = false; // 回溯
            }
        }
    }
};