Каково минимальное количество подсказок, которое может иметь Судоку?
Последнее обновление
Действительное судоку — с ровно одним решением — требует как минимум 17 заданных цифр. Это доказанный математический результат. Любая головоломка с 16 или менее подсказками имеет либо несколько решений, либо ни одного.
Доказательство 2012 года
В 2012 году Гэри МакГуайр, Бастьен Тугеманн и Жиль Сиварио из Университетского колледжа Дублина опубликовали доказательство того, что не существует действительного судоку с 16 подсказками. Их работа была в основном вычислительной: они исследовали всё пространство возможных сеток с 16 подсказками и подтвердили, что ни одна из них не даёт единственного решения. Поиск потребовал примерно 7 миллионов ядро-часов вычислений.
До этого широко считалось, что 17 — это минимум, и тысячи головоломок с 17 подсказками были найдены экспериментально. Команда МакГуайра предоставила первое строгое доказательство того, что 16 невозможно.
Как выглядят головоломки с 17 подсказками
17-clue puzzles чрезвычайно разрежены — 17 given digits в 81 cells, оставляя 64 empty. Они являются одними из самых сложных puzzles для решения и обычно требуют advanced techniques. Поиск valid 17-clue puzzles сам потребовал десятилетий computational effort. На момент написания известно более 49,000 essentially different 17-clue Sudoku puzzles.
Что это означает для дизайна головоломок
Опубликованные головоломки, предназначенные для людей-решателей, редко опускаются ниже 22 подсказок. Головоломки Эксперт и Мастер обычно используют 22-27 заданных цифр, в то время как лёгкие головоломки используют 36-45. Минимум в 17 подсказок является теоретической границей - На практике решаемость с хорошей техникой и приятный путь решения значат гораздо больше, чем количество подсказок.