Алгоритм Backtracking на Python: Создаем автоматический решатель Судоку

Решение головоломки Судоку вручную требует от человека концентрации, логики и много времени. Однако с точки зрения компьютерных наук эту задачу можно решить с помощью элегантного и лаконичного алгоритма. В обучающем видео от популярного IT-канала Computerphile ведущий демонстрирует, как написать полноценный автоматический решатель Судоку на языке Python, используя фундаментальный метод поиска с возвратом (backtracking).

🧩 Что такое судоку с точки зрения Computer Science 0:00

Судоку — это классическая математическая головоломка, состоящая из игрового поля размером 9x9 клеток . Это поле, в свою очередь, разделено на девять меньших квадратов размером 3x3 клетки . Цель игры предельно проста: заполнить все пустые клетки цифрами от 1 до 9 так, чтобы ни одно число не повторялось в пределах одной строки, одного столбца и одного малого квадрата 3x3 .

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

🔄 Алгоритм Backtracking: Магия поиска с возвратом 1:29

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

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

Тупик: на очередном шаге ни одно число от 1 до 9 не может быть вставлено в клетку без нарушения правил .
Успех: все клетки успешно заполнены, и решение найдено.

Если алгоритм заходит в тупик, активируется механизм «возврата» (backtrack) . Программа возвращается к предыдущему шагу, стирает ранее записанное число (сбрасывает значение клетки в ноль) и пробует вставить следующий по порядку вариант . Этот процесс визуально напоминает обход лабиринта: если вы уперлись в стену, вы возвращаетесь к последней развилке и пробуете другой путь. Благодаря рекурсивной природе Python, такая сложная логика реализуется удивительно просто.

🛠️ Подготовка данных и функция проверки правил 1:41

Перед тем как приступить к написанию основного решателя, необходимо представить игровое поле в виде структуры данных Python и создать функцию для проверки правил игры.

Игровое поле представляется в виде двумерного списка (матрицы) размером 9x9 . Пустые клетки обозначаются нулями:

grid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    ...
]

Для проверки возможности размещения числа n в позиции с координатами (y, x) создается вспомогательная функция possible(y, x, n) . Функция принимает три параметра: координату строки y, координату столбца x и проверяемое число n . Она должна возвращать True, если число можно поставить в эту клетку, и False в противном случае .

Проверка состоит из трех этапов:

Проверка строки: алгоритм проходит по всем элементам строки y и проверяет, нет ли там уже числа n .
Проверка столбца: аналогично проверяется весь столбец x .
Проверка малого квадрата 3x3: этот этап требует математического вычисления координат левого верхнего угла текущего малого квадрата . Координаты вычисляются по формулам `x0 = (x // 3)
3иy0 = (y // 3)
3` . Затем программа проверяет все 9 клеток этого сектора.

Если ни в строке, ни в столбце, ни в локальном квадрате число n не обнаружено, функция возвращает True .

💻 Рекурсивный решатель: Реализация функции `solve()` 3:45

Основная магия алгоритма сосредоточена в функции solve(), которая не принимает внешних параметров и работает напрямую с глобальной матрицей grid .

Работа функции строится по следующему шаблону:

Поиск пустой клетки: с помощью вложенных циклов по y и x (в диапазоне от 0 до 8) программа ищет клетку со значением 0 .
Перебор вариантов: обнаружив пустую клетку, алгоритм запускает цикл for n in range(1, 10), пытаясь примерить цифры от 1 до 9 .
Рекурсивный вызов: если possible(y, x, n) возвращает True, программа временно записывает это число в сетку (grid[y][x] = n) и рекурсивно вызывает саму себя — solve() .
Откат (Backtracking): если последующие рекурсивные вызовы завели в тупик, программа сбрасывает значение текущей клетки обратно в ноль (grid[y][x] = 0) и продолжает цикл перебора чисел .

Если программа просмотрела всю сетку и не нашла ни одного нуля, это означает, что головоломка успешно решена . В этот момент программа выводит заполненную матрицу на экран .

🚀 Демонстрация работы и поиск нескольких решений 7:40

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

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

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