public class Main4 {
public static boolean SudokuSolver(int[][] sudoku,int row, int col ){
if(row==9) return true;
int nextRow=row,nextCol=col+1;
if(col+1==9){
nextRow=row+1;
nextCol=0;
}
if(sudoku[row][col]!=0) return SudokuSolver(sudoku,nextRow,nextCol);
for(int digit=1;digit<10;digit++){
if(isSafe(sudoku,row,col,digit)){
sudoku[row][col]=digit;
if(SudokuSolver(sudoku,nextRow,nextCol)) return true;
sudoku[row][col]=0;
}
}
return false;
}
public static boolean isSafe(int [][] sudoku,int row, int col, int digit){
for (int i = 0; i < 9; i++) {
if(sudoku[i][col]==digit) return false;
}
for(int j=0;j<9;j++){
if(sudoku[row][j]== digit) return false;
}
int sr=(row/3)*3, sc=(col/3)*3;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(sudoku[sr+i][sc+j]==digit) return false;
}
}
return true;
}
public static void main(String[] args){
int sudoku[][]={
{ 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 }
};
if(SudokuSolver(sudoku,0,0)){
System.out.println("Solution exists");
for (int i = 0; i < 9; i++) {
for (int j=0;j<9;j++){
System.out.print(sudoku[i][j]+" ");
}
System.out.println();
}
}
}
}