Распечатать запись Распечатать запись

Математик заявляет о прорыве в решении головоломки судоку

Вперед, пробуйте!

Ирландский математик использовал сложный алгоритм и миллионы часов времени суперкомпьютера для решения важной открытой проблемы в математике судоку — игры, популярной в Японии, которая состоит в заполнении таблицы из квадратов 9\times9 числами от 1 до 9 по определенным правилам.

Гэри МакГайр (Gary McGuire) из Дублинского университетского колледжа в своем доказательстве, размещенном онлайн 1 января, показывает, что минимальное количество ключей, или первых цифр, необходимых для решения головоломки, составляет 17 (см. пример головоломки из работы МакГайра на рисунке), а головоломки с 16 или менее ключами не имеют единственного решения. Для сравнения, большинство головоломок из газет имеют около 25 ключей, трудность головоломки уменьшается с увеличением числа ключей.

Математики на конференции в Бостоне 7 января согласились с тем, что доказательство МакГайра, скорее всего, верно, и сделан важный шаг в развивающейся области математики судоку.

“Подход является разумным, и это правдоподобно. Я бы сказал, что этот подход внушает осторожный оптимизм’’, — говорит Джейсон Розенхаус, математик из Университета Джеймса Мэдисона в Харрисонбурге, штат Вирджиния, и соавтор недавно вышедшей книги о математике судоку.

По правилам судоку, требуется заполнить таблицу 9\times9 клеток цифрами от 1 до 9 так, чтобы никакие числа не повторялись в одном и том же столбце, строке или в одном из девяти квадратов 3\times3. Ключи — это числа, которые даны с самого начала, и энтузиасты уже давно заметили, что хотя есть небольшое количество головоломок с 17 ключами, никто не смог придумать головоломку с 16 ключами. Это привело к предположению, что головоломки с 16 ключами, имеющей единственное решение, просто не существует. Теоретически проверить это можно было бы, решив головоломку для каждого выбора 16 ключей, но это заняло бы слишком много машинного времени. Тогда МакГайр упростил задачу, разработав так называемый “алгоритм попадания в множество’’ (“hitting set algorithm”). Идея заключается в поиске того, что он называет неизбежными множествами, или расположений чисел в завершенной головоломке, являющихся взаимозаменяемыми и поэтому могущими привести к нескольким решениям. Для того чтобы предотвратить появление нескольких решений из-за неизбежных множеств, ключи должны перекрывать, или попадать в неизбежные множества. После нахождения неизбежных множеств остается гораздо более простая, хотя все же нетривиальная вычислительная задача показать, что нет головоломок с 16 ключами, которые перекроют их все.

Тестируя алгоритм в течение двух лет, МакГайр и его команда использовали около 700 миллионов часов процессорного времени в ирландском Центре высокопроизводительных вычислений в Дублине в поисках всех возможных головоломок с помощью алгоритма попадания в множество. “Единственным реальным способом сделать это было применение грубой силы’’, — говорит Гордон Ройл, математик из Западно-Австралийского университета в Перте, который работал над задачей 17 ключей, используя различные алгоритмы, — “это сложная задача , которая заставляет людей до предела использовать вычислительные и математические методы. Это как восхождение на самую высокую гору “.

“Следствием является то, что потребуется некоторое время, необходимое другим для проверки доказательства на компьютере’’, — говорит Лаура Тальман, также математик из университета Джеймса Мэдисона, соавтор книги “Принимая судоку серьезно: математика, которая стоит за самой популярной в мире головоломкой, решаемой с карандашом и бумагой’’ (вместе с Розенхаусом). Тальман говорит, что книга, которая вышла на прошлой неделе, уже устарела: в ней написано, что задача остается открытой и что тот, кто решит ее, будет “рок-звездой’’.

МакГайр подтверждает, что интерес в его доказательстве был огромен. Сначала он увлекся судоку в 2005 году, когда повальное увлечение впервые охватило земной шар, и многие газеты начали печатать головоломки на своих страницах. Он говорит, что по иронии судьбы он потратил больше времени на математику головоломки, чем на наслаждение самой головоломкой. “Я все еще считаю это хорошим способом расслабиться время от времени, но, честно говоря, я предпочитаю кроссворды’’, — говорит он. Однако его подход может окупиться в других отношениях. Идея попадания в множества, которую он разработал для доказательства, была использована в работах по анализу последовательностей генов и в сотовых сетях. МакГайр с нетерпением ожидает, что его алгоритм может быть с успехом применен и другими исследователями. “Надеюсь, это будет стимулировать больший интерес’’, — говорит он.

Источник: http://blogs.nature.com/news/2012/01/mathematician-claims-breakthrough-in-sudoku-mathematics.html

Один комментарий

  1. 1 Математики кодируют изображения с помощью судоку | Математика, которая мне нравится:

    [...] Ранее в этом году, например, была решена задача о минимальном количестве ключей для судоку, которое дает к единственное решение (таких [...]

Оставьте свой отзыв

Добавить изображение