Открыть сервисСервис

Методы решения судоку

Судоку — логическая головоломка, в которой заполняется сетка 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 и цепочки

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

Порядок работы над судоку

  1. Заполнить все клетки, где цифра определяется элементарными методами.
  2. Вести список кандидатов и обновлять его после каждого хода.
  3. Применять методы пар и троек для сокращения кандидатов.
  4. При необходимости переходить к X-Wing и другим продвинутым техникам.
  5. Если противоречие не найдено, допустимо применить метод проб и ошибок: выбрать клетку с двумя кандидатами, предположить один из них и проверить последствия.

Сложность и генерация судоку

Уровень сложности судоку определяется не количеством начальных цифр (подсказок), а глубиной логических рассуждений, необходимых для решения. Минимальное количество подсказок для единственного решения — 17; судоку с меньшим числом подсказок, как правило, имеют несколько решений. Генерация судоку с гарантированным единственным решением — нетривиальная задача, для которой используются алгоритмы, основанные на переборе и проверке однозначности.

Источники:

  • Говард Гарнс — автор современного формата судоку (1979)
  • Никола Николи (Nikoli) — японское издательство, популяризировавшее судоку
  • Книги по логическим головоломкам и методам их решения
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru