# TLE in one input

• 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;
}
};``````

• 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.

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