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

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

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

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

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

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

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

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

Обсудить
Наука и техника00:0724 июля
Пуск ракеты «Союз-2» с Восточного

Стоп машина!

Россия откажется от «Ангары» и Восточного ради Байконура и «Союза-5»
Клан Хаккано
Что общего у афганской террористической группировки и героев фильма про мафию
Корейская проститутка в национальном костюме во время акции протеста против полицейских рейдов на бордели Интим предлагать
Особенности рынка платных сексуальных услуг в Корее
Древность и молодость современного Ирана
Республика через 38 лет после Исламской революции
Георгий Толорая: Что ответит Пхеньян
Почему ядерное оружие у КНДР не станет залогом мира на Корейском полуострове
Бой за печень исламиста
Филиппинские военные с помощью иностранцев добивают боевиков в Марави
Пуск ракеты «Союз-2» с ВосточногоСтоп машина!
Россия откажется от «Ангары» и Восточного ради Байконура и «Союза-5»
Клубенек рукоделия
Картошку с тостером превратили в источник удовольствия и боли
Дотыкались
Зачем отправляли на смерть чернокожих коммунистов
Лучше «Соляриса» или нет?
Первый тест нового седана Kia Rio
Броневики смерти
Как выглядят бронированные машины, построенные террористами
Дерзкие версии скучных машин
От Sandero до пикапа: какие утилитарные модели получали спортивные версии
5 аварий грузовиков с необычным грузом
Цыплята, слизистые угри и два миллиона наличными
«Я ничего не делаю, и мне это нравится»
Откровения москвички, которая сдает жилье и принципиально не работает
Зарыться в песок
Купить квартиру на море теперь можно за миллион рублей и дешевле
Входят и выходят
Самые известные, необычные и дорогие бордели мира
У вас упало
Что на самом деле происходит с ценами на квартиры в Москве