Судоку — одна из самых популярных головоломок в мире, но для программиста это прежде всего классическая задача на построение эффективного алгоритма. В видеоролике на канале Computerphile ведущий демонстрирует, как с помощью языка Python и концепции поиска с возвратом (backtracking) написать лаконичный решатель Судоку всего в несколько десятков строк кода. Этот подход наглядно иллюстрирует силу рекурсии и системного перебора вариантов в компьютерных науках.
🧩 Суть головоломки Судоку и концепция Backtracking 0:00
Игровое поле Судоку представляет собой сетку размером 9x9 клеток, которая также разделена на девять меньших квадратов размером 3x3 . Задача игрока — заполнить пустые ячейки цифрами от 1 до 9 так, чтобы выполнялись три жестких правила:
- Каждая цифра от 1 до 9 должна встречаться в каждой строке ровно один раз.
- Каждая цифра от 1 до 9 должна встречаться в каждом столбце ровно один раз.
- Каждая цифра от 1 до 9 должна встречаться в каждом из девяти малых квадратов 3x3 ровно один раз .
Для автоматического решения такой задачи программисты используют метод под названием backtracking (поиск с возвратом) . Как объясняет ведущий канала Computerphile, этот алгоритм работает по принципу проб и ошибок. Он пытается поставить число в пустую клетку и, если это не нарушает правила, переходит к следующей клетке. Если же в процессе заполнения сетки алгоритм заходит в тупик (когда для очередной пустой клетки нет ни одного подходящего числа), он делает шаг назад, отменяет последнее действие и пробует другой вариант .
🛠️ Подготовка данных: Представление сетки в Python 1:29
Для реализации алгоритма в Python необходимо правильно представить игровое поле. Ведущий использует двумерный список (матрицу) размером 9x9, где заполненные клетки содержат соответствующие числа, а пустые ячейки обозначены нулями .
Такое представление позволяет легко обращаться к элементам по индексам строк и столбцов. Вся работа программы будет происходить непосредственно с этой глобальной переменной grid, что избавляет от необходимости постоянно передавать копии игрового поля между функциями .
🔍 Функция проверки ограничений: Метод possible 2:32
Прежде чем приступать к написанию основного решателя, необходимо создать вспомогательную функцию проверки. Автор видео объявляет функцию possible(y, x, n), которая принимает три параметра: координату строки y, координату столбца x и число n, которое мы хотим туда поместить . Функция должна возвращать True, если число можно вставить в данную позицию, и False в противном случае.
Для этого алгоритм поочередно проверяет три условия:
- Проверка строки: программа итерируется по столбцам текущей строки
yи проверяет, нет ли там уже числаn. - Проверка столбца: программа итерируется по строкам текущего столбца
xна предмет наличия числаn. - Проверка локального квадрата 3x3: этот шаг требует простой математической операции. Чтобы найти левый верхний угол малого квадрата, в котором находится клетка
(y, x), автор использует целочисленное деление на 3 с последующим умножением на 3 : - `x0 = (x // 3)
- 3`
- `y0 = (y // 3)
- 3`
После нахождения стартовой точки (y0, x0) алгоритм обходит все 9 ячеек малого квадрата с помощью вложенного цикла . Если число n не обнаружено ни в строке, ни в столбце, ни в локальном квадрате, функция возвращает True.
⚙️ Сердце алгоритма: Рекурсивный поиск solve 3:45
Главная функция solve() не принимает аргументов, так как работает напрямую с глобальной переменной сетки . Внутри нее запускается двойной цикл для обхода всех 81 ячеек поля :
for y in range(9):
for x in range(9):
...
Когда алгоритм находит пустую клетку (содержащую 0) , он пытается подобрать для нее подходящую цифру от 1 до 9. Для этого запускается цикл for n in range(1, 10) :
- Сначала вызывается функция
possible(y, x, n). - Если число
nподходит, оно временно записывается в ячейку:grid[y][x] = n. - Затем функция
solve()рекурсивно вызывает саму себя для поиска решения для оставшихся клеток . - Если в какой-то момент последующие рекурсивные вызовы заходят в тупик, управление возвращается назад. В этот момент срабатывает механизм backtracking: программа сбрасывает значение ячейки обратно на ноль (
grid[y][x] = 0) и продолжает цикл, пытаясь примерить следующее числоn.
🖨️ Вывод результатов и поиск нескольких решений 6:11
Что происходит, когда алгоритм успешно заполняет всю сетку и на поле не остается нулей? В этот момент циклы поиска пустых клеток завершаются, и программа доходит до конца функции solve() .
Автор видео настраивает программу так, чтобы при успешном заполнении сетки она выводила текущее состояние поля на экран . Однако на этом работа не заканчивается. Чтобы пользователь успел рассмотреть решение, ведущий использует стандартную команду input() .
Интересный побочный эффект такого решения заключается в том, что если пользователь нажмет клавишу Enter, программа продолжит выполнение . Она отменит последнее успешное действие (снова сработает backtracking) и попытается найти другие возможные варианты решения головоломки.
Для демонстрации этого эффекта ведущий удаляет часть подсказок из исходного Судоку . В результате сетка теряет уникальность решения, и программа при каждом нажатии Enter мгновенно выдает новые и новые варианты правильного заполнения поля .
🧠 Почему Backtracking идеален для простых задач 9:05
В заключение ведущий канала Computerphile отмечает, что метод поиска с возвратом по своей сути является разновидностью поиска в глубину (Depth-First Search) . Вся история ходов и возвратов автоматически управляется стеком вызовов самой среды Python .
Несмотря на то, что существуют более сложные и оптимизированные подходы (например, системы удовлетворения ограничений или алгоритмы на основе связей танцующих звеньев Дональда Кнута) , для стандартной сетки Судоку 9x9 обычного рекурсивного backtracking на Python более чем достаточно. Программа находит решение за доли секунды, демонстрируя элегантность и простоту кода .
