Методы решения судоку¶
Судоку — логическая головоломка, в которой заполняется сетка 9×9, разделённая на девять блоков 3×3. Цель — расставить в каждой строке, столбце и блоке цифры от 1 до 9 так, чтобы каждая цифра встречалась ровно один раз. Решение достигается не вычислениями, а дедуктивным рассуждением: из имеющихся подсказок выводятся новые цифры. Ниже описаны основные методы, применяемые при решении судоку.
¶Общие принципы
Все техники решения судоку делятся на две группы. Элементарные методы позволяют находить однозначные клетки — те, в которые подходит только одна цифра. Более сложные техники работают с кандидатами (возможными цифрами в клетке) и требуют рассмотрения нескольких вариантов сразу. Начинающему игроку рекомендуется сначала освоить элементарные методы, а затем переходить к продвинутым.
Перед применением методов полезно вести список кандидатов — маленькие цифры в каждой пустой клетке, обозначающие все допустимые варианты. Кандидаты исключаются по мере появления новых цифр.
¶Элементарные методы
¶Сканирование строк и столбцов
Самый простой способ: для каждой цифры 1–9 рассматривается, в каких строках и столбцах она уже стоит. Если в блоке 3×3 цифра отсутствует, но в двух из трёх строк блока она уже занята, свободная клетка остаётся только в одной строке — туда и ставится цифра. Аналогично для столбцов.
¶Единственная кандидатура (hidden single)
Если в строке, столбце или блоке какая-то цифра может стоять только в одной конкретной клетке (все остальные позиции заняты или заблокированы кандидатами), эта цифра ставится туда. Метод работает и в обратную сторону: если в клетке подходит только одна цифра из всех возможных, она однозначна.
¶Исключение кандидатов (naked single)
Если после всех внесённых цифр в пустой клетке остаётся ровно один кандидат, эта цифра ставится в клетку. Метод требует аккуратного ведения списка кандидатов.
¶Продвинутые методы
¶Пары и тройки
Если в пределах одной строки, столбца или блока две клетки содержат одинаковый набор из двух кандидатов (например, {3, 7}), эти кандидаты исключаются из всех остальных клеток области. Метод называется «скрытая пара», если кандидаты видны только в этих двух клетках, и «открытая пара», если в этих клетках нет других кандидатов. Аналогичные приёмы работают для троек и более крупных групп.
¶Техника X-Wing
Если для какой-то цифры в двух строках она занимает только две одинаковые позиции (одинаковые столбцы), эта цифра исключается из этих столбцов в остальных строках. Метод основан на том, что в двух столбцах цифра займёт ровно эти две позиции.
¶Сканирование с исключением (fish-методы)
X-Wing — частный случай более общей группы методов «рыбы»: Swordfish (3 строки × 3 столбца), Jellyfish (4×4) и другие. Логика та же, но масштаб больше.
¶Техника XY-Wing
Работает с тремя клетками-«крыльями», каждая из которых содержит ровно два кандидата. Если две клетки связаны с третьей общим кандидатом, этот кандидат исключается из клеток, видимых обеими «крыльями».
¶Coloring и цепочки
Метод предполагает раскраску кандидатов в два цвета по цепочкам связей. Если один из цветов приводит к противоречию, все клетки этого цвета исключаются.
¶Порядок работы над судоку
- Заполнить все клетки, где цифра определяется элементарными методами.
- Вести список кандидатов и обновлять его после каждого хода.
- Применять методы пар и троек для сокращения кандидатов.
- При необходимости переходить к X-Wing и другим продвинутым техникам.
- Если противоречие не найдено, допустимо применить метод проб и ошибок: выбрать клетку с двумя кандидатами, предположить один из них и проверить последствия.
¶Сложность и генерация судоку
Уровень сложности судоку определяется не количеством начальных цифр (подсказок), а глубиной логических рассуждений, необходимых для решения. Минимальное количество подсказок для единственного решения — 17; судоку с меньшим числом подсказок, как правило, имеют несколько решений. Генерация судоку с гарантированным единственным решением — нетривиальная задача, для которой используются алгоритмы, основанные на переборе и проверке однозначности.
Источники:
- Говард Гарнс — автор современного формата судоку (1979)
- Никола Николи (Nikoli) — японское издательство, популяризировавшее судоку
- Книги по логическим головоломкам и методам их решения
