# My easily understood solution using simple DFS and pre-process

• Note: The tricky part of this problem is the pre-process part not the DFS part

``````public class Solution {
public void solveSudoku(char[][] board) {
if (board == null || board.length != 9 || board[0].length != 9) {
return;
}

Map<Integer, Set<Character>> map = preProcess(board);

dfs(board, 0, map);
}

private boolean dfs(char[][] board, int steps, Map<Integer, Set<Character>> map) {
if (steps == 81) {
return true;   // finish traversing, we have got the correct answer
}

int rowIdx = steps / 9;
int colIdx = steps % 9;

if (board[rowIdx][colIdx] != '.') {
return dfs(board, steps + 1, map);   // search in one step further
}

Set<Character> allPossibleNums = map.get(getKey(rowIdx, colIdx));
for (char number : allPossibleNums) {
if (isValid(board, rowIdx, colIdx, number)) {
board[rowIdx][colIdx] = number;
if (dfs(board, steps + 1, map)) {
return true;
} else {
board[rowIdx][colIdx] = '.';   // reset this slot for other tries
}
}
}

return false;
}

/**
* to check if it is valid to set this slot to be this number
* @param board
* @param rowIdx - the row index of this slot
* @param colIdx - the column index of this slot
* @param number - the checked number
* @return
*/
private boolean isValid(char[][] board, int rowIdx, int colIdx, char number) {
// check the same row
for (int i = 0; i < 9; i++) {
if (board[rowIdx][i] == number) {
return false;
}
}

// check the same column
for (int i = 0; i < 9; i++) {
if (board[i][colIdx] == number) {
return false;
}
}

// check the same block
int startRowIdx = rowIdx / 3 * 3;
int startColIdx = colIdx / 3 * 3;
int endRowIdx = startRowIdx + 3;
int endColIdx = startColIdx + 3;

for (int i = startRowIdx; i < endRowIdx; i++) {
for (int j = startColIdx; j < endColIdx; j++) {
if (board[i][j] == number) {
return false;
}
}
}

return true;
}

/**
* return a map to record what numbers can be set for a specific slot at row i column j
* @param board
* @return
*/
private Map<Integer, Set<Character>> preProcess(char[][] board) {
List<Set<Character>> rowSet = new ArrayList<>(9); // store all pre-filled numbers for each row
List<Set<Character>> colSet = new ArrayList<>(9); // store all pre-filled numbers for each column
List<Set<Character>> blockSet = new ArrayList<>(9); // store all pre-filled numbers for each block

// initialize row set
for (int row = 0; row < 9; row++) {
Set<Character> set = new HashSet<>();
for (char c : board[row]) {
if (c != '.') {
}
}
}

// initialize column set
for (int col = 0; col < 9; col++) {
Set<Character> set = new HashSet<>();
for (int row = 0; row < 9; row++) {
if (board[row][col] != '.') {
}
}
}

// initialize block set
for (int block = 0; block < 9; block++) {
int startRowIdx = block / 3 * 3;
int endRowIdx = startRowIdx + 3;
int startColIdx = block % 3 * 3;
int endColIdx = startColIdx + 3;
Set<Character> set = new HashSet<>();

for (int row = startRowIdx; row < endRowIdx; row++) {
for (int col = startColIdx; col < endColIdx; col++) {
if (board[row][col] != '.') {
}
}
}
}

Map<Integer, Set<Character>> map = new HashMap<>();
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (!rowSet.get(row).contains(c)
&& !colSet.get(col).contains(c)
&& !blockSet.get(getBlockIdx(row, col)).contains(c)) {
int key = getKey(row, col);
Set<Character> s = map.get(key);
if (s == null) {
s = new HashSet<>();
map.put(key, s);
} else {
}
}
}
}
}
}

return Collections.unmodifiableMap(map);
}

private int getBlockIdx(int row, int col) {
return (row / 3) * 3 + col / 3;
}

private int getKey(int row, int col) {
return row + 33 * col;
}
}``````

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