Sudoku.java

    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.");  
    }  
    }  
    }