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

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

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

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

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

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

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

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

Обсудить
Все там будем
Почему невозможно уберечься от рака
Кровавое воскресенье 22 января 1905 года«Идиоты говорят, что Россию погубил заговор»
Почему революция 1917 года была неизбежна
«Это было волшебно!»Дефект массы
Как продолжение культовой серии Mass Effect стало одной из худших игр в истории
Старт ракеты с Dream Chaser — кораблем компании Sierra Nevada (в представлении художника)Еще батуты
Как американские компании опережают Россию в сфере пусков ракет
Пижон Джон
Дикий сэр Элтон, каким его уже мало кто помнит
«Главное — убедить людей, что они счастливы»
Джон Стейнбек и Роберт Капа о советских застольях, писателях и правительстве
Девочки кровавые в глазах
Кино недели с Денисом Рузаевым: от «Манчестера у моря» до «Демона внутри»
Под «Грибами» тает лед
Самая навязчивая песня сезона — во всех мемах страны
Очень страшные «Рейндж Роверы»
Самые жуткие варианты тюнинга автомобилей Land Rover
Пиджак и боб
Самое крутое автомобильное видео марта
Самые необычные ДТП
Автомобили на крышах, в бассейнах и другие непонятные аварии, достойные премии
Пластиковый BMW, о котором все забыли
Автомобиль-памятник смелым идеям немецкой компании
Бог простит
В церкви нашли квартиру с красной мебелью и портретами в стиле поп-арт
Фрэнк ГериСпугнули рыбу
Почему антисемиты изгнали из Канады создателя «танцующего дома»
«Наш дом — колония строгого режима»
История семьи, оказавшейся на грани распада из-за дачи
Цветам не место в доме
Почему дети мешают взрослым жить счастливо в собственных квартирах