Ученые решили «проблему подсказок в судоку»

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

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

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