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

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

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

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

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

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

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

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

Обсудить
Наука и техника00:0117 ноября

Пробила дно

Планета-пришелец расколола Землю и сдвинула континенты
Моя семья
Легендарный маньяк и его культ кровавых убийц держали в страхе всю Америку
Чарльз МэнсонКонец маньяка: Чарльз Мэнсон умер в тюрьме
Легендарный убийца не дождался великой межрасовой войны
Порошок, приходи
Жадные мексиканцы потеряли доход от марихуаны и завалили Америку героином
Кровавая ривьера
Франция отстреливает врагов по всему миру, пока никто не видит
«Девочку из России тут никто не ждет»
История сибирячки, перебравшейся в Нидерланды
Во всем виноват буй
Она мечтала о круизе с секс-рабынями, но потерялась в море с боевой подругой
«Не надо меня спасать»
Звездный путешественник нашел тайное племя головорезов, ввязался в войну и выжил
Эмилио Эстевес в роли Билли КидаМалыш на миллион
Легендарный головорез Дикого Запада передал привет из прошлого
Самые большие шины в мире
Огромные покрышки, которые подойдут даже машине Годзиллы
5 причин, почему мы ненавидим кроссоверы
Объясняем в картинках, почему самые популярные машины в мире никуда не годятся
Audi Q5 против SQ5
Пять причин купить Audi SQ5 вместо обычной Q5 (и одна против)
Кто делает самые эпатажные британские машины
«Рэйнджи», «Астоны» и «Роллс-Ройсы»: лучшие творения ателье Kahn Design
Ловушка для планктона
Тест: Какой офис идеально вам подходит
«Моя бывшая живет на помойке»
Москвич сделал из жены бомжа, и ему не стыдно
Белый друг
Самые необычные туалеты мира
Это Англия, детка!
Идеальный дом можно выиграть за две тысячи рублей
Берите две
Пять стран, где ипотеку дают под смешной процент