# Same algorithm implemented in two ways. One is AC, the other is TLE(but runs well on my own computer). WHY???

• I implement one algorithm(DFS) in two ways.
1:

``````class Solution {
public:
bool isValid(const vector<vector<char> > &board, int i, int j) {
unordered_set<char> hs;
for(int k = 0; k < 9; ++k) {
char t = board[i][k];
if(t == '.')
continue;
if(hs.find(t) != hs.end()) {
return false;
} else {
hs.insert(t);
}
}
hs.clear();
for(int k = 0; k < 9; ++k) {
char t = board[k][j];
if(t == '.')
continue;
if(hs.find(t) != hs.end()) {
return false;
} else {
hs.insert(t);
}
}
hs.clear();
int m = i / 3 * 3;
int n = j / 3 * 3;
for(int mm = m; mm < m + 3; ++mm) {
for(int nn = n; nn < n + 3; ++nn) {
char t = board[mm][nn];
if(t == '.')
continue;
if(hs.find(t) != hs.end()) {
return false;
} else {
hs.insert(t);
}
}
}
return true;
}

bool helper(vector<vector<char> > &board, int m, int n) {
int i = m, j = n;
bool isPoint = false;
//find the next '.' location from m, n in the order of
//               m,n------------------>end
//start------------------------------->end
//start------------------------------->end
for(; i < board.size(); ++i) {
for(; j < board[0].size(); ++j) {
if(board[i][j] == '.') {
isPoint = true;
break;
}
}
if(isPoint)
break;
j = 0;
}
if(i == board.size())//completed
return true;
for(int k = 1; k < 10; ++k) {//try 1~9 in i, j
board[i][j] = k + '0';
if(isValid(board, i, j)) {
if(helper(board, i, j))
return true;
}
board[i][j] = '.';
}
return false;
}

void solveSudoku(vector<vector<char> > &board) {
helper(board, 0, 0);
}
};
``````

This is TLE implementation:
Last executed input: [".....7..9",".4..812..","...9...1.","..53...72","293....5.",".....53..","8...23...","7...5..4.","531.7...."]

I ran this sample using this period of code in my own computer and I got the correct result.

/This implementation is Accepted***/

``````class Solution {
public:
bool isValid(vector<vector<char> > &board, int r, int c, char v) {
for(int j = 0; j < 9; ++j) {
if(j != c && board[r][j] == v)
return false;
}
for(int i = 0; i < 9; ++i) {
if(i != r && board[i][c] == v)
return false;
}
for(int i = 3 * (r / 3); i < 3 * (r / 3) + 3; ++i) {
for(int j = 3 * (c / 3); j < 3 * (c / 3) + 3; ++j) {
if((i != r || j != c) && v == board[i][j])
return false;
}
}
return true;
}

bool solveSudokuHelper(vector<vector<char> > &board) {
for(int i = 0; i < 9; ++i) {
for(int j = 0; j < 9; ++j) {
if(board[i][j] == '.') {
for(int k = 0; k < 9; ++k) {
if(isValid(board, i, j, '1' + k)) {
board[i][j] = '1' + k;
if(solveSudokuHelper(board))
return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}

void solveSudoku(vector<vector<char> > &board) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
solveSudokuHelper(board);
}
};
``````

I think both implementations use the same algorithm. Why does the latter one works while the first one does not??

• I had the same issue with you. I tried to change the isValid function and finally it worked out. I think it's because the operations on unordered_set is slower than validating the board using for loop directly.

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