Почему у судоку есть нижний предел подсказок
Подсказки — это цифры, уже вписанные в сетку. Чтобы судоку считалось задачей с единственным решением, этих цифр должно хватать, чтобы правила однозначно определили все пустые клетки: в каждой строке, каждом столбце и каждом квадрате 3 × 3 должны стоять цифры от 1 до 9 без повторов.
Если подсказок меньше 17, ограничения оставляют слишком много свободы. Для любой такой начальной сетки найдётся не один, а как минимум два способа заполнить её, не нарушая правил. Значит, игрок не сможет понять, какой вариант задуман как ответ.
Почему это не просто удачный поиск
Найти пример судоку с 17 подсказками сравнительно легко: достаточно предъявить сетку и проверить её решение. А доказать, что 16 подсказок никогда не хватит, гораздо сложнее — нужно исключить все возможные расположения подсказок и значения цифр, а не перебрать несколько примеров.
Для этого математики использовали компьютерную проверку огромного числа случаев. Важная идея в том, что некоторые группы клеток обязательно должны содержать хотя бы одну подсказку: иначе определённые цифры можно переставить, получив другое допустимое решение. Компьютер помог проверить, что 16 подсказок не способны перекрыть все такие возможности.
Меньше — нельзя, больше — не обязательно
Предел относится именно к судоку 9 × 9 и к требованию единственного решения. Он не означает, что любая головоломка с 17 подсказками будет решаемой или простой: расположение цифр тоже важно. Семнадцать — минимально возможное число, а не универсальная формула хорошего судоку.
