🔴 Сложный ⏱️ 55 минут

Backtracking

📋 Содержание урока

Backtracking ♟️

Представь, что ты расставляешь мебель в новой квартире. Ты ставишь диван у окна, потом пытаешься поставить шкаф у соседней стены — и понимаешь, что дверь теперь не открывается. Ты не начинаешь весь план заново: ты просто убираешь шкаф оттуда, где его только что поставил, и пробуешь другое место, оставив диван на месте. Именно так работает backtracking — поиск с возвратом: решение строится шаг за шагом, а если очередной шаг заводит в тупик, отменяется только этот шаг, а не вся работа целиком.

Эта на первый взгляд бытовая идея лежит в основе одного из самых универсальных алгоритмических инструментов в информатике. Backtracking решает задачи, где решение — это последовательность выборов, подчинённых жёстким ограничениям: расставить ферзей на доске так, чтобы никто никого не бил, заполнить судоку так, чтобы в каждой строке, столбце и блоке цифры не повторялись, раскрасить карту так, чтобы соседние регионы не совпадали по цвету. Формально такие задачи называют задачами удовлетворения ограничений (constraint satisfaction problem, CSP), и backtracking — это, пожалуй, самый прямой и фундаментальный способ их решать.

Ключевая мысль урока в том, что backtracking — это не то же самое, что «перебрать вообще всё». Полный перебор построил бы все возможные комбинации целиком, а потом проверил бы каждую на соответствие правилам — это работает, но чудовищно расточительно, потому что подавляющее большинство вариантов оказываются заведомо неправильными задолго до того, как построены полностью. Backtracking проверяет ограничения на каждом промежуточном шаге, а не только в конце, и как только становится ясно, что текущая частичная конструкция обречена, вся ветвь дерева поиска обрезается сразу — без единого шанса потратить время на её достройку. Это отсечение бесперспективных веток (в англоязычной литературе — pruning) и есть главное отличие backtracking от наивного полного перебора, и именно оно превращает теоретически экспоненциальный алгоритм в практически применимый.

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

История

Термин «backtrack» (буквально — «отследить назад», «вернуться по своим шагам») ввёл в алгоритмический обиход американский математик Д. Х. Лемер в 1950-х годах, хотя сама идея использовалась и раньше — например, при ручном решении головоломок и комбинаторных задач математики применяли её интуитивно задолго до появления компьютеров. Лемер работал над задачами перечисления комбинаторных объектов — перестановок, сочетаний, разбиений — и понял, что многие такие задачи удобно представлять как последовательный процесс построения объекта по частям с возможностью «отступить», если частичная конструкция оказалась тупиковой.

Строгую и общую теоретическую базу под backtracking подвёл в 1967 году американский информатик Роберт Флойд (тот самый, в честь которого назван алгоритм Флойда — Уоршелла из одного из предыдущих уроков этого курса) в статье «Non-deterministic Algorithms» («Недетерминированные алгоритмы»). Флойд формализовал backtracking как способ моделировать «недетерминированные» вычисления — программы, которые как бы умеют угадывать правильный выбор на каждом шаге, — с помощью полностью детерминированного алгоритма, который перебирает варианты и умеет откатываться назад при ошибке. Эта работа заложила теоретический фундамент, на котором позже выросли целые направления информатики: от логического программирования до автоматического доказательства теорем.

Практическая слава backtracking пришла вместе с языком программирования Prolog, разработанным в начале 1970-х годов Аленом Колмероэ и его коллегами во Франции. В основе Prolog лежит механизм резолюции с поиском с возвратом: интерпретатор пытается доказать утверждение, выбирая правила одно за другим, и как только очередной путь доказательства заходит в тупик, автоматически откатывается к последней точке выбора и пробует следующий вариант. Ровно этот же принцип, только применённый не к логическому выводу, а к расстановке ферзей или заполнению судоку, — то, что ты разберёшь в этом уроке. Сегодня backtracking остаётся рабочей лошадкой везде, где нужно найти решение среди комбинаторно огромного, но структурированного пространства вариантов: от компиляторов и SAT-солверов до систем планирования в робототехнике и логике игр.

Идея backtracking и отличие от полного перебора

Интуиция

Представь задачу: у тебя есть набор предметов с весами $[3, 5, 7, 2]$, и нужно найти любое подмножество, сумма весов которого равна ровно $9$. Самый прямолинейный способ — полный перебор: сгенерировать все $2^4 = 16$ возможных подмножеств (включая пустое), для каждого посчитать сумму и проверить равенство $9$. Это сработает, но обрати внимание: как только частичная сумма уже превысила $9$, дальнейшее добавление предметов с положительными весами только увеличит её — то есть уже сейчас понятно, что все подмножества, «растущие» из этой частичной суммы, заведомо не подходят, и достраивать их до конца полностью бессмысленно.

Backtracking именно на этом и экономит: вместо того чтобы сначала построить весь объект целиком, а потом проверить его на годность, он проверяет ограничения по ходу построения, после каждого отдельного шага. Как только частичное решение нарушает ограничение — сумма превысила цель, две фигуры бьют друг друга, цифра уже встречается в строке — алгоритм немедленно останавливает достройку этой ветки и возвращается на шаг назад, чтобы попробовать другой вариант. Он никогда не тратит время на то, чтобы полностью построить заведомо неверный вариант, если его неверность можно было обнаружить раньше.

Алгоритм

Схема отличия backtracking от полного перебора:

  1. Полный перебор (brute force): сгенерировать все возможные полные конструкции независимо от их корректности → для каждой полной конструкции проверить, удовлетворяет ли она всем ограничениям → оставить только подходящие.
  2. Backtracking: строить конструкцию по одному элементу за раз → после добавления каждого элемента сразу проверить ограничения на частичной конструкции → если ограничение нарушено, прекратить достройку этой ветки немедленно и вернуться на шаг назад (откатить последний выбор) → если ограничения выполняются, рекурсивно продолжить достройку дальше.

Разница выглядит как одна переставленная строчка кода, но на практике она определяет, будет ли алгоритм работать за разумное время или же за время жизни вселенной.

Разбор примеров

Пример 1 (сумма подмножества, полный перебор против backtracking). Массив $[3, 5, 7, 2]$, цель — подмножество с суммой $9$.

Полный перебор сгенерировал бы все $16$ подмножеств: $\emptyset, \{3\}, \{5\}, \{7\}, \{2\}, \{3,5\}, \{3,7\}, \{3,2\}, \{5,7\}, \{5,2\}, \{7,2\}, \{3,5,7\}, \{3,5,2\}, \{3,7,2\}, \{5,7,2\}, \{3,5,7,2\}$ — и для каждого посчитал бы сумму. Среди них подходит $\{7,2\}$ (сумма $9$) и $\{3,5,2\}$ ошибка нет — $3+5+2=10$, не подходит, единственное точное совпадение — $\{7,2\}=9$.

