Наука

Миллион долларов за разгадку шахматной головоломки

4 сентября 2017 1

шахматная доска

Источник: pixabay.com

Группа исследователей из Университета Сент-Эндрюс в Великобритании предложила 1 млн долл. тому, кто сможет разгадать старинную шахматную загадку, а именно задачу о восьми ферзях (Eight queens puzzle). Чтобы решить головоломку, необходимо расставить восемь ферзей на стандартной шахматной доске в 64 клетки, причем ни одна фигура не должна атаковать другую, говорится на официальном сайте вуза.

Задачу усложнили: размер доски увеличен

Отметим, что найти ту или иную расстановку, удовлетворяющую первоначальному условию задачи, не так трудно. Поэтому ученые решили усложнить правила, а именно увеличили размер доски до 1000 на 1000 клеток, а также и количество фигур: с 8 до 1000. К слову, пока с этой головоломкой не может справиться даже компьютер.

Напишешь программу — сможешь решить и другие задачи

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

«Среди них есть и тривиальные проблемы, такие как поиск друзей в Facebook, не знающих друг друга, или очень важные задачи, например взлом кодов, обеспечивающих безопасность всех наших онлайн-операций», — говорит руководитель проекта, профессор Ян Генте.

Немного истории                                              

Напомним, что впервые задачу о восьми ферзях сформулировал в 1848 г. немецкий шахматист М. Беццель. В июне 1850 г. доктор Ф. Наук опубликовал 60 решений. Чуть позже великому математику К. Гауссу удалось найти 72 позиции. Однако вскоре его результат был перекрыт все тем же Науком, который сумел расставить фигуры 92 способами. В 1874 г. английский математик Д. Глэшер доказал, что решений больше не существует. Однако эксперты до сих пор пытаются опровергнуть это утверждение, но пока безуспешно.


Денис Сапожников

специалист по информационной безопасности

На любого теоретика рано или поздно найдется свой практик, в частности по большим вычислительным мощностям. Мы рано или поздно придем к решению таких глобальных задач, стоит хотя бы вспомнить о том, как изменилась ориентация вычислительных мощностей CPU и GPU. Развитие нейронных сетей также не стоит на месте, поэтому данную задачу в итоге решить удастся. Однако отмечу, что человеку без компьютера этого не сделать, равно как и компьютер без человека ее не решит.

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

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Рассказать друзьям

1 Комментариев

Подписаться на рассылку

Комментарии

Войти с помощью 

Присоединяйтесь к нам в социальных сетях

В наших группах вы можете узнать много нового и интересного, а так же - принять участие в опросах и конкурсах

Присоединиться
Присоединиться