Математики решили задачу о подсказках в судоку

Судоку с 16-ю подсказками и ровно 2-мя решениями

Ирландские ученые решили так называемую проблему подсказок в судоку. Препринт их статьи появился на сайте arXiv.org.

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

В рамках новой работы ученые ответили на вопрос, сколько минимум таких подсказок нужно, чтобы судоку имело однозначное решение. Как оказалось, подсказок должно быть не менее 17. Примечательно, что ранее уже был известен пример задачи с 16 подсказками, у которой есть ровно два решения.

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

Как следствие, перебор удалось свести к чуть менее чем 5,5 миллиарда вариантам (всего правильных вариантов заполнения судоку порядка 1021). Эти вычисления, которым предшествовало двухлетнее тестирование алгоритма, были проделаны на суперкомпьютере. В результате ученые установили, что 16 подсказок (или меньше) недостаточно для того, чтобы "убить" все плохие множества, поэтому придумать головоломку с таким количеством подсказок и однозначным решением невозможно.

По словам ученых, созданная ими схема уменьшения количества вариантов с помощью плохих множеств может быть использована в других областях исследований - например, биоинформатике или автоматизированном тестировании программ.

Обсудить
Наука и техника
 — 
00:01 18 февраля 2017

Много чести

Кто кого заборет: викинг, рыцарь или самурай — обзор For Honor
Наука и техника
 — 
00:04 Сегодня
Инквизиторы допрашивают предполагаемых еретиков

Карающая длань

Как мальтийская инквизиция наказывала христиан-вероотступников
Пенная вечеринка
Легендарная серия Half-Life обретает достойное продолжение: превью Prey
Много чести
Кто кого заборет: викинг, рыцарь или самурай — обзор For Honor
Инквизиторы допрашивают предполагаемых еретиковКарающая длань
Как мальтийская инквизиция наказывала христиан-вероотступников
Демонстрация черносотенцев в Одессе вскоре после объявления «Манифеста 17 октября»Русский порядок
Почему евреи оказались главными врагами черносотенных студентов и спортсменов
Страна оленья
Почему Якутия — главное направление для путешествий в этом году
Четыре мачты парусов
Барку «Седов» в День всех влюбленных исполняется 96 лет
Дубай-Марина. ОАЭ
© Олег Жуков / Фотобанк ЛориНа границе моря и пустыни
Почему в Дубай стремятся сотни тысяч россиян
Не наше все
Страны, где не встретить путешественников из России
«Гелик» G65 против мотоцикла Ural
Путешествие американцев на Mercedes-AMG G65 и «Урале» с коляской
7 малоизвестных ландо Mercedes
Машины с кузовом «ландо», которые выглядят лучше, чем Maybach G650 Landaulet
7 неожиданно красивых «китайцев»
Кроссоверы из Поднебесной, которые вам точно захочется купить
История культовых тюнинг-ателье: Alpina
Гид по истории самого знаменитого тюнера BMW
Дворянское гнездо
Один из самых шикарных в мире домов нашли в диком лесу
Поставили баком
Англичане сделали идеальный дом из резервуара для воды
Под гербом золотым
Экскурсия по самому дорогому съемному коттеджу России
Купить по-русски
На приобретение загородных домов и участков остался месяц