Sudoku
Published in
2 min readMar 17, 2021
Разбор
Решение судоку — это задача, которая решается почти что брутфорсом, т.е. перебором различных вариантов. Но перебор выполняется с возвратом, т.е. если на очередном шаге итерации полученное частичное решение не подходит, то мы возвращаемся к предыдущему частичному решению. Так происходит, пока мы не найдем решение, если оно существует. Такой подход называется Поиском с возвратом. В англоязычных источниках алгоритмы такого рода называются “backtracking”. Многие задачи решаются таким алгоритмом. Поэтому рекомендуем ознакомиться с ним.
Алгоритм
- Запускаем наш поиск от ячейки (0, 0).
- Если текущая ячейка не пустая, то переходим к след.ячейке.
- В противном случае, находим возможные цифры кандидаты для этой ячейки и перебираем их.
- Для каждой цифры кандидата делаем предположение, что оно подходит для этой ячейки и запускаем поиск с обновленной таблицей.
- Если текущее предположение не привело к решению, снимаем это предположение, т.е. снова помечаем ячейку как пустую.
- Останавливаем процесс, когда мы достигли последней строки и последнего столбца.
Детали реализации данного алгоритма смотрите ниже по ссылке gist.github. Для большего понимания в коде есть подробные комментарии. В скриншоте статьи мы приводим только код основной функции.
Реализация
