# Getting time limit exceeded

• 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

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

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

• This post is deleted!

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

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