Getting time limit exceeded


  • 0
    I

    Here is my code:

    void solveSudoku(vector<vector<char> > &b) {
       solve(b,0);
    }
    
    bool solve(vector<vector<char> > &b, int in){
        
        if(in==81)return true;
        
        int r = in / 9;
        int c = in % 9;
        if(b[r][c] != '.')
            return solve(b,in+1);
            
        for(int i=1; i <=9 ; i++){
            b[r][c] = (char)('0'+i);
            if(valid(b,r,c)){
                if(solve(b,in+1))return true;
            }
            b[r][c]='.';
        }
        return false;
    }
    
    bool valid(vector<vector<char> > b, int r, int c){
        //check row
        int flag[10]={0};
        for(int i=0;i<9;i++){
            if(b[r][i] == '.')continue;
            int t = (int)b[r][i] - 48;
            if(flag[t]==1)
                return false;
            flag[t]=1;
        }
        
        memset(flag,0,sizeof(flag));
        for(int i=0;i<9;i++){
            if(b[i][c] == '.')continue;
            int t = (int)b[i][c] - 48;
            if(flag[t]==1)
                return false;
            flag[t]=1;
        }
        
        int j = (c/3) * 3;
        int i = (r/3) * 3;
        memset(flag,0,sizeof(flag));
        for(int k = 0; k < 3; k++){
           for(int m = 0; m < 3; m++){
             char elem = b[i+k][j+m];
             if(elem != '.'){
               int t = (int)elem - 48;
                if(flag[t]==1)
                    return false;
                flag[t]=1;  
             }                       
           }
        }
        return true;
    }
    

    I am using the backtracking approach and after placing a digit for a cell, I am checking the validity of only that column, only that row and only that grid.

    I don't know where I am getting the tle
    Please help


  • 1
    S

    It seems fine. You can try to pass reference for the first parameter of valid, like
    bool valid(vector<vector<char> >& b, int r, int c)


  • 0
    G

    Mine is almost the same as yours. maybe you could just bypass the none '.' function call solve(b,in+1). Therefore the function call overhead could be reduced, even though i don't think it's the cause of TLE.

    bool isValidSudoku(vector<vector<char> > &board) {
        // row
        for(int i = 0; i < 9; i++){
            int tmp = 0;
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.') continue;
                if(tmp & (1 << board[i][j] - '0')) return false;
                else tmp |= (1 << board[i][j] - '0');
            }
        }
        // col
        for(int i = 0; i < 9; i++){
            int tmp = 0;
            for(int j = 0; j < 9; j++){
                if(board[j][i] == '.') continue;
                if(tmp & (1 << board[j][i] - '0')) return false;
                else tmp |= (1 << board[j][i] - '0');
            }
        }
        // blk
        for(int i = 0; i < 9; i++){
            int tmp = 0;
            for(int j = 0; j < 9; j++){
                int x = 3 * (i / 3) + j / 3, y = 3 * (i % 3) + j % 3;
                if(board[x][y] == '.') continue;
                if(tmp & (1 << board[x][y] - '0')) return false;
                else tmp |= (1 << board[x][y] - '0');
            }
        }
        return true;
    }
    bool solver(vector<vector<char> > &board){
        bool done = true;
        int x, y;
        for(int i = 0; i < 81; i++){
            if(board[i / 9][i % 9] == '.'){
                done = false;
                x = i / 9;
                y = i % 9;
                break;
            }
        }
        if(done) return true;
        
        for(int i = 1; i <= 9; i++){
            board[x][y] = '0' + i;
            if(isValidSudoku(board) && solver(board)) return true;
        }
        board[x][y] = '.';
        return false;
    }
    void solveSudoku(vector<vector<char> > &board) {
        solver(board);
    }

  • 0
    B
    This post is deleted!

  • 0
    L

    HI, how do you fix it out that, when you check the blk, you use 3*(i/3)+(j/3) and 3*(i%3)+(j%3)?
    can you tell me how you get this?


Log in to reply
 

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