Уберите одно число из судоку — и, возможно, задача станет сложнее. Уберите не то — и, возможно, вы уничтожите единственный ответ головоломки. Где-то между полной сеткой и пустым листом есть жёсткий предел: 17 исходных подсказок. Почему судоку останавливается на этом числе?

Ответ начинается с вопроса, который легко упустить: у вашей головоломки есть ровно одно решение?

Одна заполненная сетка — один ответ

В классическом судоку 9×9 в каждой строке, каждом столбце и каждом квадрате 3×3 должны встречаться цифры 1–9 ровно по одному разу. Это стандартные правила, опубликованные компанией Nikoli. Уже вписанные в сетку цифры называются заданными (givens) или подсказками.

Заполненная сетка может подчиняться всем этим правилам — но при этом не быть единственным возможным ответом для заданных подсказок. Если подходят две разные финальные раскладки, игроку неоткуда будет узнать, что именно имел в виду составитель.

Вот почему важна уникальность. Хорошо сформулированное классическое судоку даёт достаточно информации, чтобы определить ровно одну заполненную сетку. Если вы только учите правила, наш путеводитель по судоку — отличная точка старта.

Понаблюдайте: как одна подсказка меняет всё

Вот намеренно почти завершённая головоломка. Точка отмечает пустую клетку.

5 3 4 | 6 . 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | . . 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

Здесь 78 подсказок и одно решение. В верхней строке нужен 7. Тогда в четвёртой строке в столбце четыре тоже должен быть 7, а в столбце пять — 6.

Теперь уберите 6 в строке один, столбце четыре. Пустых клеток стало четыре, и подходят две раскладки:

КлеткаВариант AВариант B
Строка 1, столбец 467
Строка 1, столбец 576
Строка 4, столбец 476
Строка 4, столбец 567

Все остальные числа остаются теми же. Оба варианта удовлетворяют каждой строке, каждому столбцу, каждому квадрату 3×3 и всем остальным подсказкам. Эти четыре клетки образуют прямоугольник, где 6 и 7 можно поменять местами — и при этом правило не нарушится. Мы проверили число решений: в первой головоломке было ровно одно решение; после удаления подсказки стало ровно два.

Удаление подсказки не может сделать недействительным то решение, которое уже работало: оно по-прежнему удовлетворяет всем оставшимся подсказкам. А вот что удаление может сделать — это допустить другой ответ. Даже эта головоломка с 77 заданными числами оказывается неоднозначной, так что одно большое число подсказок само по себе не гарантирует уникальность.

Почему 17 — это минимум

Гэри МакГуайр, Бастиан Тугеманн и Жиль Сиварио доказали, что ни одно классическое судоку 9×9 с 16 заданными числами не имеет ровно одного решения. Их оригинальная научная статья описывает исчерпывающий компьютерный поиск. Головоломки с 17 подсказками, имеющие единственное решение, существуют — значит, 17 и есть минимум.

Это не значит, что любое расположение 17 чисел автоматически даст корректную головоломку. Важны и позиции, и значения. Результат относится именно к классическому судоку; в вариантах с дополнительными правилами задача меняется.

Почему исключение случая с 16 означает исключение и меньших чисел? Если бы у меньшей головоломки было одно решение, вы могли бы добавить правильные подсказки из этого решения — пока в итоге не получилось бы ровно 16. При добавлении подсказок уникальный ответ сохранился бы, но это противоречит результату.

Как доказать, что меньшая головоломка невозможна?

Найти одну головоломку с 17 подсказками — значит показать, что возможно. А чтобы доказать, что с 16 не работает, нужно исключить все варианты.

Исследователи систематически перебирали уже заполненные сетки, учитывая эквивалентные случаи. Их метод использовал неизбежные множества: группы клеток, в которых обязательно должна быть подсказка, чтобы не дать появиться альтернативному завершению. Они разработали эффективный алгоритм перечисления покрывающих множеств (hitting sets) — выборов, которые пересекают эти группы, — и проверяли кандидатов по множеству подсказок на уникальность. Статья объясняет метод.

Прямоугольник выше — небольшая иллюстрация идеи. Оставьте все четыре клетки без подсказок — и вы сохраните два варианта. Зафиксируйте хотя бы одну из этих клеток — и вы блокируете именно эту перестановку местами. В разреженной головоломке многие возможные альтернативы приходится блокировать одновременно.

Минимум подсказок не означает максимум сложности

Количество подсказок отвечает на вопрос: «Сколько информации напечатано?». Но оно не говорит, какое именно рассуждение вы заметите следующим. Просто считать заданные числа недостаточно, чтобы понять, будет ли следующий ход очевидной одиночкой или шаблоном, который вы ещё не изучали.

Есть ещё одно полезное различие: минимум и минимальная. Минимум — это самое маленькое число подсказок, которое вообще возможно в классическом судоку. А минимальная головоломка — это такая, в которой удаление любой заданной подсказки убирает уникальность решения. Назвать головоломку минимальной — не значит сказать, что у неё 17 подсказок.

В вашей следующей игре попробуйте объяснять каждую расстановку до того, как делать её: «Это единственная клетка в квадрате, где может стоять 4». Если вы пока не можете объяснить ход, проверьте кандидаты или попробуйте технику из нашего гайда по решению судоку.

В следующий раз, когда вы увидите разреженное судоку, посчитайте подсказки — а затем найдите причину, почему каждая из них важна.

ПРИСОЕДИНЯЙТЕСЬ К ОБСУЖДЕНИЮ

Комментарии

0

Поделитесь мыслью, задайте вопрос или помогите другому игроку.

Проверяем вход…

Загружаем комментарии…