Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfyall of the following rules:

1. Each of the digits 1-9must occur exactly once in each row.
2. Each of the digits 1-9must occur exactly once in each column.
3. Each of the the digits 1-9must occur exactly once in each of the 93x3sub-boxes of the grid.

Empty cells are indicated by the character'.'.

Note:

• The given board contain only digits1-9and the character'.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always9x9.

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

    public boolean solveSudoku(char[][] board, int i, int j) {
        if(i == 9)
            return true;
        if(j == 9)
            return solveSudoku(board, i + 1, 0);

        if(board[i][j] != '.')
            return solveSudoku(board, i, j + 1);

        for(char c = '1'; c <= '9'; c++) {
            board[i][j] = c;
            if(isValid(board, i, j)) {
                if(solveSudoku(board, i, j + 1))
                    return true;
            }
            board[i][j] = '.';
        }

        return false;
    }

    public boolean isValid(char[][] board, int i, int j) {
        for(int k = 0; k < 9; k++) {
            if(k != i && board[k][j] == board[i][j])
                return false;
        } 

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

        for(int row = i / 3 * 3; row < i / 3 * 3 + 3; row++) {
            for(int col = j / 3 * 3; col < j / 3 * 3 + 3; col++) {
                if(row != i && col != j && board[row][col] == board[i][j])
                    return false;
            }
        }

        return true;
    }
}