A 6ms C++ Solution Using DFS and Bit Manipulation


  • 0
    Y
    class Solution { // 6ms
    public:
        void solveSudoku(vector<vector<char> > &board) {
            mark(board);
            dfs(board, 0);
        }
    
    private:
        int used_num[3][9];
        bool used_block[9][9];
        bool status = false;
    
        void mark(vector<vector<char> > &board) {
            int temp;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    used_block[i][j] = (board[i][j] != '.');
                    if (used_block[i][j]) {
                        temp = 1 << (board[i][j] - '1');
                        used_num[0][i] |= temp;
                        used_num[1][j] |= temp;
                        used_num[2][i / 3 * 3 + j / 3] |= temp;
                    }
                }
            }
        }
    
        void mark(vector<vector<char> > &board, int row, int col, int num, bool type) {
            int temp = (1 << num);
            if (type) {
                board[row][col] = char(num + '1');
                used_block[row][col] = true;
                used_num[0][row] |= temp;
                used_num[1][col] |= temp;
                used_num[2][row / 3 * 3 + col / 3] |= temp;
            } else {
                board[row][col] = '.';
                used_block[row][col] = false;
                used_num[0][row] ^= temp;
                used_num[1][col] ^= temp;
                used_num[2][row / 3 * 3 + col / 3] ^= temp;
            }
        }
    
        inline bool check(int row, int col, int num) {
            int temp = 1 << num;
            return !(used_num[0][row] & temp) &&
                   !(used_num[1][col] & temp) &&
                   !(used_num[2][row / 3 * 3 + col / 3] & temp);
        }
    
        void print(vector<vector<char> > &board) {
            cout << endl;
            for (const auto &row : board) {
                for (const char c : row) {
                    cout << c;
                }
                cout << endl;
            }
            cout << endl;
        }
    
        void dfs(vector<vector<char> > &board, int position) {
            if (position == 81) {
                status = true;
    //            print(board);
                return;
            }
            int row = position / 9, col = position % 9;
            if (!used_block[row][col]) {
                for (int num = 0; num < 9; num++) {
                    if (check(row, col, num)) {
                        mark(board, row, col, num, true);
                        dfs(board, position + 1);
                        if (status) { return; }
                        mark(board, row, col, num, false);
                    }
                }
            } else {
                dfs(board, position + 1);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.