Судоку 17 подсказок Эксперт
Последний список результатов для #1yp6d
Последний список результатов для Судоку 17 подсказок
Как играть в Судоку 17 подсказок
Было доказано, что стандартная головоломка судоку должна содержать не менее 17 подсказок, чтобы иметь уникальное решение.
Правила судоку:
<ул> <ли>Заполните числа 1–9 в каждой строке, столбце и подсетке 3 x 3 в сетке 9 x 9.
<ли>Каждое число может появляться только один раз в каждой строке, столбце и подсетке 3x3.
<ли>Заполните пустые места цифрами от 1 до 9 так, чтобы в каждой строке, столбце и подсетке 3x3 были все числа от 1 до 9.
Судоку — это логическая головоломка с размещением чисел. Цель состоит в том, чтобы заполнить сетку 9x9 числами от 1 до 9 так, чтобы каждая строка, столбец и подсетка 3x3 содержали все девять чисел ровно один раз.
В 2009 году Гэри Макгуайр и его команда доказали, что любая головоломка судоку с 16 подсказками должна иметь как минимум два решения. Они сделали это, используя технику под названием «мертвые шаблоны».
Мертвый шаблон — это конфигурация судоку, имеющая два или более возможных решения. Макгуайр и его команда обнаружили, что любая головоломка судоку с 16 подсказками должна содержать хотя бы один мертвый шаблон. Следовательно, эти головоломки должны иметь как минимум два решения.
Этот результат имеет несколько последствий. Во-первых, это означает, что не существует такого понятия, как судоку из 16 подсказок с уникальным решением. Во-вторых, это означает, что любую головоломку судоку с 16 подсказками можно решить несколькими способами. В-третьих, это означает, что существует бесконечное количество головоломок судоку с 16 подсказками.
Вот более техническое объяснение доказательства того, что головоломки судоку должны иметь как минимум 17 подсказок, чтобы иметь уникальное решение:
Доказательство начинается с рассмотрения головоломки судоку с 16 подсказками. Мы можем думать об этой головоломке как о наборе ограничений на числа, которые можно разместить в пустых квадратах.
Затем мы можем использовать технику, называемую «возвратом», чтобы попытаться найти решение головоломки. Поиск с возвратом – это рекурсивный алгоритм, который перебирает все возможные комбинации чисел в пустых квадратах, пока не найдет решение.
Если у головоломки есть уникальное решение, то возврат в конечном итоге его найдет. Однако если существует несколько решений, возврат может никогда не найти решения.
Макгуайр и его команда использовали обратный поиск, чтобы показать, что если существует головоломка судоку с 16 подсказками и уникальным решением, то должен быть способ запустить алгоритм обратного поиска таким образом, чтобы он всегда находил решение.
Затем они показали, что это невозможно. Они сделали это, составив набор из 16 подсказок, которые ведут к мертвой схеме. Этот мертвый шаблон означает, что существует два возможных решения головоломки и нет возможности запустить алгоритм поиска с возвратом таким образом, чтобы он всегда находил одно и то же решение.
Этот результат показывает, что любая головоломка судоку с 16 подсказками должна иметь как минимум два решения.
