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

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

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

    Ответить
(без регистрации)
Любопытныйфакт
На бортовых самописцах, более известных как «чёрные ящики», обычно размещена надпись: «Flight Recorder; Do Not Open» («Бортовой самописец; Не открывать»). Когда в 2010 году умер австралиец Дэвид Уоррен, изобретатель этого устройства, к его гробу прикрепили табличку: «Flight Recorder Inventor; Do Not Open».
Обновить
Рекомендуем
Конструктор сайтов - рейтинг от uGuide.ru
СвежиеКомментарии

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