Задача о восьми ферзях на миллион

№ 36(1070), 14.09.2017 г.
В мире шахмат «задача о восьми ферзях» известна с 1850 года. Условие ее состоит в следующем: необходимо расставить 8 ферзей таким образом, чтобы они не имели возможности «напасть» друг на друга в один ход. По мнению специалистов, данная задача имеет много общего с программированием
Исследователи из британского Университета Сент-Эндрюс под руководством профессора Яна Гента предложили программистам найти простое решение этой старинной шахматной головоломки. Задача — написать программу, которая сможет решать «Задачу о ферзях» для больших досок с достаточной скоростью. Победителя ожидает солидный приз размером в миллион долларов.
Причина такой высокой награды проста — по расчетам математиков, эта задача невыполнима. Подсчитано, что на 64-клеточной (8 х 8) доске количество возможных расположений восьми ферзей равно 4 426 165 368, а число «правильных» расположений в соответствии с условиями задачи — всего 92. Однако, если доска будет иметь конфигурацию 1000 х 1000 клеток, компьютерные программы просто зависнут, не осилив гигантское количество вариантов.
По мнению профессора Гента, если будет написана компьютерная программа, которая сможет решать эту сверхзадачу с достаточной скоростью, ее можно будет адаптировать для решения многих важных проблем — в частности, для дешифровки самых сложных криптографических алгоритмов.
 

Другие материалы рубрики:

  • Бродячие собаки становятся стражами улиц

    Рекламное агентство Cheil, дочерняя компания Samsung Electronics в Бангкоке, разработало концепцию превращения бродячих городских собак в полезный элемент инфраструктуры

  • Антиводород меняет состояния

    Группе ученых, работающих в рамках программы ALPHA Европейской организации ядерных исследований CERN, впервые в истории науки удалось зарегистрировать и измерить параметры перехода атомов антиводорода из энергетического состояния 1S в состояние 2S и наоборот