37. Sudoku Solver

class Solution {
    public void solveSudoku(char[][] board) {
        backTrack(board,0);
    }
    
    // return boolean to 1. reduce time complexity
    // 2.to make backtrack not revert the value in board 
    private boolean backTrack(char[][] board, int i){
        if(i==81) return true;
        
        int row = i/9;
        int col= i%9;
        
        if(board[row][col]!='.') return backTrack(board, i+1);
        
        for(char ch='1'; ch<='9'; ch++){
            if(!isValid(row, col, ch, board)) continue;
            board[row][col]=ch;
            if(backTrack(board, i+1)){
                return true;
            }
            board[row][col]='.';
        }
        return false;
    }
    
    private boolean isValid(int i, int j, char ch, char[][] board){
        //check the 3*3 subbox
        for(int row=i/3*3; row<(i/3+1)*3; row++){
            for(int col=j/3*3; col<(j/3+1)*3; col++){
                if(ch==board[row][col]){
                    return false;
                }
            }
        }
        
        //check the row
        for(int col=0; col<board[0].length; col++){
            if(ch==board[i][col]) return false;
        }
        
        //check the column
        for(int row=0; row<board.length; row++){
            if(ch==board[row][j]) return false;
        }
        return true;
    }
}