Backtracking строит подмножество поэлементно, решая для каждого элемента массива «включить или нет», и после каждого шага сравнивает текущую частичную сумму с целью:

def subset_sum(arr, target):
    result = []
    current = []

    def backtrack(index, current_sum):
        if current_sum == target:
            result.append(current[:])
            return
        if index == len(arr) or current_sum > target:
            return  # тупик — превышение цели или конец массива

        # выбор: включить arr[index]
        current.append(arr[index])
        backtrack(index + 1, current_sum + arr[index])
        current.pop()  # откат

        # выбор: не включать arr[index]
        backtrack(index + 1, current_sum)

    backtrack(0, 0)
    return result

Трассировка: индекс $0$ (значение $3$), сумма $0$. Ветка «включить $3$» → сумма $3$ → индекс $1$ (значение $5$), «включить» → сумма $8$ → индекс $2$ (значение $7$), «включить» → сумма $15 > 9$ — тупик, откат без захода в индекс $3$ вообще. Возврат в индекс $2$, ветка «не включать $7$» → сумма $8$ → индекс $3$ (значение $2$), «включить» → сумма $10 > 9$ — тупик, откат; «не включать» → сумма $8$, индекс $4$ = конец массива, сумма $8 \neq 9$ — тупик. Дальше идёт откат до индекса $1$ ветки «не включать $5$» → сумма $3$ → индекс $2$ (значение $7$), «включить» → сумма $10 > 9$ — тупик; «не включать» → сумма $3$ → индекс $3$ (значение $2$), «включить» → сумма $5$, конец массива, не совпало; «не включать» → сумма $3$, не совпало. Откат до индекса $0$, ветка «не включать $3$» → сумма $0$ → индекс $1$ (значение $5$) «включить» → сумма $5$ → индекс $2$ (значение $7$) «включить» → сумма $12>9$ тупик; «не включать» → сумма $5$ → индекс $3$ (значение $2$) «включить» → сумма $7$, конец, не совпало; «не включать» → $5$, не совпало. Откат, «не включать $5$» → сумма $0$ → индекс $2$ (значение $7$) «включить» → сумма $7$ → индекс $3$ (значение $2$) «включить» → сумма $\mathbf{9}$ — совпадение! Записываем $\{7, 2\}$.

Обрати внимание на ключевой момент: как только сумма $15$ превысила цель $9$ на глубине всего в три элемента, backtracking полностью отказался от достройки этой ветки до четвёртого элемента — а полный перебор всё равно построил бы соответствующее подмножество $\{3,5,7\}$ целиком, просто чтобы затем его отбросить.

Пример 2 (путь в лабиринте — наглядная демонстрация отката). Дана сетка $3\times3$, где # — стена, . — проход, нужно дойти из левого верхнего угла в правый нижний, двигаясь только вправо или вниз:

S . #
. # .
. . E

Backtracking пробует путь пошагово: из S (0,0) сначала «вправо» → (0,1) — проход. Из (0,1) «вправо» → (0,2) — это #, стена, шаг запрещён ограничением, дальше не идём. Из (0,1) пробуем «вниз» → (1,1) — это #, тоже стена, запрещено. Оба варианта из (0,1) — тупик, откат в (0,0). Из (0,0) пробуем «вниз» → (1,0) — проход. Из (1,0) «вправо» → (1,1) — стена, запрещено. Из (1,0) «вниз» → (2,0) — проход. Из (2,0) «вправо» → (2,1) — проход. Из (2,1) «вправо» → (2,2) — это E, цель достигнута.

def find_path(grid, r, c, path):
    rows, cols = len(grid), len(grid[0])
    if r >= rows or c >= cols or grid[r][c] == '#':
        return False  # тупик — за пределами сетки или стена
    path.append((r, c))
    if grid[r][c] == 'E':
        return True
    if find_path(grid, r, c + 1, path) or find_path(grid, r + 1, c, path):
        return True
    path.pop()  # откат — обе клетки-соседа оказались тупиковыми
    return False

Обрати внимание на строчку path.pop() — это и есть откат в буквальном смысле: если ни один из соседей не привёл к цели, текущая клетка удаляется из накопленного пути, и функция сообщает вызывающему коду «отсюда дороги нет», позволяя тому попробовать другую ветку.

Пример 3 (раскраска карты в три цвета). Три соседних региона $A$, $B$, $C$, где $A$ граничит с $B$ и $B$ граничит с $C$, но $A$ и $C$ не граничат. Доступные цвета: красный, зелёный, синий. Полный перебор проверил бы все $3^3 = 27$ комбинаций цветов и на каждой отдельно проверял оба ограничения. Backtracking красит регионы по одному и сразу отбрасывает недопустимые продолжения: красим $A$ в красный. Красим $B$ — раз $B$ граничит с $A$, цвет $B$ не может быть красным, пробуем зелёный — допустимо (ограничение с $A$ выполнено). Красим $C$ — $C$ граничит только с $B$, значит цвет $C$ не может быть зелёным (ограничение с $A$ не действует, так как они не граничат); пробуем красный — допустимо, решение найдено за три шага, ни разу не откатившись. Если бы на третьем шаге ограничение всё же нарушилось (гипотетически, если бы $C$ граничил и с $A$, и цвет пришлось бы выбирать из уже занятых двух), backtracking откатился бы к выбору цвета для $B$ и попробовал другой вариант, а не начинал бы весь перебор заново.

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

Разница между backtracking и полным перебором — это не вопрос элегантности кода, а вопрос принципиальной применимости алгоритма на практике. Формально оба подхода в худшем случае имеют экспоненциальную сложность: пространство вариантов растёт как $O(k^n)$ или $O(n!)$ в зависимости от задачи, и никакое отсечение веток не меняет эту верхнюю границу асимптотически. Но на практике — а именно практика в итоге определяет, дождёшься ли ты ответа программы за секунду или за геологическую эпоху — отсечение бесперспективных ветвей на ранних уровнях дерева поиска устраняет из рассмотрения экспоненциально большие поддеревья целиком, ни разу не заходя в них. Для судоку это разница между решением за миллисекунды и решением, которое не завершится никогда; для задачи о восьми ферзях — разница между перебором миллионов вариантов и перебором тысяч.

Общий шаблон алгоритма backtracking

Интуиция

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

Алгоритм

Общий шаблон backtracking:

  1. Выбор (choose). На каждом шаге рекурсии выбрать один из доступных вариантов продолжения частичного решения — следующий элемент для добавления, следующую клетку для заполнения, следующую позицию для размещения.
  2. Проверка ограничений (constrain). Проверить, не нарушает ли этот выбор ограничения задачи, учитывая уже сделанные ранее выборы. Если нарушает — этот вариант сразу отбрасывается, к нему не применяется рекурсия.
  3. Рекурсия (explore). Если выбор допустим, зафиксировать его как часть текущего частичного решения и рекурсивно вызвать ту же функцию для следующего шага построения.
  4. Откат (unchoose / backtrack). После того как рекурсивный вызов вернул управление — независимо от того, нашёл он полное решение или упёрся в тупик, — отменить сделанный на шаге 1 выбор, вернув состояние к тому виду, в котором оно было до этого шага, и перейти к следующему доступному варианту на шаге 1.

