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

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

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

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

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

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

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

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

подписатьсяОбсудить
00:07 25 июля 2016
Планета Х напоминает Нептун

Антихристы с Нибиру

Как Планета Х наклоняет Солнце и вызывает катаклизмы на Земле
Празднование итогов референдума. Симферополь, 16 марта 2014 года«Чем ярче эйфория, тем тяжелее отходняк»
Кумовство, коррупция и бездорожье — что говорят крымчане о жизни на полуострове
Кандидат в депутаты на руках своего пресс-секретаря рядом с избиркомом Костромской области«Кот поддерживает только Путина»
Пушистый кандидат рассказал «Ленте.ру» о планах пойти в Госдуму
Дом в Чевакино
и другие заповедные места Тверской области, где побывали добровольцы из Торжка
Не клюет...
Замглавы Росрыболовства о том, почему на прилавках нет дешевой свежей рыбы
Иван Васильевич меняет прописку
Как губернатор Вадим Потомский стал властелином времени и звездой интернета
Как купить мушкет
Где приобретают «старинное» оружие и как из него стреляют
Бунт в хакасской колонии №35Бунт во славу пророка
Кто стоит за тюремными беспорядками с исламистским подтекстом
В прицеле — юг
Как российская армия отреагирует на дестабилизацию ближайших соседей
Policemen walking down stairs and securing the area in the underground station Karlsplatz (Stachus) after a shootout in Munich, Germany, 22 July 2016. After a shootout in the Olympia shopping centre in Munich, injuries and possible deaths were reported by the police. The situation is still unclear. PHOTO: ANDREAS GEBERT/dpaКТО стучится в дверь ко мне
Какие выводы стоит сделать из полицейской операции в Мюнхене
Планета Х напоминает НептунАнтихристы с Нибиру
Как Планета Х наклоняет Солнце и вызывает катаклизмы на Земле
Палач всея Руси
Кровавые и бесчеловечные убийства, совершенные Иваном Грозным
Турецкий бардак
Тайны и прелести Османской империи: фески, котики и шаурма
Рюриковичи мы!
Что скрывается за образом основателя великой Руси
Еще нарожают
Зачем персидская знать манипулировала телами своих жен
Так любил, что почти убил
Фотоистория о женщинах, изуродованных «во имя чести»
Игорь Ротарь на входе в индейскую резервацию. Надпись на плакате: «Незаконно проникающие нарушители будут застрелены. Выжившие будут застрелены еще раз». «Быть застреленным копами тут проще, чем в России»
Рассуждения россиянина, живущего в Сан-Диего, о свободе в США и РФ
Потей с Кайлой
Чем автор фитнес-программы Bikini Body Guide привлекла пять миллионов фанатов
«Она определенно сошла с ума»
Мужья любительниц Instagram поделились своей болью
Бу-дэб-пешт
Новый танец Хэмилтона и другие события гонки Формулы-1 Венгрии
Навсегда в прошлом
Современные спорткары с очаровательным ретро-дизайном
Советский форсаж
Более 100 раритетов на Красной площади: видеотрансляция
Метры у метро
Московские новостройки, рядом с которыми скоро откроют станции подземки
Тиснули на славу
Как выглядит первое в мире здание, напечатанное на 3D-принтере
Вот это номер!
«Тайный арендатор» в многофункциональном комплексе «Ханой-Москва»
Жить стало веселее
Новая редакция «сталинского рая» на ВДНХ
Любовь по залету
Аэропорты мира, которые не захочется посещать добровольно
Rolling Acres Огайо, СШАЗакрыто навсегда
Как выглядят торговые центры-«призраки», потерявшие покупателей