Backtracking: как решать судоку и N-Queens за миллисекунды

Почему вам стоит освоить backtracking прямо сейчас

Вы когда-нибудь пытались написать решатель судоку вручную? Я помню свою первую попытку: я просто перебирал все пустые клетки, подставлял числа и проверял, сработает ли. Через несколько часов программа перебирала миллиарды вариантов, а ответа всё не было. Ноутбук гудел как реактивный двигатель, а я чувствовал себя в бесконечном цикле. Тогда я задался вопросом: есть ли способ умнее, чем полный перебор? Ответ — backtracking (поиск с возвратом). Эта техника позволяет отсекать заведомо неправильные ветви, и судоку решается за миллисекунды. В этой статье вы узнаете, как работает backtracking, увидите готовый код на Python и сможете применить его к другим задачам.

Что такое backtracking: принцип и интуиция

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

Этот шаблон применим к множеству задач: судоку, N-Queens, раскраска графа, задачи составления расписания. Вам нужно лишь определить:

• Что такое «размещение» (число в клетке, ферзь на строке).
• Как проверить, что размещение допустимо на текущем состоянии.
• Как отменить размещение при откате.

Как только эти три компонента ясны, рекурсивный скелет почти одинаков для всех задач.

Пример 1: судоку — от перебора к backtracking

Наивный перебор (не делайте так)

from itertools import product

def solve_bruteforce(board):
    # Находим все пустые клетки
    empties = [(r, c) for r in range(9) for c in range(9) if board[r][c] == 0]
    # Перебираем все комбинации чисел
    for combo in product(range(1, 10), repeat=len(empties)):
        for (r, c), val in zip(empties, combo):
            board[r][c] = val
        if is_valid_board(board):
            return True
        # Сброс доски опущен для краткости
    return False

product из itertools создаёт 9^k комбинаций, где k — число пустых клеток. Даже для простого судоку это астрономическое число. Проверка is_valid_board сканирует всю доску каждый раз, что ещё хуже.

Backtracking-решение судоку

def solve_sudoku(board):
    def backtrack():
        # Ищем первую пустую клетку
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0:
                    for num in range(1, 10):
                        if safe(board, r, c, num):
                            board[r][c] = num  # размещаем
                            if backtrack():
                                return True   # решено!
                            board[r][c] = 0   # отменяем (backtrack)
                    return False  # возвращаемся выше
        return True  # нет пустых клеток → решено

    def safe(board, r, c, num):
        # Проверка строки и столбца
        for i in range(9):
            if board[r][i] == num or board[i][c] == num:
                return False
        # Проверка блока 3×3
        sr, sc = 3 * (r // 3), 3 * (c // 3)
        for i in range(sr, sr + 3):
            for j in range(sc, sc + 3):
                if board[i][j] == num:
                    return False
        return True

    return backtrack()

Что изменилось? Мы берём следующую пустую клетку, а не перебираем заранее заготовленный список. Для каждого кандидата num вызываем safe, которая проверяет только строку, столбец и локальный блок — константное время. Если safe не прошло, число пропускается; мы никогда не углубляемся. После размещения рекурсивно вызываем backtrack. Если он вернул False, отменяем размещение (board[r][c] = 0) и пробуем следующее число. Когда числа для клетки кончились, возвращаем False, чтобы заставить родителя откатиться выше.

Пример 2: задача N-Queens

Тот же скелет, только проверка безопасности другая.

def solve_nqueens(n):
    board = [-1] * n  # board[row] = столбец ферзя в этой строке

    def backtrack(row):
        if row == n:
            return True  # все ферзи расставлены
        for col in range(n):
            if is_safe(row, col, board):
                board[row] = col
                if backtrack(row + 1):
                    return True
                board[row] = -1  # отмена
        return False

    def is_safe(r, c, b):
        # Проверяем предыдущие строки на конфликт по столбцу и диагоналям
        for prow in range(r):
            pcol = b[prow]
            if pcol == c or abs(prow - r) == abs(pcol - c):
                return False
        return True

    return backtrack(0) and board

Обратите внимание: мы храним доску как массив длины n, где индекс — строка, а значение — столбец. Это экономит память и упрощает проверку.

Типичные ошибки новичков

• Забыть отменить размещение. Если после неудачной рекурсии не вернуть клетку в исходное состояние, доска останется «грязной», и вы пропустите верные решения.
• Проверять слишком поздно. Если проверять валидность только после расстановки всех чисел (как в наивном переборе), вы теряете огромное количество времени.
• Неаккуратная работа с изменяемыми объектами. Передача доски по ссылке — нормально, но нужно вручную отменять изменения, иначе получите недетерминированные результаты.

В наших примерах отмена стоит сразу после рекурсивного вызова — это правильный паттерн.

Практический вывод: что делать прямо сейчас

Backtracking — это не просто алгоритм, а мышление. Как только вы его освоите, многие задачи на собеседованиях перестанут пугать: «Напишите решатель судоку», «Расставьте N ферзей», «Найдите слово в квадрате слов» — все они решаются одним шаблоном.

Возьмите любую головоломку, которая кажется вам нудной: какуро, гамильтонов путь в небольшом графе или даже построитель кроссвордов. Напишите три компонента: размещение, проверку, отмену — и дайте backtracking сделать всю тяжёлую работу. Когда это «щёлкнет», вы почувствуете, что открыли чит-код для комбинаторного хаоса.

Ваше задание: решите задачу N-Queens для n=8 с помощью приведённого кода. Убедитесь, что программа находит все 92 решения (или хотя бы одно). Затем попробуйте модифицировать код для судоку размером 16×16. Делитесь результатами в комментариях!