// @Title: 解数独 (Sudoku Solver)
// @Author: qisiii
// @Date: 2024-09-21 18:56:14
// @Runtime: 6 ms
// @Memory: 40 MB
// @comment: 
// @flag: 
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board, board.length, 0,0);
    }

    private boolean dfs(char[][] board, int n, int row, int column) {
        for (int i = row; i < n; i++) {
            for (int j = i==row?column:0; j < n; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                for (int k = 1; k <= 9; k++) {
                    char c = (char) (k + '0');
                    if (isValid(i, j, n, c, board)) {
                        board[i][j] = c;
                        if (dfs(board, n, i,j)) {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    private boolean isValid(int row, int column, int n, char val, char[][] board) {
        // 检查行
        for (int i = 0; i < n; i++) {
            if (val == board[row][i] ) {
                return false;
            }
        }
        // 检查列
        for (int i = 0; i < n; i++) {
            if (val == board[i][column]) {
                return false;
            }
        }
        // 九宫格
        for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
            for (int j = column / 3 * 3; j < column / 3 * 3 + 3; j++) {
                if (val == board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}