数独

C++ 解法, 执行用时: 1ms, 内存消耗: 500KB, 提交时间: 2017-08-22

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        vector<vector<int>> map(3, vector<int>(9,0));
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'){
                    map[0][i] |= (1<<(board[i][j]-'0'));
                    map[1][j] |= (1<<(board[i][j]-'0'));
                    map[2][i/3*3+j/3] |= (1<<(board[i][j]-'0'));
                }
            }
        }
        processSudoku(board, 0, map);
    }
    bool processSudoku(vector<vector<char> > &board, int start, vector<vector<int>> &map) {
        if(start>=81)return true;
        for(; start<81; start++){
            if(board[start/9][start%9] != '.'){
                continue;
            }
            int mask = (map[0][start/9]) | (map[1][start%9]) | (map[2][start/9/3*3+start%9/3]);
            for(int tryNum=1; tryNum<=9; tryNum++){
                if((mask & (1<< tryNum)) == 0){
                    board[start/9][start%9] = tryNum + '0';
                    map[0][start/9] |= (1<<tryNum);
                    map[1][start%9] |= (1<<tryNum);
                    map[2][start/9/3*3+start%9/3] |= (1<<tryNum);
                    if(processSudoku(board, start+1, map)){
                        return true;
                    }
                    board[start/9][start%9] = '.';
                    map[0][start/9] ^= (1<<tryNum);
                    map[1][start%9] ^= (1<<tryNum);
                    map[2][start/9/3*3+start%9/3] ^= (1<<tryNum);
                }
            }
            return false;
        }
        return true;
    }
};

C++ 解法, 执行用时: 1ms, 内存消耗: 504KB, 提交时间: 2017-08-10

class Solution {
private:
    int N;
public:
    bool dfs(vector<vector<char>>& board, int i, int j, vector<vector<bool> >& rows, vector<vector<bool> >& cols,vector<vector<bool> >& sques){
            if(board[i][j] != '.'){
                if(j < N - 1){
                    return dfs(board, i, j + 1, rows, cols, sques);
                }
                else if(i < N - 1){
                    return dfs(board, i + 1, 0, rows, cols, sques);
                }
                else return true;
            }
            else{
                for(int k = 0; k < N; ++k){
                    if(!rows[i][k] && !cols[j][k] && !sques[i/3 * 3 + j/3][k]){
                        board[i][j] = k + '0' + 1;
                        rows[i][k] = true;
                        cols[j][k] = true;
                        sques[i/3 * 3 + j/3][k] = true;
                        bool tmp = false;
                        if(j < N - 1){
                            tmp = dfs(board, i, j + 1, rows, cols, sques);
                        }
                        else if(i < N - 1){
                            tmp = dfs(board, i + 1, 0, rows, cols, sques);
                        }
                        else return true;
                        if(tmp) return true;
                        else{
                            board[i][j] = '.';
                            rows[i][k] = false;
                            cols[j][k] = false;
                            sques[i/3 * 3 + j/3][k] = false;
                        }
                    }
                }
                return false;
            }
    }
    void solveSudoku(vector<vector<char> > &board) {
        N = 9;
        vector<vector<bool> > rows(N, vector<bool>(N, false));
        vector<vector<bool> > cols(N, vector<bool>(N, false));
        vector<vector<bool> > sques(N, vector<bool>(N, false));
        
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                if(board[i][j] != '.' ){
                    int tmp = board[i][j] - '0' - 1;
                    rows[i][tmp] = true;
                    cols[j][tmp] = true;
                    sques[i/3 * 3 + j/3][tmp] = true;
                }
            }
        }
        dfs(board, 0, 0, rows, cols, sques);
        return;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 460KB, 提交时间: 2021-06-26

class Solution {
public:
    vector<int> row_record, col_record, square_record;
    vector<pair<int, int>> record;   int len;
    void solveSudoku(vector<vector<char> > &board) {
        row_record = vector<int>(9, 0);
        col_record = vector<int>(9, 0);
        square_record = vector<int>(9, 0);   int pos;
        for(int i=0; i<9; i++){
            vector<char> &curRow = board[i];
            for(int j=0; j<9; j++){
                if(curRow[j] != '.'){
                    pos = 1 << curRow[j]-'0';
                    row_record[i] |= pos;
                    col_record[j] |= pos;
                    square_record[ i/3*3+j/3 ] |= pos;
                    continue;
                }
                record.push_back( {i, j} );
            }
        }
        len = record.size();   DFS(board, 0);
    }
    
