Sudoku Solver in Java

In this article, we will be looking at an algorithm of Sudoku Solver that can solve the sudoku using Java program.

Since Sudoku is a very popular game often found in the daily newspaper or online games, we will be looking at solving even the toughest Sudoku grid. For those who are new to this game, I would like you to learn the rules of the game first. Moving on to the topic of solving the Sudoku challenge.

Sudoku Solver

We will be starting the algorithm by dividing it into parts. First, we will solve by checking if the rows and columns don’t have repeated numbers. Then we will look upon each 3×3 square if the numbers are not repeated.

Moreover, After the numbers are not checked for repetition, we will now fill the numbers in the correct order. Further, we will use a backtracking algorithm to continuously look for the correct number for the current position. Consequently,  If the number is found, the recursive call return true, else returns false and the recursive call is ended stating “no solution exists”.

Algorithm

1. First checking if the current number is not repeated in rows or columns through loops.
2. Then checking if the box has the number already or not.
3. After a vacant position is found, we will recursively check for numbers(1 – 9) that fit the position perfectly.
4. If the number fits perfectly, the recursive call returns true, else it returns false and recursive calls are terminated.

Java Code for Sudoku Solver

//Uses Backtracking algorithm to solve sudoku puzzle

import java.util.Scanner;
class BackTrack
{ 
public static boolean SafetyCheck(int[][] grid,  
                             int row, int col,  
                             int num)  
{ 
    // row check - returns false if existing number is present
    for (int i = 0; i < grid.length; i++)  
    {  
        if (grid[row][i] == num)  
        { 
            return false; 
        } 
    } 
      
    // column check - returns false if existing number is present
    for (int i = 0; i < grid.length; i++) 
    {   
        if (grid[i][col] == num) 
        { 
            return false; 
        } 
    } 
  
    //3x3 grid check
    int root = (int) Math.sqrt(grid.length); 
    int Gridrow = row - row % root; 
    int GridCol = col - col % root; 
  
    for (int i = Gridrow;i < Gridrow + root; i++)  
    { 
        for (int j = GridCol;j < GridCol + root; j++)  
        { 
            if (grid[i][j] == num)  
            { 
                return false; 
            } 
        } 
    } 
  
    // Returning safe if no numbers are repeated 
    return true; 
} 
  
public static boolean SudokuSolver(int[][] grid, int n)  
{ 
    int row = -1; 
    int col = -1; 
    boolean empty = true; 
    for (int i = 0; i < n; i++) 
    { 
        for (int j = 0; j < n; j++)  
        { 
            if (grid[i][j] == 0)  
            { 
                row = i; 
                col = j; 
                empty = false;   //for empty spaces  
                break; 
            } 
        } 
        if (!empty) 
        { 
            break; 
        } 
    } 
   
    if (empty)  
    { 
        return true; 
    } 
  
    // calling recursively for checking 
    //other position if the current postion is invalid
    //by backtracking
    for (int k = 1; k <= n; k++) 
    { 
        if (SafetyCheck(grid, row, col, k)) 
        { 
            grid[row][col] = k; 
            if (SudokuSolver(grid, n))  
            { 
              return true; 
            }  
            else
            { 
                grid[row][col] = 0;  
            } 
        } 
    } 
    return false; //if there is no solution for the position hence ending the call
} 
  
public static void print(int[][] grid, int N)     //printing the solved sudoku 
{  System.out.println("\n\n\nThe Solution:\n");

    for (int i = 0; i < N; i++) 
    { 
        for (int j = 0; j < N; j++) 
        { 
            System.out.print(grid[i][j]); 
            System.out.print(" "); 
        } 
        System.out.print("\n"); 
        //for printing spaces to form grid  
        if ((i + 1) % (int) Math.sqrt(N) == 0)  
        { 
            System.out.print(""); 
        } 
    } 
} 
  
// Driver Code 
public static void main(String args[]) 
{   
    int[][] grid = new int[9][9];
    Scanner s=new Scanner(System.in); 
    for(int i=0;i<9;i++)
  for(int j=0;j<9;j++)
    grid[i][j]=s.nextInt();	
     
    int length = grid.length; 
  
    if (SudokuSolver(grid, length)) 
    { 
        print(grid, length); // print solution 
    }  
    else
    { 
        System.out.println("No Solution Exists"); 
    } 
} 
}

Output:-

Time and Space Complexity:-

Since this uses a 9 x 9 grid and checks for each possibility, its time complexity is O(9^(N x N)). But Space complexity is (N x N) as it only operates on (N x N) grid.

I hope you will like the article. Any doubts or corrections are welcomed.

Thank you.