Java Sudoku Solver Program

Filed Under: Java
SUDOKU SOLVER

Remember Sudoku sections from newspapers? That grid-like puzzle filled with numbers.

Sudoku is a logic-based, combinatorial number-placement puzzle. In classic sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contain all of the digits from 1 to 9.

To solve the sudoku, you need to fill in the digits such that your solution violates none of the constraints. It can be harder than it sounds…..not for a computer though.

In this article, we will learn how to write Java code that solves sudoku within seconds.

The world record for solving a Sudoku is 1 minute 23.93 seconds. Let’s break that. Shall we?

Sudoku Number Constraints

What are the constraints in solving a sudoku?

  • A number can occur only once in a row
  • A number can occur only once in a column
  • A number can occur only once in a subgrid.

While solving, we will use these constraints to design our helper functions.

Let’s get started!

Representation of a Sudoku

A sudoku problem comes with some digits filled in already. The goal is to figure out the missing digits through trial and error.

The sudoku will be a 2D array for the computer.

In our representation we will represent the missing digits with 0.

Sudoku
Sudoku Representation

Representation of the sudoku above is:

 int[][] arr = {{5, 8, 0, 2, 0, 0, 4, 7, 0},
                {0, 2, 0, 0, 0, 0, 0, 3, 0},
                {0, 3, 0, 0, 5, 4, 0, 0, 0},
                {0, 0, 0, 5, 6, 0, 0, 0, 0},
                {0, 0, 7, 0, 3, 0, 9, 0, 0},
                {0, 0, 0, 0, 9, 1, 0, 0, 0},
                {0, 0, 0, 8, 2, 0, 0, 6, 0},
                {0, 7, 0, 0, 0, 0, 0, 8, 0},
                {0, 9, 4, 0, 0, 6, 0, 1, 5}};

The digit 0 helps us in identifying which place is for the user to fill.

Solving the Sudoku in Java

Here’s the fun part! Fasten your seatbelts and let’s go!

We will use a lot of functions to perform specific tasks.

1. Getting the unassigned position

This function will return the position in our sudoku that are not yet assigned. It returns (-1,-1) if no unassigned position is available. This would be the case when our sudoku is complete.

 public static int[] Unassigned(int[][] arr) {

        int[] ra = new int[2]; //returns the position of first unassigned position
        ra[0] = -1;
        ra[1] = -1;

        for (int row = 0; row < arr.length; row++) {
            for (int col = 0; col < arr.length; col++) {
                if (arr[row][col] == 0) {
                    ra[0] = row;
                    ra[1] = col;
                    return ra;
                }
            }
        }

        return ra;
}

The function returns the position (i,j) in the form of an array. The function simply finds the first position with 0 as its entry.

2. Can this number be used in this position?

To answer this question we need to check three things. These are the three constraints of a sudoku problem.

Three functions that check the three constraints are :

usedInRow checks for the occurrence of num in row.

usedIncol checks for the occurrence of num in col.

usedInBox checks for the occurrence of num in the box. To specify which box, (row1Start,col1Start) provide the coordinates of the first position in the box.

public static boolean usedInRow(int[][] grid, int row, int num) {
        for (int i = 0; i < grid.length; i++) {
            if (grid[row][i] == num) {
                return true;
            }
        }
        return false;
    }//is it used in that row?

    public static boolean usedIncol(int[][] grid, int col, int num) {
        for (int i = 0; i < grid.length; i++) {
            if (grid[i][col] == num) {
                return true;
            }
        }
        return false;
    }//is it used in that col?

    public static boolean usedInBox(int[][] grid, int row1Start, int col1Start, int num) {
        for (int row = 0; row < 3; row++)
            for (int col = 0; col < 3; col++)
                if (grid[row + row1Start][col + col1Start] == num) {
                    return true;
                }
        return false;

    }//is it used in that box?

The three functions return true or false. The functions return true if num appears in that particular row, column or box.

3. Putting the three conditions together

A function by the name of isSafe calls the three functions above. The isSafe function checks for simultaneous satisfaction of all three conditions.

Role of isSafe is to determine whether it is safe to put the digit ‘num’ at the position (row,col).

When all three functions return false, isSafe will return true. That is because when the number is not used in the same row, column or box as the position, only then it would be safe for the number to occur at that position.

public static boolean isSafe(int[][] grid, int row, int col, int num) {
        return (!usedIncol(grid, col, num) && !usedInRow(grid, row, num) && !usedInBox(grid, row - row % 3, col - col % 3, num));

    }//is it safe to place that number at that position, might not be correct nut just safe

4. The Sudoku Solver Method

With the understanding of the helper functions above, we can move forward to the part of actually solving the sudoku.

    public static boolean sudoku(int[][] grid) {
        int[] ra = Unassigned(grid);
        if (ra[0] == -1) {
            return true;
        }

        int row = ra[0];
        int col = ra[1];

        for (int num = 1; num <= 9; num++) {
            if (isSafe(grid, row, col, num)) {
                grid[row][col] = num;
                boolean check = sudoku(grid);
                if (check == true) {
                    return true;
                }
                grid[row][col] = 0;
            }
        }
        return false;
    }

To solve the sudoku, we use backtracking. Backtracking recursively finds the solution to the problem at hand.

The first step is to get the first unassigned position. If there is no unassigned position that means the sudoku is complete and we return true. The return type of the function is booleans since it will help in recursion (more on that in a bit).

Otherwise, if the sudoku is not yet complete, we run a loop from one to nine and see which of the digits will fit in that position. To achieve this, we call the function isSafe. The coordinates given to isSafe are that of the unassigned position.

