# 10ms Java DFS. (start from the block with the least possibilities)

• ``````public class Solution {

private static int[][] d = {{0,0}, {0,1}, {1,2}, {1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}};

private boolean solve(char[][] board, Set<Integer>[][] set) {
//find the element which has least possibilities
int min = 10, min_x = -1, min_y = -1;
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
if (board[i][j]=='.' && set[i][j].size()<min) {
min = set[i][j].size();
min_x = i;
min_y = j;
}
if (min==10)
return true;
// try all possibilities.
Set<Integer> p = set[min_x][min_y];
List<Integer> mx = new ArrayList<Integer>();
List<Integer> my = new ArrayList<Integer>();
for (int number: p) {
//update set and board
mx.clear();my.clear();
for (int i=0; i<9; i++) {
if (i!=min_y && board[min_x][i]=='.' && set[min_x][i].contains(number)) {
set[min_x][i].remove(number);
}
if (i!=min_x && board[i][min_y]=='.' && set[i][min_y].contains(number)) {
set[i][min_y].remove(number);
}
int xx = min_x/3*3+d[i][0], yy = min_y/3*3+d[i][1];
if ((xx!=min_x || yy!=min_y) && board[xx][yy]=='.' && set[xx][yy].contains(number)) {
set[xx][yy].remove(number);
}
}
board[min_x][min_y] = (char) (number+48);
//try next
if (solve(board, set)) return true;
//recover set
for (int i=0; i<mx.size(); i++)
board[min_x][min_y] = '.';
}
return false;
}

public void solveSudoku(char[][] board) {
Set<Integer>[][] set = new Set[9][9];
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
if (board[i][j]=='.'){
set[i][j] = new HashSet<Integer>();
}
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
if (board[i][j]=='.') {
//delete numbers shown in same line
for (int k=0; k<9; k++)
if (board[i][k]!='.')
set[i][j].remove(board[i][k]-48);
//delete numbers shown in same column
for (int k=0; k<9; k++)
if (board[k][j]!='.')
set[i][j].remove(board[k][j]-48);
//delete numbers shown in same box
int ox = i/3*3,
oy = j/3*3;
for (int k=0; k<9; k++)
if (board[ox+d[k][0]][oy+d[k][1]]!='.')
set[i][j].remove(board[ox+d[k][0]][oy+d[k][1]]-48);
}
solve(board, set);
}
}``````

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