# Зачем нужно 17 подсказок? Судоку, которое нельзя сделать меньше

Почему классическому судоку нужно минимум 17 исходных подсказок, чтобы иметь единственное решение? Разбираем предел, доказательство и то, что это значит для игроков.

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

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

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

В классическом судоку 9×9 в каждой строке, каждом столбце и каждом квадрате 3×3 должны встречаться цифры 1–9 ровно по одному разу. Это [стандартные правила, опубликованные компанией Nikoli](https://www.nikoli.co.jp/en/puzzles/sudoku/). Уже вписанные в сетку цифры называются _заданными_ (givens) или подсказками.

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

Вот почему важна уникальность. Хорошо сформулированное классическое судоку даёт достаточно информации, чтобы определить **ровно одну** заполненную сетку. Если вы только учите правила, наш [путеводитель по судоку](/en/blog/how-to-play-sudoku) — отличная точка старта.

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

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

```text
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, столбец 4 | 6         | 7         |
| Строка 1, столбец 5 | 7         | 6         |
| Строка 4, столбец 4 | 7         | 6         |
| Строка 4, столбец 5 | 6         | 7         |

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

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

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

Гэри МакГуайр, Бастиан Тугеманн и Жиль Сиварио доказали, что **ни одно классическое судоку 9×9 с 16 заданными числами не имеет ровно одного решения**. Их [оригинальная научная статья](https://arxiv.org/abs/1201.0749) описывает исчерпывающий компьютерный поиск. Головоломки с 17 подсказками, имеющие единственное решение, существуют — значит, 17 и есть минимум.

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

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

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

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

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

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

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

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

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

В вашей следующей игре попробуйте объяснять каждую расстановку до того, как делать её: «Это единственная клетка в квадрате, где может стоять 4». Если вы пока не можете объяснить ход, проверьте кандидаты или попробуйте технику из нашего [гайда по решению судоку](/en/blog/common-techniques-for-solving-sudoku).

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