На псевдокоде это записывается универсально для огромного класса задач:

def backtrack(state, choices_made):
    if is_complete(state):
        record_solution(state)
        return

    for choice in get_candidates(state):       # 1. выбор
        if is_valid(state, choice):             # 2. проверка ограничений
            apply(state, choice)                 # фиксируем выбор
            backtrack(state, choices_made + 1)   # 3. рекурсия
            undo(state, choice)                  # 4. откат

Именно эту четырёхшаговую структуру — выбор, проверка, рекурсия, откат — ты увидишь дальше в этом уроке буквально в каждом примере, от расстановки ферзей до заполнения судоку, лишь с разным содержанием функций get_candidates, is_valid, apply и undo.

Разбор примеров

Пример 1 (генерация валидных скобочных последовательностей). Задача: сгенерировать все правильные последовательности из $n$ пар круглых скобок. Для $n=2$ правильными являются (()) и ()(), а )(( — нет. «Выбор» здесь — поставить ( или ) следующим символом; «ограничение» — нельзя поставить ), если открывающих скобок среди уже поставленных не больше, чем закрывающих, и нельзя поставить (, если открывающих уже поставлено $n$.

def generate_parentheses(n):
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(''.join(current))
            return
        if open_count < n:                       # ограничение: не более n открывающих
            current.append('(')
            backtrack(current, open_count + 1, close_count)
            current.pop()                          # откат
        if close_count < open_count:              # ограничение: закрывающих не больше открывающих
            current.append(')')
            backtrack(current, open_count, close_count + 1)
            current.pop()                          # откат

    backtrack([], 0, 0)
    return result

Трассировка для $n=2$: старт [], open=0, close=0. Выбор ( → ['('], open=1. Из этого состояния снова выбор ( (так как $1<2$) → ['(','('], open=2; теперь ( больше нельзя (достигли $n=2$), пробуем ) (так как $0<2$) → ['(','(',')'], close=1; снова ) (так как $1<2$) → ['(','(',')',')'] — длина $4=2n$, записываем (()). Откат до ['(','('], вариантов кроме ) не было — откат дальше до ['(']. Теперь из ['('] (open=1, close=0) пробуем ветку ) (так как $0<1$) → ['(',')'], close=1. Из неё снова ( (так как $1<2$) → ['(',')','('], open=2; затем только ) (так как $1<2$) → ['(',')','(',')'] — длина $4$, записываем ()(). Итого получены обе правильные последовательности, и ни одна ветка не выходила за пределы допустимых состояний, потому что ограничение проверялось на каждом отдельном символе, а не в конце.

Пример 2 (буквенные комбинации телефонного номера). Классическая задача: каждой цифре телефонной кнопки соответствует несколько букв (как на старых кнопочных телефонах: 2→"abc", 3→"def"), и нужно сгенерировать все возможные строки букв для заданной последовательности цифр, например "23".

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
               "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    result = []
    current = []

    def backtrack(index):
        if index == len(digits):
            result.append(''.join(current))
            return
        for letter in mapping[digits[index]]:   # выбор буквы для текущей цифры
            current.append(letter)                # ограничений здесь нет — любая буква допустима
            backtrack(index + 1)                   # рекурсия к следующей цифре
            current.pop()                          # откат

    backtrack(0)
    return result

Для "23" дерево перебора: цифра 2 даёт три ветки — a, b, c. Из ветки a цифра 3 добавляет d, e, f, давая ad, ae, af; аналогично из b — bd, be, bf, из c — cd, ce, cf. Итого $3 \times 3 = 9$ комбинаций, и в этой задаче ограничений на промежуточных шагах фактически нет — она интересна именно как пример «чистого» декартова произведения, полученного тем же самым каркасом выбор-рекурсия-откат, что показывает: backtracking работает даже там, где нечего отсекать, просто вырождаясь в систематический перебор.

Пример 3 (combination sum — числа с повторением). Дан набор чисел $[2, 3, 6, 7]$ (числа можно использовать многократно), нужно найти все комбинации, сумма которых равна $7$. «Выбор» — очередное число из набора; «ограничение» — сумма не должна превышать цель, а чтобы не порождать перестановки одной и той же комбинации (например, [2,2,3] и [3,2,2] как разные результаты), выбор ограничивается индексами не меньше текущего.

def combination_sum(candidates, target):
    result = []
    current = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        if remaining < 0:
            return  # тупик — превысили цель
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, remaining - candidates[i])  # i, не i+1 — числа можно повторять
            current.pop()  # откат

    backtrack(0, target)
    return result

Трассировка: remaining=7, пробуем 2 → remaining=5 → снова 2 → remaining=3 → снова 2 → remaining=1 → снова 2 → remaining=-1<0, тупик, откат; пробуем 3 из позиции после 2 → remaining=-2<0, тупик, откат; ветка [2,2,2] исчерпана, откат до [2,2], пробуем 3 → remaining=0 — совпадение, записываем [2,2,3]; пробуем 6, 7 из этой позиции → remaining<0, тупик; откат до [2], пробуем 3 → remaining=2, пробуем 3 → remaining=-1<0 тупик; пробуем 6,7 → тупик; откат до [2], пробуем 6 → remaining=-1 тупик, пробуем 7 → remaining=-2 тупик; откат до [], пробуем 3 → remaining=4, пробуем 3 → remaining=1, дальше тупик; пробуем 6 → remaining=-2 тупик; откат до [3], пробуем 6 → remaining=-2 тупик, пробуем 7→remaining=-3 тупик; откат до [], пробуем 6→remaining=1, тупик на всех продолжениях; пробуем 7→remaining=0 — совпадение, записываем [7]. Итог: [[2,2,3],[7]].

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

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

Задача о N ферзях: полный разбор

Интуиция

Классическая задача о N ферзях: расставить $N$ ферзей на шахматной доске $N \times N$ так, чтобы ни один ферзь не бил другого — то есть никакие два ферзя не стоят на одной строке, одном столбце или одной диагонали (напомним, ферзь в шахматах ходит на любое число клеток по горизонтали, вертикали и диагонали). Это, пожалуй, самая известная иллюстрация backtracking во всей информатике — не в последнюю очередь потому, что на ней особенно наглядно видно, как отсечение ветвей превращает астрономическое число вариантов в практически посчитываемое.

