30 lines, 4ms bit-manipulation backtracking solution


  • 1
    class Solution {
    int check[3][9] = {{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}};
    public:
        void solveSudoku(vector<vector<char> >& board) {
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++) 
                    if (board[i][j] != '.')
                        fill(i, j, 1<<(board[i][j]-'0'-1));
            isValid(0,board);
        }
        bool isValid(int n,vector<vector<char> >& board){
            if (n > 80) return true;
            int i = n/9, j = n%9, rem = check[0][i]|check[1][j]|check[2][i/3*3+j/3];
            if (board[i][j] != '.') return isValid(n+1,board);
            for (int k = 1; k <= 9; k++) {
                if ((rem&(1<<(k-1))) != 0) continue;
                board[i][j] = '0'+k;
                fill(i, j, 1 << (k-1));
                if(isValid(n+1,board)) return true;
                fill(i, j, 1 << (k-1));
            }
            board[i][j] = '.';
            return false;
        }
        void fill(int i, int j, int offset) {
            check[0][i] ^= offset;
            check[1][j] ^= offset;
            check[2][i/3*3+j/3] ^= offset;
        }
    };

Log in to reply
 

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