Backtracking on Sudoku Solver

Introduction:

Backtracking is a powerful algorithmic technique for solving combinatorial problems. In the context of a Sudoku solver, it systematically searches for a solution by trying all possibilities and backtracking whenever a constraint is violated.

How Backtracking Works:

The algorithm fills empty cells one by one with numbers from 1 to 9, checking if the current number is valid. If a conflict arises, it backtracks to the previous cell and tries the next number.

Step-by-Step Diagram:

Step 1: Start with an empty cell
[5 3 _ | 6 _ _ | _ 9 8]
[7 _ _ | 1 9 5 | _ _ _]
[_ 9 8 | _ _ _ | _ 6 _]
---------------------
[8 _ _ | _ 6 _ | _ _ 3]
[4 _ _ | 8 _ 3 | _ _ 1]
[7 _ _ | _ 2 _ | _ _ 6]
---------------------
[_ 6 _ | _ _ _ | 2 8 _]
[_ _ _ | 4 1 9 | _ _ 5]
[_ _ _ | _ 8 _ | _ 7 9]

Step 2: Try a number in the first empty cell
[5 3 4 | 6 _ _ | _ 9 8]
[7 _ _ | 1 9 5 | _ _ _]
[_ 9 8 | _ _ _ | _ 6 _]
---------------------
[8 _ _ | _ 6 _ | _ _ 3]
[4 _ _ | 8 _ 3 | _ _ 1]
[7 _ _ | _ 2 _ | _ _ 6]
---------------------
[_ 6 _ | _ _ _ | 2 8 _]
[_ _ _ | 4 1 9 | _ _ 5]
[_ _ _ | _ 8 _ | _ 7 9]

Step 3: Continue filling the grid
[5 3 4 | 6 7 8 | 9 1 2]
[6 7 2 | 1 9 5 | 3 4 8]
[1 9 8 | 3 4 2 | 5 6 7]
---------------------
[8 5 9 | 7 6 1 | 4 2 3]
[4 2 6 | 8 5 3 | 7 9 1]
[7 1 3 | 9 2 4 | 8 5 6]
---------------------
[9 6 1 | 5 3 7 | 2 8 4]
[2 8 7 | 4 1 9 | 6 3 5]
[3 4 5 | 2 8 6 | 1 7 9]

Step 4: Completed grid
[5 3 4 | 6 7 8 | 9 1 2]
[6 7 2 | 1 9 5 | 3 4 8]
[1 9 8 | 3 4 2 | 5 6 7]
---------------------
[8 5 9 | 7 6 1 | 4 2 3]
[4 2 6 | 8 5 3 | 7 9 1]
[7 1 3 | 9 2 4 | 8 5 6]
---------------------
[9 6 1 | 5 3 7 | 2 8 4]
[2 8 7 | 4 1 9 | 6 3 5]
[3 4 5 | 2 8 6 | 1 7 9]
    

Code Implementation:

public class SudokuSolver {
    private static final int SIZE = 9;

    public boolean solveSudoku(int[][] board) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                if (board[row][col] == 0) {
                    for (int num = 1; num <= SIZE; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            if (solveSudoku(board)) {
                                return true;
                            }
                            board[row][col] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(int[][] board, int row, int col, int num) {
        for (int i = 0; i < SIZE; i++) {
            if (board[row][i] == num || board[i][col] == num || 
                board[row - row % 3 + i / 3][col - col % 3 + i % 3] == num) {
                return false;
            }
        }
        return true;
    }
}
      

Sudoku Solved Successfully!