Ключевое наблюдение, которое сразу резко сокращает пространство поиска: раз никакие два ферзя не могут стоять в одной строке, в каждой строке доски должен стоять ровно один ферзь. Это значит, что задачу можно решать построчно: для строки $0$ выбрать столбец, для строки $1$ выбрать столбец, и так далее, — и решение автоматически превращается в последовательность из $N$ выборов (по одному столбцу на строку), что идеально ложится на общий шаблон backtracking из предыдущего раздела.

Алгоритм

Backtracking-алгоритм для N ферзей:

  1. Обрабатывать доску строку за строкой, начиная со строки $0$.
  2. Для текущей строки перебрать все столбцы от $0$ до $N-1$ как кандидатов для размещения ферзя (это «выбор»).
  3. Для каждого кандидата-столбца проверить три ограничения: столбец ещё не занят ни одним ранее поставленным ферзём, восходящая диагональ (где $\text{строка} - \text{столбец} = \text{const}$) ещё не занята, нисходящая диагональ (где $\text{строка} + \text{столбец} = \text{const}$) ещё не занята.
  4. Если все три ограничения выполнены — поставить ферзя, рекурсивно перейти к следующей строке.
  5. Если строка равна $N$ (все строки обработаны) — зафиксировано полное решение.
  6. После возврата из рекурсии — снять ферзя с текущей клетки (откат) и попробовать следующий столбец в этой же строке.

Диагонали удобно отслеживать через два множества: значения $\text{row} - \text{col}$ (постоянны вдоль одной «восходящей» диагонали, идущей снизу-слева вверх-направо) и $\text{row} + \text{col}$ (постоянны вдоль одной «нисходящей» диагонали). Это позволяет проверять конфликт с любым из уже поставленных ферзей за $O(1)$, а не перебором всех предыдущих ферзей на каждом шаге:

def solve_n_queens(n):
    solutions = []
    cols = set()
    diag1 = set()   # row - col: постоянно вдоль одной диагонали
    diag2 = set()   # row + col: постоянно вдоль другой диагонали
    board = [-1] * n

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # ограничение нарушено — эта ветка сразу отбрасывается
            board[row] = col
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            backtrack(row + 1)

            cols.remove(col)          # откат
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return solutions

Разбор примеров

Пример 1 (полная трассировка для $N=4$). Доска $4\times4$, строки и столбцы нумеруются с $0$.

Строка $0$: пробуем столбец $0$. Множества пусты, ограничений нет — ставим, cols={0}, diag1={0}, diag2={0}.

Строка $1$: столбец $0$ занят (конфликт по столбцу) — пропуск. Столбец $1$: $\text{diag1}=1-1=0$ — уже в diag1 (конфликт по диагонали) — пропуск. Столбец $2$: $\text{diag1}=1-2=-1$, не в множестве; $\text{diag2}=1+2=3$, не в множестве — допустимо, ставим. cols={0,2}, diag1={0,-1}, diag2={0,3}.

Строка $2$: столбец $0$ занят — пропуск. Столбец $1$: $\text{diag1}=2-1=1$, свободно; $\text{diag2}=2+1=3$ — уже занято (конфликт с ферзём строки $1$) — пропуск. Столбец $2$ занят — пропуск. Столбец $3$: $\text{diag1}=2-3=-1$ — уже занято (конфликт с ферзём строки $1$) — пропуск. Ни один столбец не подошёл — тупик, откат в строку $1$.

Строка $1$, продолжаем перебор: столбец $3$: $\text{diag1}=1-3=-2$, свободно; $\text{diag2}=1+3=4$, свободно — допустимо, ставим вместо столбца $2$. cols={0,3}, diag1={0,-2}, diag2={0,4}.

Строка $2$: столбец $0$ занят — пропуск. Столбец $1$: $\text{diag1}=2-1=1$, свободно; $\text{diag2}=2+1=3$, свободно — допустимо, ставим. cols={0,3,1}, diag1={0,-2,1}, diag2={0,4,3}.

Строка $3$: столбец $0$ занят, столбец $1$ занят. Столбец $2$: $\text{diag1}=3-2=1$ — уже занято (конфликт с ферзём строки $2$) — пропуск. Столбец $3$ занят. Ни один столбец не подошёл — тупик, откат в строку $2$, где вариантов кроме столбца $1$ не было — откат в строку $1$, где вариантов кроме столбца $3$ не было — откат в строку $0$.

Строка $0$: пробуем столбец $1$ (аналогичным путём, который здесь для краткости не расписан подробно, отсечение работает симметрично) — эта ветка приводит к решению $[1, 3, 0, 2]$: ферзи стоят в столбцах $1, 3, 0, 2$ для строк $0, 1, 2, 3$ соответственно, и все три типа конфликтов действительно отсутствуют. Продолжая перебор столбца $0$ в строке $0$ дальше (столбцы $2$ и $3$), можно показать, что столбец $2$ по симметрии доски даёт второе решение $[2, 0, 3, 1]$, а столбец $3$ (зеркальное отражение неудачного столбца $0$) решений не даёт.

Итог: у задачи 4 ферзей ровно два решения — $[1,3,0,2]$ и $[2,0,3,1]$, и это хорошо известный, проверяемый факт.

Пример 2 (случаи без решений: $N=2$ и $N=3$). Для доски $2\times2$: строка $0$, столбец $0$ — ставим. Строка $1$: столбец $0$ занят; столбец $1$ — $\text{diag1}=1-1=0$, уже занято (диагональный конфликт с ферзём из $(0,0)$) — пропуск. Оба столбца отброшены — тупик, откат в строку $0$; столбец $1$ строки $0$ по симметрии тоже не даёт решения. Решений нет. Для доски $3\times3$ ситуация аналогична: любая расстановка первых двух ферзей на доске такого маленького размера неизбежно оставляет третью строку без единого допустимого столбца — это можно проверить полным перебором всех $3^3=27$ независимых размещений по столбцам, но backtracking обнаруживает это за считаные шаги, отсекая большинство веток уже на второй строке. Интересный факт: у задачи N ферзей решения существуют для любого $N \geq 4$, а вот $N=2$ и $N=3$ — единственные размеры доски (не считая тривиального и не совсем содержательного случая $N=1$), для которых решений не существует вовсе.

Пример 3 (масштаб задачи и роль отсечения для $N=8$ — классическая «задача восьми ферзей»). Если бы мы перебирали вообще все способы поставить $8$ ферзей на $64$ клетки без единого ограничения «по одному в строке», число вариантов было бы $\binom{64}{8} = 4\,426\,165\,368$ — свыше четырёх миллиардов. Уже наблюдение «по одному ферзю на строку» сокращает это до $8^8 = 16\,777\,216$ вариантов (каждая из $8$ строк независимо выбирает один из $8$ столбцов). Переформулировка задачи как поиска перестановки (по одному ферзю ещё и на столбец, то есть столбцы для восьми строк — это перестановка чисел от $0$ до $7$) сокращает пространство дальше — до $8! = 40\,320$ вариантов, которые нужно было бы проверить на диагональные конфликты, если бы мы просто перебирали все перестановки и проверяли каждую целиком в конце. Backtracking же с проверкой диагоналей на каждом шаге отсекает подавляющее большинство из этих $40\,320$ веток ещё до того, как они достроены хотя бы до половины доски, потому что диагональные конфликты в среднем возникают уже на третьей-четвёртой строке. Именно поэтому для $N=8$ backtracking находит все $92$ существующих решения (среди которых $12$ различаются с точностью до поворотов и отражений доски) за доли секунды на обычном ноутбуке — при том что полный перебор всех $4.4$ миллиарда изначальных размещений на той же машине занял бы часы.

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

