# Two very Simple and Neat C++ DFS/Backtracking solutions

• 1.The first one uses three `2D-array` to check valid. Running time is about 4-8ms.

``````bool row[9][9]={}, col[9][9]={}, block[9][9]={};
void solveSudoku(vector<vector<char>>& board) {
int num, k;
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if(board[i][j]!='.') {
num = board[i][j]-'1';
k = i/3*3 + j/3;
row[i][num] = col[j][num] = block[k][num] = 1;
}
}
}
Helper(board, 0);
}
bool Helper(vector<vector<char>>& b, int ind){
if(ind==81) return true;
int i=ind/9, j=ind%9, num, k;
if(b[i][j]!='.') return Helper(b, ind+1);
else{
for(char f='1'; f<='9'; f++){
num = f-'1';
k= i/3*3 + j/3;
if(!row[i][num] && !col[j][num] && !block[k][num]){
b[i][j]= f;
row[i][num] = col[j][num] = block[k][num] = 1;
if(Helper(b, ind+1)) return true;
b[i][j]='.';
row[i][num] = col[j][num] = block[k][num] = 0;
}
}
return false;
}
}
``````

2.The second one check with `board itself`. The code is neat and simple, but it runs so slow. Running time is about 52ms. Copy my own code from here. And there is the Java version.

``````void solveSudoku(vector<vector<char>>& board) {
helper(board, 0);
}
bool helper(vector<vector<char>>& b, int ind){
if(ind==81) return true;
int i=ind/9, j=ind%9;
if(b[i][j]!='.') return helper(b, ind+1);
else{
for(char f = '1'; f <= '9'; f++){
if(isValidFill(b, i, j, f)){
b[i][j]= f;
if(helper(b, ind+1)) return true;
b[i][j]='.';
}
}
return false;
}
}
bool isValidFill(vector<vector<char>>& b, int i, int j, char fill) {
for(int k=0; k<9; k++){
int r= i/3*3+j/3;   //select the block
if(b[i][k]==fill || b[k][j]==fill || b[r/3*3+k/3][r%3*3+k%3]==fill)
return false; //check row, column, block
}
return true;
}
``````

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