How to Implement a Sudoku Solver using Backtracking in Java

Question

What is a backtracking algorithm for solving Sudoku in Java and how can I implement it?

public class SudokuSolver {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    private boolean solve(char[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            if (solve(board)) {
                                return true;
                            }
                            board[row][col] = '.'; // backtrack
                        }
                    }
                    return false; // trigger backtracking
                }
            }
        }
        return true; // solved
    }
    private boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num || 
                board[3*(row/3) + i/3][3*(col/3) + i%3] == num) {
                return false;
            }
        }
        return true;
    }
}

Answer

Implementing a Sudoku solver using the backtracking algorithm in Java involves creating a method that tries to fill in the board by exploring possible numbers for each cell. Backtracking allows for efficiently navigating potential solutions and undoing decisions when a conflict is found.

public class SudokuSolver {
    public void solveSudoku(char[][] board) {
        if (solve(board)) {
            System.out.println("Sudoku solved successfully!");
        } else {
            System.out.println("Cannot solve the Sudoku.");
        }
    }
    private boolean solve(char[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            if (solve(board)) {
                                return true;
                            }
                            board[row][col] = '.'; // Undo
                        }
                    }
                    return false; // Trigger backtracking
                }
            }
        }
        return true; // Puzzle solved
    }
    private boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num || 
                board[3*(row/3) + i/3][3*(col/3) + i%3] == num) {
                return false;
            }
        }
        return true;
    }
}

Causes

Inadequate knowledge of backtracking principles.
Failure to handle invalid placements properly.
Lack of thorough testing with various Sudoku puzzles.

Solutions

Introduce a function to check if a number is valid for a given cell.
Implement recursive calls to try different numbers in empty cells.
Add a backtracking mechanism to revert changes when a number leads to an unsolvable state.

Common Mistakes

Mistake: Assuming that there is always a solution for any given board configuration.

Solution: Ensure that the Sudoku puzzle is solvable before applying the algorithm.

Mistake: Not checking all three rules of Sudoku (rows, columns, boxes) during validation.

Solution: Implement robust checks in the 'isValid' method to account for all rules.

Mistake: Not handling edge cases where no valid number can be placed.

Solution: Properly implement the backtracking step to return false and backtrack on conflicts.

Helpers

Sudoku solver
backtracking in Java
Sudoku algorithm
Java programming
Sudoku implementation Java