Исследователи из британского University of St Andrews бросили вызов: найти решение «простой» шахматной загадки и за это получить 1 миллион долларов.
Профессор Ян Гент и его коллеги считают, что программа, способная эффективно решить знаменитую головоломку «Queens Puzzle», позволит справиться с вопросами дешифровки кодов в интернете.
Об этой задаче известно еще с 1850 года: требуется разместить 8 ферзей на игровой доске, состоящей из 64 клеток, таким образом, чтобы любые два из них не могли друг друга атаковать. Решение существует вплоть до увеличения размера шахматного поля и количества фигур до тысячи.
Команда исследователей обнаружила, что как только число клеток достигает 1000 на 1000, то компьютер, решающий головоломку «Queens Puzzle», зависает.
В статье, которую опубликовали в Journal of Artificial Intelligence Research, британские ученые предложили создать алгоритм для быстрого решения данной задачи или доказать, что его нет.