Two very Simple and Neat Java DFS/Backtracking solutions

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

``````private char[][] b;
private boolean[][] row = new boolean[9][9];
private boolean[][] col = new boolean[9][9];
private boolean[][] block = new boolean[9][9];
public void solveSudoku(char[][] board) {
b = 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] = true;
}
}
}
Helper(0);
}
public boolean Helper(int ind){
if(ind==81) return true;
int i=ind/9, j=ind%9, num, k;
if(b[i][j]!='.') return Helper(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] = true;
if(Helper(ind+1)) return true;
b[i][j]='.';
row[i][num] = col[j][num] = block[k][num] = false;
}
}
return false;
}
}
``````

2.The second one check with `board itself`. The code is neat and simple. Running time is about 252-332ms. The time difference between these two version is small. But it's huge in C++ answer.

``````private char[][] b;
public void solveSudoku(char[][] board) {
if(board == null || board.length < 9) return;
b = board;
solve(0);
}
public boolean solve(int ind){
if(ind==81) return true;
int i=ind/9, j=ind%9;
if(b[i][j]!='.') return solve(ind+1);
else{
for(char f = '1'; f <= '9'; f++){
if(isValidFill(i, j, f)){
b[i][j]= f;
if(solve(ind+1)) return true;
b[i][j]='.';
}
}
return false;
}
}
public boolean isValidFill(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;
}
``````

• I like this answer which utilize boolean[][] matrix to check the number, which is better than just loop through the row, column and box each time to check duplicates, why this answer just have 2 votes? It deserves more votes!

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