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

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

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

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

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

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

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

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

подписатьсяОбсудить
Владимир Путин и Си Цзиньпин с супругойПоход на Восток
Почему главными темами для Путина станут Сирия, Донбасс и Курилы
«Будет мир, только часть народа будет убита»
Участники первой чеченской кампании о штурме Грозного, Кадырове и кошмарах
Голосование на избирательном участке в посольстве России во ФранцииСорвали голос
Провокации на Украине и другие помехи для выборов в Госдуму за рубежом
Ника борется за жизнь
Чудом выжившую девочку спасет внутривенное питание
Военнослужащие армии КазахстанаПрофилактика хаоса
Каковы цели российского военного планирования в Центральной Азии
Шальная «Императрица»
Будни российских проституток
Отборные кадры
Как в России подыскивают присяжных для суда
Все очень плохо
Почему новая холодная война опаснее старой
Скованные беспроводной цепью
Рассказы домашних арестантов о жизни с электронным браслетом
Скука, тестостерон и дешевый бензин
В чем смысл «арабского дрифта» и зачем его легализовали
Я вас не слышу
Чего не хватает новому Chevrolet Camaro: первый тест
Не отпускать и не сдаваться
Что происходило на одном из самых сумасшедших Гран-при сезона
Северный олень
Сохранил ли новый Mitsubishi Pajero Sport свою суровость и страшно ли на нем заезжать в глушь
Дно Олимпиады
Проблемы Рио похлеще допингов и переломов
«Я не позволяла себе ничего, каждая копейка уходила на кредит»
Рассказ россиянки, купившей не одну квартиру при зарплате в 40 тысяч рублей
Камерная дача
10 фактов о доме в Форосе, ставшем тюрьмой для Горбачева
До чего докатились
Как выглядят лица людей, съехавших с небоскреба
Бабушкино наследство
Вся недвижимость кандидата в президенты США Хиллари Клинтон