Как написать алгоритм для решения головоломки Судоку?

Классический алгоритм для решения Судоку — поиск с возвратом (Backtracking). Он перебирает возможные варианты чисел для пустых клеток и откатывается при обнаружении противоречия.

Принцип работы:

1. Найти первую пустую клетку (обозначенную как 0).
2. Попробовать подставить в нее числа от 1 до 9.
3. Для каждого числа проверить, допустимо ли оно по правилам Судоку (отсутствие в строке, столбце и блоке 3x3).
4. Если число допустимо, поместить его в клетку и рекурсивно вызвать алгоритм для решения оставшейся части сетки.
5. Если рекурсивный вызов вернул true — решение найдено.
6. Если ни одно число не подошло — откатиться (backtrack): обнулить клетку и вернуть false, чтобы предыдущий вызов попробовал другое число.

Реализация на Java:

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

    public boolean solve(int[][] board) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                if (board[row][col] == EMPTY) {
                    for (int num = 1; num <= SIZE; num++) {
                        if (isValidPlacement(board, row, col, num)) {
                            board[row][col] = num; // Пробуем число
                            if (solve(board)) {    // Рекурсивно решаем дальше
                                return true;       // Решение найдено!
                            }
                            board[row][col] = EMPTY; // Откат (backtrack)
                        }
                    }
                    return false; // Нет допустимых чисел для этой клетки
                }
            }
        }
        return true; // Все клетки заполнены
    }

    private boolean isValidPlacement(int[][] board, int row, int col, int num) {
        // Проверка строки и столбца
        for (int i = 0; i < SIZE; i++) {
            if (board[row][i] == num || board[i][col] == num) {
                return false;
            }
        }
        // Проверка блока 3x3
        int blockRowStart = 3 * (row / 3);
        int blockColStart = 3 * (col / 3);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[blockRowStart + i][blockColStart + j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}

Сложность: В худшем случае O(9^(N)), где N — количество пустых клеток, но на практике откаты сокращают перебор, и алгоритм решает стандартные головоломки почти мгновенно.