Задача о N ферзях — это не просто эффектная головоломка для демонстрации на лекциях: она компактно показывает всё, ради чего вообще стоит изучать backtracking. Пространство поиска растёт формально экспоненциально — $O(N!)$ в терминах числа перестановок, которые в принципе нужно было бы рассмотреть, — и никакая хитрость не устраняет эту границу асимптотически: для достаточно большого $N$ backtracking тоже станет практически неприменим. Но диапазон значений $N$, для которых задача решается за разумное время, у backtracking на порядки шире, чем у наивного перебора, именно благодаря тому, что конфликт по столбцу или диагонали обнаруживается сразу после размещения очередного ферзя, а не после того, как все восемь (или сто восемь) ферзей уже расставлены. Тот же самый принцип — обнаруживать нарушение ограничения максимально рано, чтобы не тратить ресурсы на заведомо неверное продолжение, — лежит в основе того, зачем в промышленных SAT-решателях и планировщиках вообще используют backtracking с продвинутыми эвристиками отсечения, а не грубый перебор.

Генерация перестановок, подмножеств и судоку как задачи удовлетворения ограничений

Интуиция

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

Алгоритм

Backtracking для перестановок:

  1. Завести массив-флаг «использован» для каждого элемента исходного набора.
  2. Если текущая частичная перестановка уже содержит все элементы — зафиксировать её как готовый результат.
  3. Иначе перебрать все ещё не использованные элементы как кандидатов для очередной позиции.
  4. Для каждого кандидата — пометить его использованным, добавить в текущую перестановку, рекурсивно продолжить для следующей позиции.
  5. После возврата из рекурсии — убрать элемент из текущей перестановки и снять пометку «использован» (откат).

Backtracking для подмножеств:

  1. На каждом шаге рекурсии текущий накопленный набор уже является одним из допустимых подмножеств — сразу зафиксировать его как результат (никаких ограничений на «допустимость» нет).
  2. Перебрать оставшиеся ещё не рассмотренные элементы исходного массива, начиная с некоторого индекса start.
  3. Для каждого элемента — добавить его в текущий набор, рекурсивно вызвать продолжение с индексом start+1 (или больше — в зависимости от позиции взятого элемента), чтобы не порождать перестановки одного и того же подмножества.
  4. После возврата — убрать элемент из текущего набора (откат) и перейти к следующему индексу.

Backtracking для судоку:

  1. Найти первую (в порядке обхода строк и столбцов) пустую клетку. Если пустых клеток не осталось — доска полностью и корректно заполнена, решение найдено.
  2. Перебрать цифры от $1$ до $9$ как кандидатов для этой клетки.
  3. Для каждой цифры проверить три ограничения одновременно: цифра ещё не встречается в этой строке, ещё не встречается в этом столбце, ещё не встречается в блоке $3\times3$, которому принадлежит клетка.
  4. Если все три ограничения выполнены — записать цифру в клетку и рекурсивно перейти к решению доски с этой заполненной клеткой.
  5. Если рекурсивный вызов не нашёл решения дальше по дереву — стереть цифру из клетки (откат) и попробовать следующую цифру-кандидата.
  6. Если ни одна из девяти цифр не подошла — сообщить о тупике, чтобы вызывающий уровень рекурсии откатил свой выбор.

Разбор примеров

Пример 1 (перестановки трёх элементов с полной трассировкой). Массив [1, 2, 3].

def permutations(arr):
    result = []
    used = [False] * len(arr)
    current = []

    def backtrack():
        if len(current) == len(arr):
            result.append(current[:])
            return
        for i in range(len(arr)):
            if used[i]:
                continue
            used[i] = True
            current.append(arr[i])
            backtrack()
            current.pop()      # откат
            used[i] = False    # откат

    backtrack()
    return result

