Problem on judging if it is valid to place number N in board[x][y] position


  • 0
    S

    Hi, all
    Can someone help to take a look at my current code?
    I met some problem in judging if it is OK to place number N at board[x][y] position.

    //board[x][y]='.'
    If I use the bitmap method,
    if((row[x]&(0x01<<i)==0) && (column[y]&(0x01<<i)==0) && (blk[x/3+(y/3)*3]&(0x01<<i)==0)){
    I got wrong answer, seems that no right answer can be found
    However, if I use the normal method
    if(isValid(x,y,i,board)){
    I got ACCEPTED...

    Thanks if you can help a little bit.

    class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            // back tracking
            // when found a proper 
            int row[9]={0}, column[9]={0}, blk[9]={0}; //(row[i] & (0x01<<n))==0 indicates row [i] doesn't have number n yet
            vector<vector<char>> res;
            memset(row,0,sizeof(row));
            memset(column,0,sizeof(column));
            memset(blk,0,sizeof(blk));
            
            
            //find all pre-filled items, and record their location
            for(int x=0;x<9;++x){
                for(int y=0;y<9;++y){
                    if(board[x][y]!='.') {
                        int n=board[x][y]-'0';
                        row[x]+=(0x01<<n);
                        column[y]+=(0x01<<n);
                        blk[x/3+(y/3)*3]+=(0x01<<n);
                    }
                }
            }
            
            helper(board,0,0,row,column,blk,res);
            if(res.size()!=0)
                board=res;
            
            return;
        }
        void helper(vector<vector<char>>& board, int x, int y, int* row, int* column, int*blk, vector<vector<char>>& finalRes){
    
            if(y==9) {//y beyond the boundary
                helper(board,x+1,0,row,column,blk,finalRes);
                return;
            }
            
            if(x==9&&y==0) {    //alraedy got an answer
                finalRes=board;
                return;
            }
            
            if(board[x][y]!='.'){
                
                helper(board,x,y+1,row,column,blk,finalRes);
                return;
            }
            
            //board[x][y]='.'
            for(int i=1; i<=9;++i){
                if((row[x]&(0x01<<i)==0) && (column[y]&(0x01<<i)==0) && (blk[x/3+(y/3)*3]&(0x01<<i)==0)){
                //if(isValid(x,y,i,board)){
                    row[x]+=(0x01<<i);
                    column[y]+=(0x01<<i);
                    blk[x/3+(y/3)*3]+=(0x01<<i);
                    board[x][y]='0'+i;
                    
                    helper(board,x,y+1,row,column,blk,finalRes);
                    if(finalRes.size()==board.size()) return;   //return in advance
                    
                    board[x][y]='.';
                    row[x]-=(0x01<<i);
                    column[y]-=(0x01<<i);
                    blk[x/3+(y/3)*3]-=(0x01<<i);
                    
                }
            }
            
            return;
            
        }
        
        bool isValid(int x, int y, int n, vector<vector<char> >&board ){
            for(int i=0;i<9;++i){
                if(board[i][y]==('0'+n)) return false;
                if(board[x][i]==('0'+n)) return false;
            }
            int a=x/3, b=y/3;
            for(int i=0; i<3;++i){
                for(int j=0; j<3; ++j){
                    if(board[3*a+i][3*b+j]==('0'+n)) return false;  // remember x3!!!!fxxxkkk
                }
            }
            
            return true;
            
        }
    };

  • 0
    I

    Beware the precedence of & in the C and C++ languages. This if-statement won't print anything:

    if ( 2 & 2 == 2 ) {
        printf("true\n");
    }
    

    But this one will:

    if ( (2 & 2) == 2 ) {
        printf("true\n");
    }
    

    That's because the compiler sees the first if-statement as:

     if ( 2 & (2 == 2) ) { 
        printf("true\n");
    }
    

  • 0
    S

    Hi, thanks for your reply


Log in to reply
 

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