Задача о восьми ферзях принесет программистам $1 млн

Трое ученых из шотландского Сент-Эндрюсского университета пообещали награду в виде миллиона долларов тому, чья программа сможет эффективно решить шахматную «задачу о восьми ферзях». Статья опубликована в Journal of Artificial Intelligence Research.

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

Авторы статьи обнаружили, что компьютерные программы перестают справляться с решением задачи, когда размер доски доходит до 1000 на 1000 клеток. По мнению одного из них, профессора Сент-Эндрюсского университета Яна Гента, тот, кто сможет написать программу, способную решить задачу быстро, сможет адаптировать ее и для решения других важных проблем: «К ним относятся поиск самой большой группы друзей в Facebook, которые не знакомы друг с другом, или взлом кода, который защищает все наши операции в Интернете». По словам авторов, их статья показывает, что решение задачи о восьми ферзях эквивалентно решению одной из так называемых задач тысячелетия, а именно задачи о тождестве классов сложности Р и NP. За решение именно этой задачи Институт Клэя и обещал миллион долларов.

«Награда в один миллион долларов достанется тому, кто ответит на вопрос, возможно ли разрешить задачу быстро, так что приз достаточно велик», — добавил соавтор работы и коллега Гента, Кристофер Джефферсон.