Трассировка: current=[]. Берём 1 (индекс $0$) → current=[1], used=[T,F,F]. Из [1] берём 2 → current=[1,2]. Из [1,2] берём 3 (единственный неиспользованный) → current=[1,2,3], длина $3$ — записываем [1,2,3]. Откат до [1,2], других вариантов нет — откат до [1]. Из [1] берём 3 (индекс $2$) → current=[1,3]. Из [1,3] берём 2 → current=[1,3,2], длина $3$ — записываем [1,3,2]. Откат до [1], элементы $2$ и $3$ уже перебраны — откат до []. Далее аналогично для стартового элемента 2: получаем [2,1,3] и [2,3,1]; для стартового элемента 3: [3,1,2] и [3,2,1]. Итог: все $3! = 6$ перестановок — [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

Пример 2 (подмножества массива из двух элементов с полной трассировкой). Массив [1, 2].

def subsets(arr):
    result = []
    current = []

    def backtrack(start):
        result.append(current[:])   # фиксируем текущий набор сразу, без ограничений
        for i in range(start, len(arr)):
            current.append(arr[i])
            backtrack(i + 1)
            current.pop()           # откат

    backtrack(0)
    return result

Трассировка: вызов backtrack(0) сразу записывает current=[] → результат содержит []. Цикл: i=0 (значение 1) → current=[1] → вызов backtrack(1) сразу записывает [1]. Внутри: i=1 (значение 2) → current=[1,2] → вызов backtrack(2) записывает [1,2], цикл внутри пуст (индексы кончились) — возврат. Откат: current возвращается к [1]. Возврат из backtrack(1) — откат current к []. Продолжаем цикл в backtrack(0): i=1 (значение 2) → current=[2] → вызов backtrack(2) записывает [2], цикл пуст — возврат, откат к []. Итог: все $2^2=4$ подмножества — [], [1], [1,2], [2] — обрати внимание, что здесь backtracking не столько «отсекает» ветви, сколько систематически перечисляет их все, ведь у задачи «сгенерировать все подмножества» попросту нет содержательных ограничений, которые можно было бы нарушить.

Пример 3 (мини-судоку $4\times4$ — иллюстрация отката при конфликте). Возьмём упрощённую версию судоku на сетке $4\times4$ с блоками $2\times2$ и цифрами от $1$ до $4$ вместо стандартных $9\times9$ — принцип идентичен, но трассировку можно провести полностью. Пусть первая строка уже заполнена как 1 2 . ., вторая строка пуста, и мы решаем, что поставить в клетку $(1,0)$ (первая пустая клетка при обходе слева направо, сверху вниз).

def solve_sudoku(board, size=4, block=2):
    empty = find_empty(board)
    if not empty:
        return True  # пустых клеток не осталось — решение найдено
    row, col = empty
    for digit in range(1, size + 1):
        if is_valid(board, row, col, digit, block):
            board[row][col] = digit
            if solve_sudoku(board, size, block):
                return True
            board[row][col] = 0  # откат — цифра не привела к решению дальше
    return False  # ни одна цифра не подошла — сигнал тупика наверх

Для клетки $(1,0)$: пробуем цифру $1$ — уже есть в столбце $0$ (клетка $(0,0)=1$) — конфликт по столбцу, пропуск. Пробуем $2$ — уже есть в блоке $2\times2$ левого верхнего угла (клетка $(0,1)=2$ входит в тот же блок) — конфликт по блоку, пропуск. Пробуем $3$ — не встречается ни в строке $1$ (она пока пуста), ни в столбце $0$ (там только $1$), ни в блоке (там $1$ и $2$) — допустимо, ставим $3$ в $(1,0)$ и рекурсивно переходим к следующей пустой клетке. Если бы на каком-то более глубоком уровне рекурсии выяснилось, что при $3$ в клетке $(1,0)$ доска неразрешима (например, для клетки $(1,1)$ не осталось бы ни одной допустимой цифры), функция вернула бы False, и внешний вызов стёр бы тройку из $(1,0)$ (строка board[row][col] = 0) и попробовал бы следующую цифру-кандидата — в данном случае $4$ — прежде чем сдаться и сообщить о тупике ещё выше по дереву рекурсии.

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

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

Здесь же стоит честно провести мостик к машинному обучению, ради которого ты, скорее всего, и проходишь этот курс. Судоку и раскраска графа — учебные, но абсолютно точные примеры задачи удовлетворения ограничений (constraint satisfaction problem), а CSP регулярно всплывает в инженерии ML-систем не как теоретическая экзотика, а как рабочий инструмент: например, при автоматизированном подборе гиперпараметров модели (auto-ML, hyperparameter tuning) часто существуют жёсткие ограничения совместимости — определённый оптимизатор несовместим с определённым типом слоя, определённый размер батча требует минимального объёма видеопамяти при заданной архитектуре, конкретная комбинация нормализации и функции активации даёт NaN в градиентах, — и полный перебор всех комбинаций гиперпараметров с последующей фильтрацией по этим правилам расточителен ровно по той же причине, по которой расточителен полный перебор в задаче о ферзях: подавляющее большинство комбинаций отсекается уже на первых двух-трёх выбранных значениях, и backtracking-подобная логика (попробовать значение → сразу проверить совместимость с уже выбранными → при конфликте отступить и попробовать другое) экономит вычислительный бюджет тем же самым способом, что и в шахматной задаче. А сама идея «пробуем — если результат неудовлетворителен, откатываемся к более раннему состоянию» концептуально перекликается с early stopping при обучении нейросети (откат к весам с лучшей метрикой на валидации, если дальнейшее обучение начало ухудшать результат) и с поиском по дереву решений в некоторых алгоритмах планирования и игровых ИИ (например, в поиске по дереву игры с отсечением заведомо проигрышных ветвей, родственном идее alpha-beta pruning) — это не строгая математическая эквивалентность, а именно содержательная параллель в самой стратегии «пробуй, проверяй, отступай при необходимости», которая стоит того, чтобы держать её в голове при проектировании собственных пайплайнов поиска.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Трассировать backtracking для subset-sum на массиве [2, 3, 5] с целью 5: перечислить все найденные подмножества и явно указать, на каком шаге происходит откат.

Задание 2: Объяснить своими словами, в чём отличие backtracking от полного перебора (перечисления всех вариантов с проверкой в конце), на примере генерации перестановок трёх элементов.

Задание 3: Записать общий шаблон backtracking-функции (выбор → проверка ограничений → рекурсия → откат) в виде псевдокода для абстрактной задачи.

Задание 4: Сколько всего перестановок у массива [1, 2, 3]? Перечислить их все в том порядке, в котором backtracking из примера этого урока найдёт их.

Задание 5: Сколько существует решений задачи о расстановке 4 ферзей на доске $4\times4$?

Задание 6: Объяснить, почему решение судоку через backtracking — это частный случай задачи удовлетворения ограничений (constraint satisfaction problem, CSP).

Задание 7: Что произойдёт, если в функции генерации подмножеств забыть строку current.pop() после рекурсивного вызова? Привести пример поломки на массиве [1, 2].

Задание 8: Реализовать backtracking-генератор всех подмножеств массива [1, 2] и явно перечислить результат.

Задание 9: Оценить (по порядку величины) число вершин дерева перебора для полного перебора всех расстановок 5 ферзей на доске $5\times5$ без каких-либо ограничений, кроме «по одному ферзю в строке».

Задание 10: Что означает «тупик» (dead end) в контексте backtracking? Привести пример на маленьком лабиринте $2\times2$, где путь из левого верхнего угла в правый нижний невозможен.

Средние задания (11–20)

Задание 11: Реализовать backtracking для генерации всех валидных комбинаций из $n=2$ пар скобок.

Задание 12: Трассировать backtracking для $N=3$ ферзей и объяснить, почему решений нет.

Задание 13: Реализовать combination sum: найти все комбинации чисел из [2, 3, 6, 7] (числа можно повторять), сумма которых равна $7$.

Задание 14: Оценить сложность полного перебора для задачи о N ферзях без учёта ограничения «по одному в столбце» при $N=8$ и сравнить с числом перестановок $8!$.

Задание 15: Реализовать функцию is_valid(row, col, cols, diag1, diag2) для проверки, можно ли поставить ферзя в клетку (row, col) при уже занятых множествах столбцов и диагоналей.

Задание 16: Написать backtracking-функцию для генерации перестановок массива с повторяющимися элементами без дублей в результате, например для [1, 1, 2].

Задание 17: Объяснить, какие три вида ограничений (строка, столбец, блок $3\times3$) проверяются при каждой попытке поставить цифру в судоку, и почему все три обязательны одновременно.

Задание 18: Реализовать поиск слова в сетке букв (word search) через backtracking с обходом соседних клеток по горизонтали и вертикали.

Задание 19: Оценить (без полной трассировки, по аналогии с $N=4$) количество решений задачи о N ферзях для $N=6$.

Задание 20: Объяснить, зачем в реализации N-ферзей использовать множества (set) для столбцов и диагоналей вместо цикла по уже поставленным ферзям при каждой проверке.

Продвинутые задания (21–30)

Задание 21: Описать план реализации полного backtracking-решателя судоку $9\times9$, включая ключевые вспомогательные функции.

Задание 22: Реализовать генерацию всех подмножеств массива [3, 1, 4, 2] с суммой ровно 5, с ранним отсечением, когда текущая частичная сумма уже превышает цель.

Задание 23: Реализовать раскраску графа (graph coloring) через backtracking: дан граф в виде списка смежности и число цветов $m$, найти допустимую раскраску вершин, при которой соседние вершины не совпадают по цвету.

Задание 24: Оценить, во сколько раз сокращается пространство поиска для 8 ферзей за счёт формулировки задачи как перестановки ($8!$) по сравнению с наивным перебором всех расстановок 8 ферзей на 64 клетках без единого ограничения ($\binom{64}{8}$).

Задание 25: Реализовать поиск пути в лабиринте через backtracking с возможностью двигаться в четырёх направлениях (не только вправо и вниз) и с откатом при тупике.

Задание 26: Привести конкретный пример того, как backtracking-подобная логика применяется в задаче подбора гиперпараметров с жёсткими ограничениями совместимости в машинном обучении.

Задание 27: Реализовать генерацию перестановок массива, в которых ни один элемент не стоит на своей исходной позиции (derangements), через backtracking.

Задание 28: Реализовать N-ферзей с ранним прекращением поиска сразу после нахождения первого решения, в отличие от поиска всех решений, — показать разницу в коде.

Задание 29: Сравнить теоретическую верхнюю границу сложности backtracking для задачи о N ферзях в худшем случае ($O(N!)$ или $O(N^N)$) с фактической производительностью алгоритма на практике благодаря отсечению. Объяснить, почему это не противоречие.

Задание 30: Спроектировать backtracking-решение для задачи «обход конём» (Knight's Tour) — обойти конём все клетки доски $N\times N$ без повторов, — описав план и ключевые функции без полной реализации.

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

Ошибка 1. Забывают откатить состояние после рекурсивного вызова, из-за чего изменения одной ветки «просачиваются» в другие ветки перебора.

Как выглядит: код добавляет элемент в общий изменяемый список или множество перед рекурсией, но не убирает его после возврата из рекурсивного вызова — строка undo или pop() попросту отсутствует.

Почему возникает: легко сосредоточиться на «прямом» пути — сделать выбор и пойти вглубь рекурсии, — и упустить из виду, что после возврата состояние нужно вернуть точно в то же состояние, в котором оно было до выбора, иначе следующая итерация цикла в этом же вызове будет работать с уже испорченными данными.

Как правильно: на каждое изменение общего состояния перед рекурсивным вызовом (append, add, присваивание в ячейку) должна приходиться ровно одна отменяющая операция (pop, remove, сброс значения) сразу после возврата из этого рекурсивного вызова — правило «что взял, то и положи обратно» должно выполняться без исключений.

Ошибка 2. Путают backtracking с обычной рекурсией без отслеживания и отмены состояния, из-за чего алгоритм превращается в скрытый полный перебор без единого реального отсечения.

Как выглядит: функция действительно рекурсивно перебирает варианты, но проверка ограничений выполняется только в самом конце, когда решение уже полностью построено, а не на каждом промежуточном шаге.

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

Как правильно: всегда стараться перенести проверку ограничения как можно раньше — сразу после того, как сделан минимально достаточный для этой проверки выбор, а не после полной достройки решения; для судоку это означает проверку цифры сразу при её постановке, а не после заполнения всей доски.

Ошибка 3. Копируют изменяемый объект (список, множество) по ссылке вместо значения при сохранении найденного решения, из-за чего все сохранённые «решения» на самом деле указывают на один и тот же объект и искажаются последующими откатами.

Как выглядит: строка result.append(current) вместо result.append(current[:]) (или list(current)) — в result попадает ссылка на тот же самый список current, который backtracking продолжает изменять дальше.

Почему возникает: в языках вроде Python списки и множества передаются и сохраняются по ссылке, и на маленьких примерах, где отладка останавливается сразу после первого найденного решения, ошибка незаметна — искажение проявляется только тогда, когда после сохранения «решения» алгоритм продолжает работу и меняет тот же объект дальше.

Как правильно: всегда сохранять копию текущего состояния (current[:], list(current), current.copy()), а не ссылку на изменяемый объект, который backtracking продолжит модифицировать после сохранения.

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

Как выглядит: для проверки конфликта нового ферзя с уже поставленными в N-ферзях пишут цикл for existing_queen in placed_queens: if conflicts(new, existing_queen): ... вместо проверки принадлежности множествам cols, diag1, diag2.

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

Как правильно: заранее продумать, какую вспомогательную структуру данных (множество, массив-флаг, счётчик) можно поддерживать инкрементально при выборе и откате, чтобы сводить проверку ограничения к $O(1)$ или хотя бы к малой константе, а не к перебору всей истории выборов.

Ошибка 5. Не предусматривают ранний выход после нахождения одного решения там, где по условию задачи нужно только одно решение, из-за чего алгоритм продолжает бесполезно перебирать оставшиеся ветки дерева до конца.

Как выглядит: функция ищет только один ответ (например, «существует ли решение судоку») но возвращает None или продолжает цикл вместо немедленного return True при первом найденном полном решении.

Почему возникает: шаблон «перебрать все решения и сложить их в список» настолько привычен, что его иногда копируют бездумно даже туда, где на самом деле нужен только факт существования решения или само первое найденное решение.

Как правильно: если задача требует лишь одно решение или ответ на вопрос «существует ли решение вообще», рекурсивная функция должна возвращать булево значение и немедленно прекращать дальнейший перебор (return True) при первом успехе, как показано в задании 28 этого урока, — это может на порядки сократить время работы по сравнению с полным перебором всех решений.

Главное запомнить

  • Backtracking — поиск с возвратом: решение строится последовательностью шагов, а ограничения проверяются на каждом промежуточном шаге, а не только на полностью построенном решении.

  • Главное отличие от простого полного перебора — ранняя проверка ограничений позволяет отсечь целые поддеревья заведомо неверных продолжений, ни разу не заходя в них, что резко сокращает практическое время работы, не меняя теоретическую верхнюю границу.

  • Общий шаблон backtracking состоит из четырёх шагов: выбор кандидата, проверка ограничений (is_valid), рекурсивный вызов вглубь, и обязательный откат состояния после возврата из рекурсии.

  • В задаче о N ферзях наблюдение «по одному ферзю в строке» сводит задачу к последовательности из $N$ выборов столбца, а проверка столбцов и диагоналей через множества позволяет отсекать конфликты за $O(1)$ на каждом шаге.

  • Для $N=4$ существует $2$ решения, для $N=6$ — $4$, для $N=8$ — $92$; для $N=2$ и $N=3$ решений не существует вовсе — эти конкретные числа стоит держать в голове как проверочные примеры.

  • Генерация перестановок, генерация подмножеств и решение судоку — три архетипа одного и того же каркаса backtracking: с одним ограничением (не повторяй элемент), вовсе без содержательных ограничений (любое частичное подмножество допустимо) и с несколькими одновременными ограничениями (строка, столбец, блок) соответственно.

  • Сложность backtracking в худшем случае остаётся экспоненциальной ($O(N!)$ или $O(k^n)$ в зависимости от задачи) — отсечение ветвей ускоряет практику, но не меняет теоретическую асимптотическую верхнюю границу.

  • Если задаче нужно только одно решение (или ответ «существует ли решение»), рекурсивную функцию стоит писать так, чтобы она немедленно прекращала перебор при первом успехе, а не продолжала искать все решения без необходимости.

  • Backtracking концептуально — прямой алгоритмический ответ на задачи удовлетворения ограничений (CSP), и это же общее понятие «пробуй — проверяй — при конфликте откатывайся» встречается далеко за пределами головоломок, включая инженерию ML-систем.

Связь с темами курса

Что нужно было знать до этого урока

Backtracking напрямую опирается на рекурсию и стратегию «разделяй и властвуй» из предыдущего урока 272 — в обоих случаях задача решается через рекурсивные вызовы на «уменьшенной» версии себя, только в D&C подзадачи решаются независимо и объединяются, а в backtracking подзадачи явно зависят от уже сделанных ранее выборов и могут быть отменены. Понимание того, как устроен стек вызовов рекурсии (из более ранних уроков блока алгоритмов) важно и здесь: каждый уровень рекурсии в backtracking хранит своё собственное состояние выбора, и откат — это буквально возврат на предыдущий кадр этого стека.

Что изучить дальше

Следующий урок 274 переходит к алгоритмам на строках — задачам поиска подстрок, сравнения последовательностей и обработки текста, где рекурсивные и динамические техники, включая идеи, близкие к backtracking (например, при сопоставлении с шаблоном или регулярными выражениями), снова оказываются рабочим инструментом, но уже в контексте другого типа данных.

Где это нужно в жизни

🤖 ML/AI и инженерия систем. Подбор гиперпараметров с жёсткими ограничениями совместимости (auto-ML, hyperparameter tuning) — прямой аналог задачи удовлетворения ограничений: пробуем комбинацию, проверяем совместимость, при конфликте откатываемся и пробуем другую, вместо перебора всех комбинаций с фильтрацией в конце. Идея «попробовать — если не получилось, откатиться» также концептуально перекликается с early stopping при обучении моделей (возврат к весам с лучшей метрикой на валидации) и с поиском по дереву решений в некоторых алгоритмах планирования и игровых ИИ.

🧩 Логическое программирование и SAT-решатели. Язык Prolog и современные SAT/SMT-решатели, широко используемые в формальной верификации и планировании, в своей основе опираются на backtracking с продвинутыми эвристиками выбора переменной и порядка перебора значений — это прямое промышленное развитие идей, разобранных в этом уроке.

🗺️ Планирование и робототехника. Поиск маршрута с ограничениями (например, обход препятствий, планирование последовательности задач при ограниченных ресурсах) во многих практических системах реализуется именно через backtracking-подобный поиск по дереву вариантов с отсечением недопустимых веток.

🔐 Криптография и комбинаторная оптимизация. Классические задачи вроде судоку, N ферзей, раскраски графов — не только учебные примеры, но и упрощённые модели куда более практических задач планирования расписаний, распределения ресурсов и проверки выполнимости логических формул (SAT), где та же самая стратегия «выбор → проверка → откат» масштабируется до промышленных решателей.

Интересные факты

  • Термин «backtracking» ввёл математик Д. Х. Лемер в 1950-х годах для задач перечисления комбинаторных объектов, а строгую теоретическую формализацию как метода моделирования «недетерминированных» вычислений дал в 1967 году Роберт Флойд — тот самый, в честь которого назван алгоритм Флойда — Уоршелла для поиска кратчайших путей во всех парах вершин графа.

  • Задача о восьми ферзях была впервые поставлена в 1848 году немецким шахматным композитором Максом Беззелем, а знаменитый математик Карл Гаусс заинтересовался ею и попытался найти все решения вручную — по легенде, изначально он нашёл не все $92$ решения, что для человека без компьютера совершенно объяснимо, учитывая, что даже перебор всех $4.4$ миллиарда изначальных размещений вручную немыслим.

  • Язык программирования Prolog, разработанный в начале 1970-х годов, целиком построен вокруг backtracking: когда программа на Prolog «доказывает» логическое утверждение, интерпретатор перебирает применимые правила и автоматически откатывается назад к последней точке выбора при неудаче — ровно тот же механизм, что и в задаче о ферзях, только применённый к логическому выводу, а не к шахматной доске.

  • Число решений задачи о N ферзях растёт очень неравномерно с увеличением $N$: $N=4 \to 2$, $N=5 \to 10$, $N=6 \to 4$ (заметное падение!), $N=7 \to 40$, $N=8 \to 92$ — и до сих пор не существует простой замкнутой формулы, которая предсказывала бы точное число решений для произвольного $N$ без непосредственного вычисления.

Лайфхаки

  • Прежде чем писать код, явно сформулируй для своей задачи четыре вещи: что такое «частичное решение», что является «выбором» на очередном шаге, какое условие делает выбор «допустимым» и какое условие означает «решение полностью построено» — как только эти четыре ответа есть, тело функции backtrack почти пишется само по общему шаблону этого урока.

  • Переноси проверку ограничений максимально рано — сразу после минимально достаточного для этой проверки частичного выбора, а не в конец, когда решение уже полностью построено; именно в этом сдвиге проверки на более ранний шаг и заключается всё практическое ускорение backtracking по сравнению с полным перебором.

  • Для проверки ограничений, которые сравнивают новый выбор со всеми уже сделанными (конфликт по столбцу, диагонали, цвету, цифре), заранее продумай вспомогательную структуру данных (set, массив-флаг, счётчик), поддерживаемую инкрементально при выборе и откате, — это превращает проверку из $O(k)$ в $O(1)$ и экономит время на каждом из экспоненциально многих узлов дерева перебора.

  • Всегда явно проверяй парность операций «изменить состояние перед рекурсией» и «отменить изменение после возврата из рекурсии» — на каждый append/add/присваивание перед рекурсивным вызовом должен приходиться ровно один pop/remove/сброс сразу после него, без исключений и без забытых веток.

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

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

  • Если backtracking работает заметно медленнее, чем ожидалось, в первую очередь проверь порядок перебора кандидатов и то, насколько рано срабатывает отсечение: часто простая перестановка порядка проверки ограничений (сначала самое строгое и самое дешёвое в вычислении ограничение) резко сокращает число реально посещённых узлов дерева поиска без каких-либо изменений в самой логике алгоритма.

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

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!