# Very Readable DFS Java Solution

• DFS with back trace, use a global var boolean found to end the recursion.

``````public class Solution {
boolean found;
public void solveSudoku(char[][] board) {
found = false;
dfs(board, 0, 0);
}

private void dfs(char[][] board, int x, int y){
// position correction
if(x==9){
x = 0;
y = y + 1;
}

// base case
if(y==9) {found = true;return;}

// recursion
if(board[x][y]!='.'){
dfs(board, x+1, y);
}else{
List<Integer> list = validNum(board, x, y);
for(int i = 0;i < list.size();i++){
board[x][y] = (char)('0' + list.get(i));
dfs(board, x+1, y);
if(found) return;
board[x][y] = '.';
}
}
}

private List<Integer> validNum(char[][] board, int x, int y){
List<Integer> list = new ArrayList<Integer>();
int center_x = x/3 * 3 + 1;
int center_y = y/3 * 3 + 1;
boolean[] engaged = new boolean[9];
for(int i = -1;i <= 1;i++)
for(int j = -1;j <= 1;j++)
if(board[center_x+i][center_y+j]!='.')
engaged[(int)(board[center_x+i][center_y+j]-'1')] = true;
for(int i = 0;i < 9;i++)
if(board[i][y]!='.') engaged[(int)(board[i][y] - '1')] = true;
for(int j = 0;j < 9;j++)
if(board[x][j]!='.') engaged[(int)(board[x][j] - '1')] = true;
for(int i = 0;i < engaged.length;i++)