Get TLE in sudoku solver problem


  • 1
    N

    l thought the code blew is fine, but lt get tle problem,could someone help me out? thanks

       void solveSudoku(vector<vector<char> > &board){
        solve(board);
    }
    bool solve(vector<vector<char> > &board) {
        int rsize=board.size();
        if(rsize<=0)    return false;
        int csize=board[0].size();
        for(int i=0;i<rsize;i++){
            for(int j=0;j<csize;j++){
                if(board[i][j]!='.'){
                    continue;
                }
                for(int k=1;k<=9;k++){
                    board[i][j] = (char)('0'+k);
                    if(isValid(board,i,j) && solve(board)){
                        return true;
                    }
                    board[i][j]='.';
                }
                return false;
            }
        }
        return true;
    }
    
    bool isValid(vector<vector<char> > &board,int a,int b){
        unordered_set<char> uset;
        for(int i=0;i<9;i++){
            if(board[a][i]=='.')    continue;
            if(uset.find(board[a][i])!=uset.end())  return false;
            else uset.insert(board[a][i]);
        }
        uset.clear();
        for(int i=0;i<9;i++){
            if(board[i][b]=='.')    continue;
            if(uset.find(board[i][b])!=uset.end())  return false;
            else uset.insert(board[i][b]);
        }
        uset.clear();
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                int x=a/3*3+i; 
                int y=b/3*3+j;
                 if(board[x][y]=='.')    continue;
                if(uset.find(board[x][y])!=uset.end())  return false;
                else uset.insert(board[x][y]);
            }
        }
        return true;
    }

Log in to reply
 

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