Max Home IndustryИгра в судоку была и остается страстью для многих, но удивительно, как мало мы знаем о ее алгоритмической структуре. Теперь у нас есть результат: у вас не может быть проблемы только с 16 подсказками — вам нужно больше, чтобы гарантировать уникальное решение.
Стандартная головоломка судоку играется на сетке 9×9, и обычные правила заключаются в том, что каждая сетка 3×3 содержит цифры от 1 до 9 ровно один раз. Для правильного судоку также общепризнано, что при начальном наборе заполненных квадратов должно быть только одно правильное завершение, то есть только один «правильный» ответ.
Теперь, если вы программист, очевидный вопрос, ну один из вопросов, это
«сколько цифр нужно ввести, чтобы гарантировать, что существует только одно решение?»
Учитывая, что в сетке 81 ячейка, а типичные опубликованные головоломки содержат около 25 цифр, вы можете быть удивлены, узнав, что есть головоломки с уникальным решением, использующим только 17 подсказок.
Вот пример:
Учитывая, что сложность судоку, вероятно, зависит от количества подсказок, существует реальный интерес к поиску головоломок с 16 или меньшим количеством подсказок, но ни одна из них не была найдена.
Теперь мы знаем почему.
Группе, возглавляемой Гэри Макгуайром из Университетского колледжа Дублина, удалось доказать, что головоломка с 16 ключами всегда имеет более одного решения и, следовательно, не существует сеток судоку с 16 ключами.
Поначалу использованный метод может показаться несколько грубым — исчерпывающий поиск по всему пространству головоломок с 16 ключами. Возьмите все готовые сетки судоку и поищите головоломки, в которых эта конкретная сетка является решением. Даже умный, оптимизированный поиск методом грубой силы занял бы около 300 000 лет, поэтому очевидно, что прямой подход невозможен.
Также стоит отметить, что чисто математические подходы к доказательству отсутствия сетки из 16 ключей с уникальным решением практически ни к чему не привели. Вы можете легко доказать, что сетка из 7 подсказок имеет как минимум два решения — две недостающие цифры можно поменять местами, чтобы получить другое решение, — но не очевидно, что сетка из 8 подсказок имеет более одного решения. Расстояние от 7 до 17 — это довольно много, поэтому чисто логическое решение, вероятно, сложно.
Последняя программа поиска, которая не смогла найти ни одной решетки судоку с 16 ключами, использовала некоторые теоремы, чтобы сузить круг вопросов, которые необходимо было рассмотреть. Подробный алгоритм объясняется в статье, и утверждается, что он почти наверняка имеет другие применения в аналогичных комбинаторных задачах, включая геномику, биоинформатику, компьютерные сети и тестирование программного обеспечения. В конечном итоге он использует проблему «совпадения множеств», которая является одной из классических NP-полных задач, поэтому она трудна в вычислительном отношении.
Проблема набора ударов звучит достаточно невинно, когда вы впервые сталкиваетесь с ней, но вы быстро понимаете, что найти набор ударов сложно.
Учитывая набор подмножеств элементов, все, что вам нужно сделать, это найти набор заданного размера k, набор k-ударов, который содержит по одному элементу из каждого подмножества. Учитывая, что некоторые наборы могут содержать один и тот же предмет, вы можете видеть, что это сложнее, чем кажется на первый взгляд — попробуйте, если вы мне не верите.
Окончательный алгоритм по-прежнему занял 7,1 миллиона ядерных часов на машине с 320 вычислительными узлами, каждая с 6 ядрами. Программа была запущена в январе 2011 года и завершена в декабре 2011 года.
Так что же это значит для мира, играющего в судоку? На самом деле не очень много — задач с 17 подсказками очень мало, и большинство игроков находят проблемы с обычным количеством подсказок достаточно сложными.
Однако очень унизительно замечать, что даже на простые вопросы о конечных вещах очень быстро становится очень трудно ответить.
Наконец, кто мог сопротивляться возможности процитировать мультфильм xkcd на эту тему: