Британские исследователи предложили миллион долларов за решение «задачи о восьми ферзях»

5 сентября 2017, Александр Агеев,
1
Задача о восьми ферзях

В мире шахмат «задача о восьми ферзях» известна с 1850 года. Условие ее состоит в следующем: необходимо расставить 8 ферзей таким образом, чтобы они не имели возможности «напасть» друг на друга в один ход. По мнению специалистов, данная задача имеет много общего с программированием.

Исследователи из британского Университета Сент-Эндрюс под руководством профессора Яна Гента предложили программистам найти простое решение этой старинной шахматной головоломки. Задача — написать программу, которая сможет решать «Задачу о ферзях» для больших досок с достаточной скоростью. Победителя ожидает солидный приз размером 1 млн. долларов.

Причина такой высокой награды проста — по расчетам математиков, эта задача невыполнима. Подсчитано, что на 64-клеточной (8 х 8) доске количество возможных расположений восьми ферзей равно 4 426 165 368, а число «правильных» расположений в соответствии с условиями задачи – всего 92. Однако, если доска будет иметь конфигурацию 1000 х 1000 клеток, компьютерные программы просто зависнут, не осилив гигантское количество вариантов.

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

Поделиться
Вконтакте
Комментарии  1
  • Tsykunov5 сентября 2017 в 16:03

    Даже жалко тратить время на тупую задачу. Тоже самое, что посчитать факториал миллиона.

    Ответить
(без регистрации)
Любопытныйфакт
В дворцово-парковом ансамбле Петергофа насчитывается 176 фонтанов, которые работают без единого насоса. Вода поступает в них самотёком по специально сооружённым каналам из родников Ропшинских высот.
Обновить
Рекомендуем
Конструктор сайтов - рейтинг от uGuide.ru
СвежиеКомментарии

ВойтиРегистрация
Вход
Почта:
Пароль:
Регистрация
Почта:
Имя:
Пароль: