Возврат: как решать судоку и N-Queens с помощью рекурсии

Зачем вам возврат?

Вы когда-нибудь смотрели на пустую сетку судоку на собеседовании и чувствовали, как мозг закипает? Интервьюер улыбается: «Просто заполните». Легко, да? После нескольких минут хаотичных попыток вы понимаете, что перебираете все числа во всех клетках — 9^81 вариантов. Вспоминается сцена из «Матрицы», где Нео видит код дождём. Хотелось бы увидеть скрытые ограничения, чтобы отсечь безумие. Ответ — возврат (backtracking). Это не очередной трюк с рекурсией, а принципиальный способ исследовать варианты, зная, когда повернуть назад.

Суть возврата

В основе возврата лежит поиск в глубину с совестью. Представьте, что вы идёте по лабиринту. На каждом перекрёстке вы выбираете направление и постоянно спрашиваете: «Есть ли у этого пути шанс привести к выходу?» Если нет, вы немедленно возвращаетесь на последний перекрёсток и пробуете другой маршрут. Магия в проверке ограничений. Прежде чем сделать выбор, мы проверяем его на соответствие правилам задачи. Если выбор нарушает правило, мы отбрасываем ветвь мгновенно. Это превращает экспоненциальный перебор в нечто почти мгновенное.

Примеры кода: от наивного к эффективному

Наивный решатель судоку (без отсечения)

def solve_sudoku_bruteforce(board):
    empty = find_empty(board)
    if not empty:
        return True  # решено
    row, col = empty
    for num in range(1, 10):
        board[row][col] = num
        if solve_sudoku_bruteforce(board):
            return True
        board[row][col] = 0  # отмена
    return False

Функция работает, но на сложных головоломках блуждает вечно, потому что не спрашивает: «Разрешено ли num здесь?» Конфликт обнаруживается только после погружения.

Решатель с возвратом (с проверкой ограничений)

def is_valid(board, row, col, num):
    # проверка строки
    if any(board[row][c] == num for c in range(9)):
        return False
    # проверка столбца
    if any(board[r][col] == num for r in range(9)):
        return False
    # проверка блока 3x3
    start_r, start_c = 3 * (row // 3), 3 * (col // 3)
    for r in range(start_r, start_r + 3):
        for c in range(start_c, start_c + 3):
            if board[r][c] == num:
                return False
    return True

def solve_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True
    row, col = empty
    for num in range(1, 10):
        if is_valid(board, row, col, num):  # <-- отсечение
            board[row][col] = num
            if solve_sudoku(board):
                return True
            board[row][col] = 0  # возврат
    return False

Строка if is_valid(...) — секретный ингредиент. Она отсекает целые поддеревья, превращая безнадёжный перебор в быстрый решатель.

Задача N-Queens — тот же шаблон

def solve_n_queens(n):
    board = [-1] * n  # board[row] = столбец ферзя в этой строке
    def backtrack(row):
        if row == n:
            return True  # все ферзи расставлены
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                if backtrack(row + 1):
                    return True
                board[row] = -1  # возврат
        return False
    return backtrack(0)

def is_safe(board, row, col):
    for r in range(row):
        c = board[r]
        if c == col or abs(c - col) == row - r:
            return False
    return True

Проверка is_safe — наш досрочный выход. Без неё мы бы перебирали все перестановки столбцов (N! вариантов) и замечали диагональную атаку только после расстановки половины ферзей.

Частые ошибки

• Забыть отменить выбор — если не сбросить board[row][col] после рекурсивного вызова, состояние загрязняется для соседних ветвей.
• Проверка слишком поздно — размещение проверки после рекурсивного вызова лишает смысла отсечение.
• Неосторожное использование глобального состояния — передавайте копию или мутируйте и возвращайте; смешение подходов ведёт к ошибкам.

Почему это важно

Вооружившись возвратом, вы сможете решать целый класс задач на собеседованиях: судоку, N-Queens, поиск слов, раскраску графов, настройку конфигураций. Шаблон всегда один: определить точку принятия решения, определить быструю проверку ограничений, рекурсивно перебирать и отменять. Благодаря отсечению при первом нарушении эффективное ветвление резко снижается. На практике судоку решается за несколько тысяч рекурсивных вызовов, N-Queens для N=15 — за доли секунды. Это отличная модель для реальных систем: распространение ограничений в планировании, проверка конфигураций, AI-планирование.

Практический вывод: ваша очередь

Попробуйте модифицировать решатель судоку, чтобы он возвращал все решения, а не только первое. Подсказка: собирайте решения в список и продолжайте поиск после нахождения. Или реализуйте Knight's Tour по тому же шаблону — измените проверку на «клетка внутри доски и не посещена». Выложите код в комментариях. Настоящая победа — не просто работающая программа, а ощущение, как дерево поиска сжимается на глазах, словно Нео уклоняется от пуль, видя Матрицу такой, какая она есть.