[leetcode]Sudoku Solver

这题的思路是
用recursion, 遇到非'.'跳过，遇到'.' 就从 ‘1’ 到'9' 每个数字做一次DFS
需要一个helper function来检验当前sukdoku是否有效

public class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board, 0, 0);
    }

    public boolean solveSudokuHelper(char[][] board, int startI, int startJ){
        if (startI == board.length){
            return true;
        }
        if (startJ == board[0].length){
            return solveSudokuHelper(board, startI+1, 0);
        }
        if (board[startI][startJ] != '.'){
            return solveSudokuHelper(board, startI, startJ+1);
        }  
        for (char temp = '1'; temp <= '9'; temp++){
            board[startI][startJ] = temp;
            if (isValidSudoku(board, startI, startJ) && solveSudokuHelper(board, startI, startJ+1)){
                return true;
            }
        }
        board[startI][startJ] = '.';
        return false;
    }

    public boolean isValidSudoku(char[][] board, int i, int j) {
        for (int checkRow = 0; checkRow < board[0].length; checkRow++){
            if (checkRow != j && board[i][checkRow] == board[i][j]){
                return false;
            }
        }

        for (int checkColumn = 0; checkColumn < board.length; checkColumn++){
            if (checkColumn != i && board[checkColumn][j] == board[i][j]){
                return false;
            }
        }

        int boxRow = (i/3)*3;
        int boxColumn = (j/3)*3;
        for (int k = boxRow; k < boxRow+3; k++){
            for (int q = boxColumn; q < boxColumn+3; q++){
                if (k != i && q != j && board[k][q] == board[i][j]){
                    return false;
                }
            }
        }

        return true;
    }
}