https://leetcode-cn.com/problems/sudoku-solver/

dfs + 剪枝 + 回溯

• 把限制先预处理好，然后递归的时候把限制带着玩 ```java public static void solveSudoku(char[][] board) { boolean[][] row = new boolean[9][10]; boolean[][] col = new boolean[9][10]; boolean[][] bucket = new boolean[9][10]; initMaps(board, row, col, bucket); process(board, 0, 0, row, col, bucket); }

private static void initMaps(char[][] board, boolean[][] row, boolean[][] col, boolean[][] bucket) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { int bid = (i / 3) * 3 + j / 3; if (board[i][j] != ‘.’) { int num = board[i][j] - ‘0’; row[i][num] = true; col[j][num] = true; bucket[bid][num] = true; } } } }

private static boolean process(char[][] board, int i, int j, boolean[][] row, boolean[][] col, boolean[][] bucket) { if (i == 9) { return true; } int nexti = j != 8 ? i : i + 1; int nextj = j != 8 ? j + 1 : 0; if (board[i][j] != ‘.’) { return process(board, nexti, nextj, row, col, bucket); } else { int bid = (i / 3) * 3 + j / 3; for (int num = 1; num <= 9; num++) { if ((!row[i][num])&& (!col[j][num]) && (!bucket[bid][num])) { row[i][num] = true; col[j][num] = true; bucket[bid][num] = true; board[i][j] = (char) (num - ‘0’); if (process(board, nexti, nextj, row, col, bucket)) { return true; } // 恢复现场 row[i][num] = false; col[j][num] = false; bucket[bid][num] = false; board[i][j] = ‘.’; } } return false; } } ```