Вопросы с тегом «sudoku»

23
Если я могу решить судоку, могу ли я решить задачу коммивояжера (TSP)? Если так, то как?

Допустим, есть такая программа, которая, если вы дадите частично заполненную судоку любого размера, даст вам соответствующую заполненную судоку. Можете ли вы рассматривать эту программу как черный ящик и использовать это для решения TSP? Я имею в виду, есть ли способ представить проблему TSP как...

16
Эффективное кодирование головоломок судоку

Указание любой произвольной сетки 9x9 требует указания позиции и значения каждого квадрата. Наивное кодирование для этого может дать 81 (x, y, значение) триплетов, требуя 4 бита для каждого x, y и значения (1-9 = 9 значений = 4 бита) в общей сложности 81x4x3 = 972 бита. При нумерации каждого...

14
Какая разница в сложности может быть между поиском решения головоломки Судоку и доказательством того, что решение является единственным решением?

Поэтому обычно судоку составляет , но этот вопрос распространяется и на головоломок с . Существует много правил вычета полиномиального времени, которые могут помочь в поиске решения головоломки Судоку. Но тогда иногда требуется угадывание значений и последующие цепочки выводов, чтобы исключить...

13
Генератор случайных судоку

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

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

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