public class SudokuPuzzle  {  
public boolean isSafe(int[][] b, int r, int c, int n)  {  
// the loop takes care of the clash in the row of the grid  
for (int d = 0; d < b.length; d++)  {  
// if the number that we have inserted is already   
// present in that row then return false  
    if (b[r][d] == n)   {  
return false;  
        }  
    }  
  
// the loop takes care of the clash in the column of the grid  
    for (int r1 = 0; r1 < b.length; r1++)  {  
  
// if the number that we have inserted is already   
// present in that column then return false  
        if (b[r1][c] == n)  {  
            return false;  
        }  
    }  
  
// the loop takes care of the clash in the sub-grid that is present in the grid  
    int sqt = (int)Math.sqrt(b.length);  
    int boxRowSt = r - r % sqt;  
    int boxColSt = c - c % sqt;  
  
    for (int r1 = boxRowSt; r1 < boxRowSt + sqt; r1++)  {  
        for (int d = boxColSt; d < boxColSt + sqt; d++)  {  
// if the number that we have inserted is already   
// present in that sub-grid then return false  
            if (b[r1][d] == n)  {  
                return false;  
            }  
        }  
    }  
  
// if there is no clash in the grid, then it is safe and   
// true is returned  
    return true;  
}  
  
public boolean solveSudoku(int[][] b, int num)  {  
    int r = -1;  
    int c = -1;  
    boolean isVacant = true;  
    for (int i = 0; i < num; i++)  {  
        for (int j = 0; j < num; j++)  {  
            if (b[i][j] == 0)  {  
                r = i;  
                c = j;  
// false value means   
// there is still some   
// vacant cells in the grid  
                isVacant = false;  
                break;  
            }  
        }  
    if (!isVacant)   {  
        break;  
        }  
    }  
  
// there is no empty space left  
// in the grid  
    if (isVacant)  {  
        return true;  
    }  
  
// otherwise for each row do the backtracking  
    for (int no = 1; no <= num; no++)  {  
        if (isSafe(b, r, c, no))  {  
            b[r][c] = no;  
            if (solveSudoku(b, num))  {  
// display(board, num);  
                return true;  
            }  
            else  {  
                b[r][c] = 0;  
            }  
        }  
    }  
    return false;  
}  
  
public void display(int[][] b, int n)  {  
// We have got the solution, just display it  
for (int i = 0; i < n; i++)  {  
    for (int d = 0; d < n; d++)  {  
        System.out.print(b[i][d]);  
        System.out.print(" ");  
        }  
        System.out.print("\n");  
        if ((i + 1) % (int)Math.sqrt(n) == 0)  {  
            System.out.print("");  
            }  
        }  
    }  

// main method  
public static void main(String argvs[])  {  
  
// the 9 x 9  grid   
int[][] b = new int[][] { { 7, 0, 0, 0, 0, 0, 2, 0, 0 },   
                        { 4, 0, 2, 0, 0, 0, 0, 0, 3 },   
                        { 0, 0, 0, 2, 0, 1, 0, 0, 0 },   
                        { 3, 0, 0, 1, 8, 0, 0, 9, 7 },   
                        { 0, 0, 9, 0, 7, 0, 6, 0, 0 },   
                        { 6, 5, 0, 0, 3, 2, 0, 0, 1 },   
                        { 0, 0, 0, 4, 0, 9, 0, 0, 0 },   
                        { 5, 0, 0, 0, 0, 0, 1, 0, 6 },   
                        { 0, 0, 6, 0, 0, 0, 0, 0, 8 }   
                        } ;  
  
// creating an object of the class SudokuPuzzle  
SudokuPuzzle obj = new SudokuPuzzle();  
  
// computing the size of the grid  
int size = b.length;  
  
System.out.println("The grid is: ");  
for(int i = 0; i < size; i++)  {  
    for(int j = 0; j < size; j++)  {  
        System.out.print(b[i][j] + " ");    
        }  
    System.out.println();  
    }  
    System.out.println();  
    if (obj.solveSudoku(b, size))  {  
// display solution  
        System.out.println("The solution of the grid is: ");  
        obj.display(b, size);  
    }  
    else   {  
        System.out.println("There is no solution available.");  
        }
    }
}