37. Sudoku Solver

题目描述

37. Sudoku Solver

回溯

class Solution {
    vector<vector<bool>> row_used;
    vector<vector<bool>> col_used;
    vector<vector<bool>> box_used;

public:
    void solveSudoku(vector<vector<char>>& board) {
        row_used.resize(9,vector<bool>(9,false));
        col_used.resize(9,vector<bool>(9,false));
        box_used.resize(9,vector<bool>(9,false));
        for(int row= 0;row < 9;row++){
            for(int col = 0;col < 9;col++){
                if(board[row][col] != '.'){
                    int digit = board[row][col] - '0' -1;
                    row_used[row][digit] = true;
                    col_used[col][digit] = true;
                    box_used[(row/3)*3 + col/3][digit] = true;
                }
            }
        }
        backtrack(board);
    }

    bool backtrack(vector<vector<char>>& board){
        for(int row = 0;row < 9;row++){
            for(int col = 0;col < 9;col++){
                if(board[row][col] != '.')
                    continue;
                for(int digit = 0;digit<9;digit++){
                    if(row_used[row][digit])
                        continue;
                    if(col_used[col][digit])
                        continue;
                    if(box_used[(row/3)*3+ col/3][digit])
                        continue;
                    row_used[row][digit] = true;
                    col_used[col][digit] = true;
                    box_used[(row/3)*3+ col/3][digit] = true;
                    board[row][col] = '0'+ digit + 1;
                    if(backtrack(board)) return true;
                    board[row][col] = '.';
                    row_used[row][digit] = false;
                    col_used[col][digit] = false;
                    box_used[(row/3)*3+ col/3][digit] = false;
                }
                return false;
            }
        }
        return true;
    }
};