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~9
        for (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;
    }
}