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

    // 从左至右，从上往下进行遍历递归
    private boolean helper(char[][] board, int i, int j) {
        if(j >= 9) {
            return helper(board, i+1, 0);
        }
        if(i == 9) {
            return true;
        }
        if(board[i][j] == '.') {
            for(int k=1; k<=9; k++) {
                board[i][j] = (char)(k + '0');
                if(isValid(board, i, j)) {
                    if(helper(board, i, j+1)) {  // 递归到下一格
                        return true;
                    }
                }
                board[i][j] = '.';
            }
        } else {
            return helper(board, i, j+1);
        }
        return false;
    }

    private boolean isValid(char[][] board, int i, int j) {
        // 对行进行valid
        for(int k=0; k<9; k++) {
            if(board[i][k] != '.' && k!=j && board[i][k]==board[i][j]) {
                return false;
            }
        }
        // 对列进行valid
        for(int k=0; k<9; k++) {
            if(board[k][j] != '.' && k!=i && board[k][j]==board[i][j]) {
                return false;
            }
        }
        // 对每个九宫格进行valid
        for(int m=0; m<3; m++) {
            for(int n=0; n<3; n++) {
                int x=i/3*3+m;
                int y=j/3*3+n;
                if((x!=i || y!=j) && board[x][y]==board[i][j]) { // 注意判断条件
                    return false;
                }
            }
        }
        return true;
    }
}