Минимальное количество подсказок, чтобы полностью указать любую судоку?

9

Из этой статьи мы знаем, что не существует загадки, которую можно решить, начиная с 16 или менее ключей, но это означает, что существует загадка, которую можно решить из 17 подсказок. Можно ли указать все действующие головоломки судоку в 17 подсказках? Если нет, каково минимальное количество подсказок, которые могут полностью указать каждую действительную головоломку? Более формально, существует ли действительная головоломка судоку (или, я думаю, это будет набор головоломок), которая не может быть однозначно решена только из 17 подсказок? Если так, то каково минимальное количество ключей , чтобы каждая действительная головоломка судоку могла быть однозначно определена в C или меньше ключей?СС

Kevin
источник

Ответы:

2

Так как перестановка двух строк в одном блоке действительного, завершенного судоку создает другую действительную, завершенную судоку, вы можете взять любую законченную доску (81 подсказка) и удалить первые две строки (81-18 = 63 подсказки), что даст вам неполная судоку с двумя решениями. Обратите внимание, что даже если вы удалите все, кроме одного из 18 чисел, решение будет определено однозначно (так как в одном столбце не может быть повторений).

Другая операция, которая производит другую завершенную судоку, - это применение перестановки . Если вы берете перестановку, которая является транспозицией (переставляет два элемента, оставляя остальные фиксированными), снова, как и раньше, вы можете удалить все появления этих двух элементов, и у вас будет неполное судоку с двумя возможными решениями и 63 подсказками. Опять же, если вы не удалите все 18 номеров, решение будет уникальным.{1,...,9}

Из шести элементарных операций, которые производят завершенную судоку (см. Здесь ), эти две могут включать наименьшее количество элементов, поэтому я бы сказал, что - верхняя граница того, что вы ищете. Я знаю, что это не совсем отвечает на ваш вопрос, но общая идея удаления наборов позиций, которые дают два разных решения, может быть хорошей отправной точкой.Сзнак равно63

Janoma
источник
1

В наименьшее количество подсказок , необходимых для надлежащего судоку является 17, но не все завершенные сетки могут быть сокращены до надлежащего 17 ключ судоку. Было найдено около 49 000 уникальных (не эквивалентных) Судоку с 17 подсказками. (Правильный судоку имеет только одно решение).

В большинстве подсказок в минимальном судоку , как полагают, 40 (два , как известно, существует), но это не было доказано , если это максимум. (минимальный означает, что если какая-либо подсказка будет удалена, у Судоку будет более одного решения, и, следовательно, он не будет правильным Судоку)

(Эта информация взята из Википедии, на которую хорошо ссылаются эти утверждения).

Томока Казуки
источник
N2
Я не видел, что доказано ни в одной статье. Интересно, что почти вся работа по нахождению минимального судоку с высоким значением «h», по-видимому, проводится поиском известного судоку и изменением его для итеративного увеличения «h». Работа по поиску минимальных 40 разгадочных головоломок позволила создать базу данных из более чем 6 500 000 000 других минимальных загадок с высокой подсказкой. За исключением тривиальных проблем, я почти не видел строгих расследований, кроме как «поиска». Но ваше предложение интересное.
Томока Казуки
Не могли бы вы добавить сюда цитаты, пожалуйста? Или хотя бы ссылку на соответствующую страницу Википедии.
Дэвид Ричерби
Эта информация взята из статьи Википедии «Математика судоку», раздел «Максимальное количество даров». Цитируемая ссылка (для обнаружения 1-го 40-ти подсказного минимального судоку): forum.enjoysudoku.com/high-clue-tamagotchis-t30020-135.html Ключевая информация - это лист 10, но связанная информация - как до, так и после листа 10.
Томока Казуки
0

У этого Судоку есть 77 подсказок, и все же у этого есть многократные решения (2). Вы можете использовать 7-4 в верхнем ряду и 4-7 в другом или 4-7 в верхнем и 7-4 в нижнем. Эта конкретная головоломка судоку нуждается в 78 подсказках, чтобы иметь уникальное решение.введите описание изображения здесь

Nicomal
источник
Это хороший момент, но я думаю, что это не совсем вопрос, который задают, а именно о минимальном количестве подсказок для задания головоломки, если вы выбираете стратегически подсказки
6005
Я думаю, что это хороший ответ, но было бы неплохо добавить к этому ответу (1) примечание, почему это немного отличается от задаваемого вопроса, (2) преобразовать нечеткое изображение в текстовую таблицу и / или объяснение
6005