My 7ms C++ Solution Using Bit Operation,Even Faster Than Some C Solution.


  • 0
    G
    class Solution {
    private:
        bool flag;
        int col[9],row[9],blo[9],val[10],num[9][9];
    public:
        int findBlock(int x,int y) {
            x=(x>5) ? 3 : (x>2) ? 2 : 1;
            y=(y>5) ? 3 : (y>2) ? 2 : 1;
            return (x-1)*3+y-1;
        }
        void setTables(vector<vector<char>>& b) {
            for (int i=1;i<10;i++) val[i]=1<<i;
            col[9]={0},row[9]={0},blo[9]={0};
            for (int i=0;i<9;i++)
                for (int j=0;j<9;j++) {
                    num[i][j]=findBlock(i,j);
                    if (b[i][j]!='.') {
                        col[j]|=val[b[i][j]-'0'];
                        row[i]|=val[b[i][j]-'0'];
                        blo[num[i][j]]|=val[b[i][j]-'0'];
                    }
                }
        }
        void backTrack(int r,int c,vector<vector<char>>& b) {
            if (r==9) {
                flag=true;
                return;
            }
            int nextC=(c==8) ? 0 :c+1,nextR=(nextC==0) ? r+1 : r;
            if (b[r][c]!='.')
                backTrack(nextR,nextC,b);
            else {
                for (int i=1;i<10;i++)
                    if (!(col[c]&val[i]) && !(row[r]&val[i]) && !(blo[num[r][c]]&val[i])) {
                        b[r][c]=i+'0';
                        col[c]|=val[i];
                        row[r]|=val[i];
                        blo[num[r][c]]|=val[i];
                        if (nextR==9) {
                            flag=true;
                            return;
                        }
                        backTrack(nextR,nextC,b);
                        if (flag) return;
                        b[r][c]='.';
                        col[c]&=~val[i];
                        row[r]&=~val[i];
                        blo[num[r][c]]&=~val[i];
                    }
            }
        }
        void solveSudoku(vector<vector<char>>& board) {
            setTables(board);
            flag=false;
            backTrack(0,0,board);
        }
    };

  • 0

    my friends ask me why I cry in front of my computer LOL


Log in to reply
 

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