Introduction

Sudoku is a popular logic-based puzzle that involves filling a 9×9 grid with digits from 1 to 9. The objective is to fill in the grid so that each row, each column, and each 3×3 sub-grid (also called a “box”) contain all digits from 1 to 9, with no repetition. The puzzle typically starts with some cells pre-filled, and the task is to fill in the remaining cells to complete the puzzle.

In this example, we will write a Java program that solves Sudoku puzzles using a technique known as “backtracking”. This method systematically fills in the grid and backtracks whenever it encounters a cell that cannot be filled with a valid number. The program will check whether a number is valid in the current row, column, and sub-grid before placing it in the cell.

Objective

The objective of this program is to create a Sudoku solver in Java that:

• Takes a partially filled 9×9 Sudoku grid as input.
• Uses the backtracking algorithm to solve the puzzle.
• Displays the solved Sudoku grid after finding the solution.

Code

public class SudokuSolver {

    // Define the size of the Sudoku grid
    private static final int SIZE = 9;

    // Function to solve the Sudoku puzzle
    public static boolean solveSudoku(int[][] board) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                // Find an empty cell
                if (board[row][col] == 0) {
                    // Try placing numbers 1 to 9 in the empty cell
                    for (int num = 1; num <= SIZE; num++) {
                        if (isSafe(board, row, col, num)) {
                            board[row][col] = num;
                            
                            // Recursively attempt to solve the rest of the grid
                            if (solveSudoku(board)) {
                                return true;
                            }
                            
                            // If the number does not lead to a solution, reset the cell
                            board[row][col] = 0;
                        }
                    }
                    // If no valid number can be placed, return false
                    return false;
                }
            }
        }
        // If the entire grid is filled, return true
        return true;
    }

    // Function to check if it's safe to place a number in a specific cell
    public static boolean isSafe(int[][] board, int row, int col, int num) {
        // Check the row
        for (int x = 0; x < SIZE; x++) {
            if (board[row][x] == num) {
                return false;
            }
        }
        
        // Check the column
        for (int x = 0; x < SIZE; x++) {
            if (board[x][col] == num) {
                return false;
            }
        }

        // Check the 3x3 sub-grid
        int startRow = row - row % 3;
        int startCol = col - col % 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i + startRow][j + startCol] == num) {
                    return false;
                }
            }
        }

        // The number can be safely placed in the cell
        return true;
    }

    // Function to print the Sudoku board
    public static void printBoard(int[][] board) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // Example of a Sudoku puzzle with some pre-filled numbers (0 means empty)
        int[][] board = new int[][] {
            {5, 3, 0, 0, 7, 0, 0, 0, 0},
            {6, 0, 0, 1, 9, 5, 0, 0, 0},
            {0, 9, 8, 0, 0, 0, 0, 6, 0},
            {8, 0, 0, 0, 6, 0, 0, 0, 3},
            {4, 0, 0, 8, 0, 3, 0, 0, 1},
            {7, 0, 0, 0, 2, 0, 0, 0, 6},
            {0, 6, 0, 0, 0, 0, 2, 8, 0},
            {0, 0, 0, 4, 1, 9, 0, 0, 5},
            {0, 0, 0, 0, 8, 0, 0, 7, 9}
        };

        // Solve the Sudoku puzzle
        if (solveSudoku(board)) {
            System.out.println("Sudoku solved successfully:");
            printBoard(board);
        } else {
            System.out.println("No solution exists.");
        }
    }
}

Program Explanation

This Java program works as follows:

• The program uses a 9×9 2D array to represent the Sudoku board, where each element can either be a number from 1 to 9 or 0 (indicating an empty cell).
• The solveSudoku function is the core of the backtracking algorithm. It finds the first empty cell (represented by 0) and attempts to place each number (from 1 to 9) in that cell. For each number, it checks if it is safe to place by calling the isSafe function. If placing a number leads to a valid solution, the program proceeds to fill the next empty cell. If no valid number can be placed, it backtracks by resetting the cell to 0 and trying the next possible number.
• The isSafe function checks if a number can be placed in a given cell without violating the Sudoku rules. It checks the current row, column, and 3×3 sub-grid for any conflicting numbers.
• The program prints the solved Sudoku board to the console once the puzzle is solved or indicates that no solution exists.

How to Run the Program

To run this program, follow these steps:

1. Save the program code in a file named SudokuSolver.java.
2. Compile the program using the Java compiler:

   javac SudokuSolver.java

3. Run the compiled program:

   java SudokuSolver

4. The program will solve the Sudoku puzzle and print the solution to the console.