The moment we find a digit that fits at the given position, we make the change in our 2D matrix. After making the change, we further call the function sudoku on the grid. This will look for the next unassigned position and try to fill that.

The variable check will be true if the sudoku is complete and no unassigned position is remaining. In that case, our sudoku is solved and we can call it a day (return true).

However, if the recursion call returns false, we need to backtrack on our current assignment. For that we set grid[row][col] as 0. This makes it unassigned and since it is in a for loop, the next digit between [1-9] will be tried at this position.

The process of recursion calls and backtracking continues until we arrive at a solution.

Java Sudoku Solver Complete Code

We know, you like code that you can just copy and run to see it for yourself. So here you go :

public class Main {

    public static void main(String[] args) {
        // write your code here

        int[][] arr = {{5, 8, 0, 2, 0, 0, 4, 7, 0},
                {0, 2, 0, 0, 0, 0, 0, 3, 0},
                {0, 3, 0, 0, 5, 4, 0, 0, 0},
                {0, 0, 0, 5, 6, 0, 0, 0, 0},
                {0, 0, 7, 0, 3, 0, 9, 0, 0},
                {0, 0, 0, 0, 9, 1, 0, 0, 0},
                {0, 0, 0, 8, 2, 0, 0, 6, 0},
                {0, 7, 0, 0, 0, 0, 0, 8, 0},
                {0, 9, 4, 0, 0, 6, 0, 1, 5}};
        print_initial(arr, arr.length);
        sudoku(arr);
        System.out.println("AFTER SOLVING : ");
        print(arr, arr.length);

    }

    public static boolean sudoku(int[][] grid) {
        int[] ra = Unassigned(grid);
        if (ra[0] == -1) {
            return true;
        }

        int row = ra[0];
        int col = ra[1];

        for (int num = 1; num <= 9; num++) {
            if (isSafe(grid, row, col, num)) {


                grid[row][col] = num;
                boolean check = sudoku(grid);
                if (check == true) {
                    return true;
                }
                grid[row][col] = 0;


            }
        }
        return false;
    }


    public static int[] Unassigned(int[][] arr) {

        int[] ra = new int[2]; //returns the position of first unassigned position
        ra[0] = -1;
        ra[1] = -1;

        for (int row = 0; row < arr.length; row++) {
            for (int col = 0; col < arr.length; col++) {
                if (arr[row][col] == 0) {
                    ra[0] = row;
                    ra[1] = col;
                    return ra;
                }
            }
        }

        return ra;


    }//returns the first unassigned position

    public static boolean usedInRow(int[][] grid, int row, int num) {
        for (int i = 0; i < grid.length; i++) {
            if (grid[row][i] == num) {
                return true;
            }
        }
        return false;
    }//is it used in that row?

    public static boolean usedIncol(int[][] grid, int col, int num) {
        for (int i = 0; i < grid.length; i++) {
            if (grid[i][col] == num) {
                return true;
            }
        }
        return false;
    }//is it used in that col?

    public static boolean usedInBox(int[][] grid, int row1Start, int col1Start, int num) {
        for (int row = 0; row < 3; row++)
            for (int col = 0; col < 3; col++)
                if (grid[row + row1Start][col + col1Start] == num) {
                    return true;
                }
        return false;

    }//is it used in that box?

    public static boolean isSafe(int[][] grid, int row, int col, int num) {//is it safe to place that number at that position, might not be correct nut just safe

        return (!usedIncol(grid, col, num) && !usedInRow(grid, row, num) && !usedInBox(grid, row - row % 3, col - col % 3, num));

    }

    public static void print(int[][] arr, int N) {// prints the sudoku
        for (int i = 0; i < N; i++) {
            if (i % 3 == 0 && i != 0) {
                System.out.println("----------|---------|----------");
            }
            int count1 = 0;
            for (int j = 0; j < N; j++) {


                if (j % 3 == 0) {
                    System.out.print("|");
                }
                System.out.print(" " + arr[i][j]
                        + " ");

            }
            System.out.println();
        }


    }
    public static void print_initial(int[][] arr, int N) {// prints the sudoku
        for (int i = 0; i < N; i++) {
            if (i % 3 == 0 && i != 0) {
                System.out.println("----------|---------|----------");
            }
            int count1 = 0;
            for (int j = 0; j < N; j++) {


                if (j % 3 == 0) {
                    System.out.print("|");
                }
                if(arr[i][j]==0){
                    System.out.print(" " + "-"
                            + " ");
                }
                else {
                    System.out.print(" " + arr[i][j]
                            + " ");
                }

            }
            System.out.println();
        }


    }


    public static boolean isSafe(int row, int col, int[][] board, int N) {
        //checking rows
        int i, j;

        /* Check this row on left side */
        for (i = 0; i < row; i++)
            if (board[i][col] == 1)
                return false;

        /* Check upper diagonal on left side */
        for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 1)
                return false;

        /* Check lower diagonal on left side */
        for (i = row, j = col; i >= 0 && j < N; j++, i--)
            if (board[i][j] == 1)
                return false;

        return true;

    }

}
Java Sudoku Solver Output
Java Sudoku Solver Output

The two functions print and print_initial just print the grid in the form of sudoku.

Conclusion

Our Sudoku solver beats the world record set by humans by 1 minute and 20 seconds. The code uses backtracking to solve the problem. Some of the famous problems that require backtracking for solving are n-queens problem and rat in a maze.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages