# Как написать решатель Судоку на Python: разбираем алгоритм Backtracking с Computerphile Источник: https://www.youtube.com/watch?v=G_UYXzGuqvM Канал: Computerphile Опубликовано: 12.02.2020 --- Судоку — одна из самых популярных головоломок в мире, но для программиста это прежде всего классическая задача на построение эффективного алгоритма. В видеоролике на канале Computerphile ведущий демонстрирует, как с помощью языка Python и концепции поиска с возвратом (backtracking) написать лаконичный решатель Судоку всего в несколько десятков строк кода. Этот подход наглядно иллюстрирует силу рекурсии и системного перебора вариантов в компьютерных науках. ## 🧩 Суть головоломки Судоку и концепция Backtracking [[JUMP:00:00]] Игровое поле Судоку представляет собой сетку размером 9x9 клеток, которая также разделена на девять меньших квадратов размером 3x3 [00:29]. Задача игрока — заполнить пустые ячейки цифрами от 1 до 9 так, чтобы выполнялись три жестких правила: * Каждая цифра от 1 до 9 должна встречаться в каждой строке ровно один раз. * Каждая цифра от 1 до 9 должна встречаться в каждом столбце ровно один раз. * Каждая цифра от 1 до 9 должна встречаться в каждом из девяти малых квадратов 3x3 ровно один раз [00:45]. Для автоматического решения такой задачи программисты используют метод под названием backtracking (поиск с возвратом) [01:29]. Как объясняет ведущий канала Computerphile, этот алгоритм работает по принципу проб и ошибок. Он пытается поставить число в пустую клетку и, если это не нарушает правила, переходит к следующей клетке. Если же в процессе заполнения сетки алгоритм заходит в тупик (когда для очередной пустой клетки нет ни одного подходящего числа), он делает шаг назад, отменяет последнее действие и пробует другой вариант [01:29]. ## 🛠️ Подготовка данных: Представление сетки в Python [[JUMP:01:29]] Для реализации алгоритма в Python необходимо правильно представить игровое поле. Ведущий использует двумерный список (матрицу) размером 9x9, где заполненные клетки содержат соответствующие числа, а пустые ячейки обозначены нулями [01:56]. Такое представление позволяет легко обращаться к элементам по индексам строк и столбцов. Вся работа программы будет происходить непосредственно с этой глобальной переменной `grid`, что избавляет от необходимости постоянно передавать копии игрового поля между функциями [03:45]. ## 🔍 Функция проверки ограничений: Метод `possible` [[JUMP:02:32]] Прежде чем приступать к написанию основного решателя, необходимо создать вспомогательную функцию проверки. Автор видео объявляет функцию `possible(y, x, n)`, которая принимает три параметра: координату строки `y`, координату столбца `x` и число `n`, которое мы хотим туда поместить [02:48]. Функция должна возвращать `True`, если число можно вставить в данную позицию, и `False` в противном случае. Для этого алгоритм поочередно проверяет три условия: 1. **Проверка строки:** программа итерируется по столбцам текущей строки `y` и проверяет, нет ли там уже числа `n` [03:01]. 2. **Проверка столбца:** программа итерируется по строкам текущего столбца `x` на предмет наличия числа `n` [03:01]. 3. **Проверка локального квадрата 3x3:** этот шаг требует простой математической операции. Чтобы найти левый верхний угол малого квадрата, в котором находится клетка `(y, x)`, автор использует целочисленное деление на 3 с последующим умножением на 3 [03:17]: * `x0 = (x // 3) * 3` * `y0 = (y // 3) * 3` После нахождения стартовой точки `(y0, x0)` алгоритм обходит все 9 ячеек малого квадрата с помощью вложенного цикла [03:17]. Если число `n` не обнаружено ни в строке, ни в столбце, ни в локальном квадрате, функция возвращает `True`. ## ⚙️ Сердце алгоритма: Рекурсивный поиск `solve` [[JUMP:03:45]] Главная функция `solve()` не принимает аргументов, так как работает напрямую с глобальной переменной сетки [03:45]. Внутри нее запускается двойной цикл для обхода всех 81 ячеек поля [03:58]: ```python for y in range(9): for x in range(9): ... ``` Когда алгоритм находит пустую клетку (содержащую `0`) [04:15], он пытается подобрать для нее подходящую цифру от 1 до 9. Для этого запускается цикл `for n in range(1, 10)` [04:33]: * Сначала вызывается функция `possible(y, x, n)` [05:06]. * Если число `n` подходит, оно временно записывается в ячейку: `grid[y][x] = n` [05:20]. * Затем функция `solve()` рекурсивно вызывает саму себя для поиска решения для оставшихся клеток [05:37]. * Если в какой-то момент последующие рекурсивные вызовы заходят в тупик, управление возвращается назад. В этот момент срабатывает механизм backtracking: программа сбрасывает значение ячейки обратно на ноль (`grid[y][x] = 0`) [05:56] и продолжает цикл, пытаясь примерить следующее число `n`. ## 🖨️ Вывод результатов и поиск нескольких решений [[JUMP:06:11]] Что происходит, когда алгоритм успешно заполняет всю сетку и на поле не остается нулей? В этот момент циклы поиска пустых клеток завершаются, и программа доходит до конца функции `solve()` [06:30]. Автор видео настраивает программу так, чтобы при успешном заполнении сетки она выводила текущее состояние поля на экран [06:57]. Однако на этом работа не заканчивается. Чтобы пользователь успел рассмотреть решение, ведущий использует стандартную команду `input()` [07:14]. Интересный побочный эффект такого решения заключается в том, что если пользователь нажмет клавишу Enter, программа продолжит выполнение [07:40]. Она отменит последнее успешное действие (снова сработает backtracking) и попытается найти *другие* возможные варианты решения головоломки. Для демонстрации этого эффекта ведущий удаляет часть подсказок из исходного Судоку [08:05]. В результате сетка теряет уникальность решения, и программа при каждом нажатии Enter мгновенно выдает новые и новые варианты правильного заполнения поля [08:30]. ## 🧠 Почему Backtracking идеален для простых задач [[JUMP:09:05]] В заключение ведущий канала Computerphile отмечает, что метод поиска с возвратом по своей сути является разновидностью поиска в глубину (Depth-First Search) [09:05]. Вся история ходов и возвратов автоматически управляется стеком вызовов самой среды Python [09:18]. Несмотря на то, что существуют более сложные и оптимизированные подходы (например, системы удовлетворения ограничений или алгоритмы на основе связей танцующих звеньев Дональда Кнута) [09:31], для стандартной сетки Судоку 9x9 обычного рекурсивного backtracking на Python более чем достаточно. Программа находит решение за доли секунды, демонстрируя элегантность и простоту кода [10:27].