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

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

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

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

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

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

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

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

Обсудить
Джон Кеннеди c дочерьюГосударствообразующая семья
Династия Кеннеди вчера и сегодня
«Ближние соседи важнее дальних гегемонов»
Александр Ломанов о приоритетах внешней и внутренней политики Китая
Збигнев БжезинскийЧеловек в истории
Война и мир Збигнева Бжезинского
The library at Holland House in Kensington, London, extensively damaged by a Molotov 'Breadbasket' fire bombВзорвать Британию
Соединенное Королевство уже 48 лет ведет необъявленную войну с бомбистами
Маэстро, урежьте марш
Большая семерка и НАТО — не «концерт держав», а оркестр
Хакер, который смог
Американец сбежал от произвола ФБР и стал самым успешным пиратом современности
Самоубийственные аресты
За борьбой с «группами смерти» может стоять конфликт в силовых структурах
Бей, души, убивай
Социальные сети не просто следят за нашими чувствами, они управляют ими
«Живу как в кино»
История уроженки Брянска, переехавшей на Кипр
Не лайкай всуе
10 заповедей самой вредной для психики социальной сети в мире
Гибче надо быть
Мобилити-трейнинг — модная тренировка для тех, кто не достает пальцами до пола
Жжение и зуд
Феттель против Райкконена, McLaren против кармы и другие события Гран-при Монако
10 недорогих, но крутых машин
Десятка клевых автомобилей, на которые не надо тратить много денег. В Америке
Ноги вверх!
Как устроен и чем полезен адаптивный круиз-контроль
Паровые танки
Пять увлекательных попыток построить паровую технику для войны
От нашего стола
Российские интерьеры, сводящие иностранцев с ума
Зависли на хате
Украинцы придумали дом, который может обойтись без российского газа
Москва за нами
Какие квартиры можно купить в пределах МКАД по цене до трех миллионов рублей
Сносное настроение
Демонтаж жилых домов в Москве: что нужно знать
Вышка светит
Как выглядит частный особняк, побивший мировой рекорд этажности