TLE in one input

Question

Hi,

I use back approach in this question, and when deciding whether a number is valid, I only check if this number exist in the current row, current column or current "cube", but it still got TLE in this input....

Last executed input: ["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]

    class Solution {
public:
    bool solve(int i,int j,vector<vector<char> > &board,vector<vector<bool> >& each_row,vector<vector<bool> >& each_column,vector<vector<bool> >& each_cube){

        if(9==i && 0==j)
            return true;

        int next_j=(j+1)%9;
        int next_i=i+(j+1)/9;

        if(board[i][i]!='.')
            return solve(next_i,next_j,board,each_row,each_column,each_cube);

        //try to fill
        for(int n=1;n<10;n++){
            if(each_row[i][n]==true && each_column[j][n]==true && each_row[(i/3)*3+j/3][n]==true){
                each_row[i][n]=false;
                each_column[j][n]=false;
                each_row[(i/3)*3+j/3][n]=false;

                board[i][j]=n+'0';
                if(solve(next_i,next_j,board,each_row,each_column,each_cube))
                    return true;


                each_row[i][n]=true;
                each_column[j][n]=true;
                each_row[(i/3)*3+j/3][n]=true;
            }

        }

        board[i][j]='.';
        return false;
    }

    void solveSudoku(vector<vector<char> > &board) {
        vector<vector<bool> > each_row(9);
        for(int i=0;i<9;i++)
            each_row[i].assign(10,true);

        vector<vector<bool> > each_column=each_row;
        vector<vector<bool> > each_cube=each_row;

        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][i]!='.'){
                    int n=board[i][i]-'0';  
                    each_row[i][n]=false;
                    each_column[j][n]=false;
                    each_cube[(i/3)*3+j/3][n]=false;}
            }
        }

        solve(0,0,board,each_row,each_column,each_cube);

        return;
    }
};

Answer 1

There are so many typo in your code, like if(board[i][i]!='.') each_row[(i/3)*3+j/3][n]=true; etc . I believe these are the reason to TLE.

I think you might use copy-paste to implement your algorithm, it is not a good habit.

However, for these problem, you can use 1d integer array instead of 2d bool array to do the valid check, each bit of integer can be 0 or 1, just like boolean. Integer has 31 bit, so 9 bits is enough for 1-9.