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

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

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

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

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

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

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

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

    Ответить
    • Я5 октября 2017 в 23:40

      Я писал ещё в школе на Олимпиаде по информатике в 92 году на бейсике программу по расстановке ферзей - от тогда то и занял 1 место по городу только из-за этой проги.

      Ответить
  • Я5 октября 2017 в 23:42

    И это даже близко не факториал миллиона. Очень много исключений - после постановки очередного ферзя .

    Ответить
(без регистрации)
Любопытныйфакт
Изобретателем роликовых коньков принято считать бельгийца Жан-Жозефа Мерлена. Он продемонстрировал их на лондонском бале-маскараде в 1760 году, катаясь среди публики в дорогих туфлях с металлическими колесиками и играя на скрипке. Однако эти ролики были ещё настолько несовершенны, что Мерлен не смог вовремя затормозить и врезался в стену.
Обновить
СвежиеКомментарии

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