PRODIGY_SD_04.java

public class PRODIGY_SD_04 {
        public static void main(String[] args) {
            // Sudoku puzzle (0 represents empty cells)
            char[][] sudokuBoard = {
                {'5', '3', '0', '0', '7', '0', '0', '0', '0'},
                {'6', '0', '0', '1', '9', '5', '0', '0', '0'},
                {'0', '9', '8', '0', '0', '0', '0', '6', '0'},
                {'8', '0', '0', '0', '6', '0', '0', '0', '3'},
                {'4', '0', '0', '8', '0', '3', '0', '0', '1'},
                {'7', '0', '0', '0', '2', '0', '0', '0', '6'},
                {'0', '6', '0', '0', '0', '0', '2', '8', '0'},
                {'0', '0', '0', '4', '1', '9', '0', '0', '5'},
                {'0', '0', '0', '0', '8', '0', '0', '7', '9'}
            };
    
            PRODIGY_SD_04 solver = new PRODIGY_SD_04();
            solver.solveSudoku(sudokuBoard);

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(sudokuBoard[i][j] + " ");
                }
                System.out.println();
            }
        }
    
    public boolean isSafe(char[][] board, int row, int col, int number){
        for(int i=0; i<board.length; i++){
            if(board[i][col] == (char)(number + '0')){
                return false;
            }
            if(board[row][i] == (char)(number + '0')){
                return false;
            }
        }

        //grid
        int sr = row/3 * 3;
        int sc = col/3 * 3;
        for(int i = sr; i<sr+3; i++){
            for(int j = sc; j<sc+3; j++){
                if(board[i][j] == (char)(number + '0')){
                    return false;
                }
            }
        }
        return true;
    }


    public boolean helper(char[][] board, int row, int col){
        if(row == board.length)
        {
            return true;
        }
        int nrow=0;
        int ncol =0;
        if(col != board.length -1)
        {
            nrow = row;
            ncol = col+1;
        }
        else{
            nrow = row+1;
            ncol =0;
        }

        if( board[row][col] != '0'){
            if(helper(board, nrow, ncol)){
                return true;
            }
        }
        else{
            for(int i=1; i<=9; i++)
            {
                if(isSafe(board, row, col, i)){
                    board[row][col] = (char)(i+'0');
                    if(helper(board, nrow, ncol))
                    {
                        return true;
                    }
                    else{
                        board[row][col] = '0';
                    }
                }
            }
        }
        return false;
    }


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

}