Solve Sudoku - Backtracking

Introduction

Sudoku is a popular number puzzle where the goal is to fill in a 9x9 grid with numbers from 1 to 9 such that each row, column, and 3x3 block contains all of the numbers from 1 to 9.

Approach

We can use a backtracking algorithm to find a solution for the Sudoku puzzle. The basic idea is to try filling in the empty cells with valid values, and if we reach a point where no valid value can be placed in any of the remaining empty cells, we backtrack and try a different value for a previously filled cell.

Implementation

The SudokuSolver class contains the main method which initializes the Sudoku board as a two-dimensional array of integers and calls the solve() method to find a solution.

The solve() method is a recursive function that takes the row and column of the current cell as input. It first checks if the current cell is the last column of the last row. If it is, the function returns true to indicate that a solution has been found.

If the current cell is not the last column of the last row, the function checks if the cell is already filled. If it is, the function calls itself recursively with the next cell as the current cell. If the cell is empty, the function tries all possible values for the cell using a loop. For each value, it checks if it is a valid choice for the current cell using the isSafe() method. If the value is valid, it assigns it to the current cell and calls itself recursively with the next cell as the current cell. If the function returns true, the function returns true to indicate that a solution has been found. If the function returns false, the function backtracks and tries the next value. If no value works, the function returns false to indicate that no solution was found.

The isSafe() method checks if the given value is a valid choice for the given cell. It returns true if the value is not already used in the current row, column, or 3x3 block, and false otherwise.

The display() method is a helper function that prints the Sudoku board to the console.

Conclusion

This Sudoku solver uses a backtracking algorithm to find a solution for the puzzle. It works by trying different values for the empty cells and backtracking when no valid value can be placed in any of the remaining empty cells. The algorithm terminates when a solution is found or when it has tried all possible values and none of them worked.

Code

public class SudokuSolver {
    public static void main(String[] args) {
        int[][] board = {
                {0,0,5,6,9,0,0,0,0},
                {0,3,0,0,0,0,0,0,9},
                {0,0,8,0,0,0,0,1,0},
                {4,7,0,0,3,0,0,0,0},
                {1,0,0,0,0,4,0,0,8},
                {0,0,0,0,0,7,0,0,0},
                {0,0,0,0,0,0,4,7,1},
                {0,0,0,2,0,0,3,0,0},
                {0,0,0,3,0,5,8,0,0}
        };
        if(solve(board)){
            System.out.println(board);
        }
        else{
            System.out.println("Sudoku Cannot be solved");
        }
    }

    static boolean solve(int[][] board){
        int n = board.length;
        int row = -1;
        int col = -1;

        boolean emptyLeft = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == 0){
                    row = i;
                    col = j;
                    emptyLeft = false;
                    break;
                }
            }
            if(!emptyLeft){
                break;
            }
        }
        if(emptyLeft){
            return true;
        }
        for (int number = 1; number <= 9; number++) {
            if(isSafe(board, row, col, number)){
                board[row][col] = number;
                if(solve(board)){
                    display(board);
                    return true;
                }
                else{
                    board[row][col] = 0;
                }
            }
        }
        return false;
    }

    private static void display(int[][] board) {
        for(int[] row : board){
            for(int number : row){
                System.out.print(number + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static boolean isSafe(int[][] board, int row, int col, int num){
        for (int i = 0; i < board.length; i++) {
            if(board[row][i] == num){
                return false;
            }
        }
        for(int[] nums : board){
            if(nums[col] == num){
                return false;
            }
        }
        int sqrt = (int)(Math.sqrt(board.length));
        int rowStart = row - row % sqrt;
        int colStart = col - col % sqrt;

        for (int r = rowStart; r < rowStart + sqrt; r++) {
            for (int c = colStart; c < colStart + sqrt; c++) {
                if(board[r][c] == num){
                    return false;
                }
            }
        }
        return true;
    }
}