Хотите видеть только хорошие новости?

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

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

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

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

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

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

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

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

Обсудить
Министр обороны Саудовской Аравии принц Мухаммед объявляет о создании блокаНАТО с Кораном и гуриями
Саудовская Аравия строит собственный военный блок
Монастырь Мар Маттай«Саддам покончил бы с этим бардаком за пару недель»
Рассказ монаха древнего иракского монастыря о жизни по соседству с террористами
Лошадиные силы
Мустанги, воспитанные за решеткой, несут службу на границе
Далай-лама XIV«Сто лет назад я был бы среди революционеров»
Далай-лама XIV об основах буддизма, избрании Трампа и важности образования
Эффект обратного действия
Теракт в Берлине укрепил позиции Меркель и доверие немцев к стражам порядка
«Живу обычно, ем летучих мышей»
История москвича, переехавшего в Камбоджу
Качайся как девчонка
Пауэрлифтинг вошел в моду у представительниц прекрасного пола
Проект «Оливье»
Фотоистория о том, чем россияне потчевали себя в Новый год
Ким КардашьянСтарики-разбойники
Выслежена банда преступников-пенсионеров, ограбивших Ким Кардашьян
Красивейшие машины Советского Союза
Самые красивые машины СССР, так и не увидевшие конвейера
Enlarge your Lada
Самые нелепые российские лимузины
Редкие «ГАЗы»
5 внедорожников Горьковского автозавода, которые так и не увидели свет
Самые продаваемые машины в России
Самые популярные автомобили российского рынка за минувшие 12 месяцев
«Теперь она бомж и живет в закутке под лестницей»
История преподавательницы, лишившейся трех квартир в Москве
«Мы начали решать свои проблемы, как в 90-х»
За потребительские кредиты смогут отбирать квартиры
Развели тут бордель
Экскурсия по самому большому публичному дому Южного полушария
Война дворцам
Каких домов лишились в 2016 году звезды Голливуда