LeetCode每日一题，2025-8-31

dfs搜索解数独，重点是如何判断当前这位置的board[x][y]是否可以填数字num

public class T37 {public static void main(String[] args) {char[][] board = new char[][]{{'5', '3', '.', '.', '7', '.', '.', '.', '.'},{'6', '.', '.', '1', '9', '5', '.', '.', '.'},{'.', '9', '8', '.', '.', '.', '.', '6', '.'},{'8', '.', '.', '.', '6', '.', '.', '.', '3'},{'4', '.', '.', '8', '.', '3', '.', '.', '1'},{'7', '.', '.', '.', '2', '.', '.', '.', '6'},{'.', '6', '.', '.', '.', '.', '2', '8', '.'},{'.', '.', '.', '4', '1', '9', '.', '.', '5'},{'.', '.', '.', '.', '8', '.', '.', '7', '9'}};T37 t37 = new T37();t37.solveSudoku(board);// 输出结果for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {System.out.print(board[i][j] + " ");}System.out.println();}}public void solveSudoku(char[][] board) {dfs(board, 0, 0);}// 回溯private boolean dfs(char[][] board, int row, int col) {// 如果列到头，换行if (col == 9) {return dfs(board, row + 1, 0);}// 如果行到头，说明填完了if (row == 9) {return true;}// 如果当前位置不是空格，直接跳过if (board[row][col] != '.') {return dfs(board, row, col + 1);}// 尝试填 1~9for (char c = '1'; c <= '9'; c++) {if (isValid(board, row, col, c)) {board[row][col] = c;if (dfs(board, row, col + 1)) {return true; // 找到答案就立即返回}board[row][col] = '.'; // 回溯}}return false; // 9 个都不行，返回 false}// 判断当前位置填 num 是否有效private boolean isValid(char[][] board, int row, int col, char num) {for (int i = 0; i < 9; i++) {if (board[row][i] == num) return false; // 行if (board[i][col] == num) return false; // 列if (board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == num) return false; // 3x3 宫格}return true;}
}