    bool DFS(vector<vector<char> > &board, int idx)
    {
        if(idx == len) return true;
        int x = record[idx].first, y = record[idx].second, square_idx = x/3*3+y/3;
        int valid = ~(row_record[x] | col_record[y] | square_record[square_idx]) & 0x3FE, pos;
        while(valid)
        {
            pos = valid & 0-valid;
            row_record[x] |= pos;
            col_record[y] |= pos;
            square_record[square_idx] |= pos;
            
            board[x][y] = '0'+__builtin_ctz(pos);
            if( DFS(board, idx+1) ) return true;
            
            row_record[x] ^= pos;
            col_record[y] ^= pos;
            square_record[square_idx] ^= pos;
            
            valid &= valid-1;
        }
        board[x][y] = '.';
        return false;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 360KB, 提交时间: 2020-10-04

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        vector<vector<int>> arr(3,vector<int>(9,0));
        for(int i= 0;i<9;i++){
            for(int j= 0;j<9;j++){
                if(board[i][j]!='.'){
                    int tmp= board[i][j]-'0';
                    int tmp2= i/3*3+j/3;
                    arr[0][i]|=(1<<tmp);
                    arr[1][j]|=(1<<tmp);
                    arr[2][tmp2]|=(1<<tmp);
                }
            }
        }
        processSudoku(board,0,arr);
    }
    bool processSudoku(vector<vector<char> > &board, int start, vector<vector<int>> &map) {
        if(start>=81)return true;
        for(; start<81; start++){
            if(board[start/9][start%9] != '.'){
                continue;
            }
            int mask = (map[0][start/9]) | (map[1][start%9]) | (map[2][start/9/3*3+start%9/3]);
            for(int tryNum=1; tryNum<=9; tryNum++){
                if((mask & (1<< tryNum)) == 0){
                    board[start/9][start%9] = tryNum + '0';
                    map[0][start/9] |= (1<<tryNum);
                    map[1][start%9] |= (1<<tryNum);
                    map[2][start/9/3*3+start%9/3] |= (1<<tryNum);
                    if(processSudoku(board, start+1, map)){
                        return true;
                    }
                    board[start/9][start%9] = '.';
                    map[0][start/9] ^= (1<<tryNum);
                    map[1][start%9] ^= (1<<tryNum);
                    map[2][start/9/3*3+start%9/3] ^= (1<<tryNum);
                }
            }
            return false;
        }
        return true;
    }
        bool suduku(vector<vector<char>> &board,vector<vector<int>> &arr,int sta){
            if(sta>=81) return true;
            for(;sta<81;sta++){
                if(board[sta/9][sta%9]!='.')
                    continue;
                int tmp= sta/9/3*3+(sta%9)/3;
                int num_ch= (arr[0][sta/9])|(arr[1][sta%9])|(arr[2][tmp]);
                for(int num=1;num<=9;num++){
                    if(num_ch &(1<<num)==0){
                        board[sta/9][sta%9]= num+'0';
                        arr[0][sta/9]|=(1<<num);
                        arr[1][sta%9]|=(1<<num);
                        arr[2][tmp]|=(1<<num);
                        if(suduku(board,arr,sta+1))
                            return true;
                        board[sta/9][sta%9]= '.';
                        arr[0][sta/9]^=(1<<num);
                        arr[1][sta%9]^=(1<<num);
                        arr[2][tmp]^=(1<<num);
                    }
                }
                return false;
            }
            return true;
        }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-10-17

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        vector<vector<int>> map(3, vector<int>(9,0));
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'){
                    map[0][i] |= (1<<(board[i][j]-'0'));
                    map[1][j] |= (1<<(board[i][j]-'0'));
                    map[2][i/3*3+j/3] |= (1<<(board[i][j]-'0'));
                }
            }
        }
        processSudoku(board, 0, map);
    }
    bool processSudoku(vector<vector<char> > &board, int start, vector<vector<int>> &map) {
        if(start>=81)return true;
        for(; start<81; start++){
            if(board[start/9][start%9] != '.'){
                continue;
            }
            int mask = (map[0][start/9]) | (map[1][start%9]) | (map[2][start/9/3*3+start%9/3]);
            for(int tryNum=1; tryNum<=9; tryNum++){
                if((mask & (1<< tryNum)) == 0){
                    board[start/9][start%9] = tryNum + '0';
                    map[0][start/9] |= (1<<tryNum);
                    map[1][start%9] |= (1<<tryNum);
                    map[2][start/9/3*3+start%9/3] |= (1<<tryNum);
                    if(processSudoku(board, start+1, map)){
                        return true;
                    }
                    board[start/9][start%9] = '.';
                    map[0][start/9] ^= (1<<tryNum);
                    map[1][start%9] ^= (1<<tryNum);
                    map[2][start/9/3*3+start%9/3] ^= (1<<tryNum);
                }
            }
            return false;
        }
        return true;
    }
};

详情