В Британии предложили 1 млн долларов за алгоритм решения шахматной головоломки

05.09.2017     
Группа исследователей из Сент-Эндрюсского университета в Великобритании объявила, что заплатит 1 млн долларов программисту, который сможет решить старинную шахматную задачу о восьми ферзях. Об этом сообщается на официальном сайте университета. 
 
Эта задача известна с 1850 года. Ее суть в том, чтобы расставить на стандартной шахматной доске в 64 клетки восемь ферзей таким образом, чтобы ни один из них не мог атаковать другого. 
 
Такую задачу может решить и обычный человек, но если усложнить условия – увеличить размер поля и количество фигур, то с головоломкой способен справиться только компьютер. Однако при увеличении игрового поля до 1000 на 1000 клеток, программа уже не в состоянии справиться с задачей – возникает так много вариантов решения, что на их рассмотрение может уйти несколько лет. 
 
В связи с этим ученые предложили всем желающим попробовать придумать алгоритм для решения задачи или же доказать, что его не существует в принципе. Как считают исследователи, тот, кто сможет решить задачу, смог бы адаптировать свое решение для других более важных повседневных проблем, с которыми человечество сталкивается ежедневно. 


Автор:
Яна Казьмина Редактор ленты новостей


Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. a_titeev 20 06.09.17 12:24 Сейчас в теме
Епрс. Такое на собеседованиях дают.
Вот - https://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens#Python
Или я чего-то не понял?
2. a_titeev 20 06.09.17 12:26 Сейчас в теме
А. Там 1000 на 1000 клеток хотят с нужной производительностью. Понятно.
Но как показывает практика - зарубежные институты русским не выплачивают :)
3. klinval 310 06.09.17 12:40 Сейчас в теме
(2) Я понял так: компьютеры по существующим алгоритмам виснут на 1000x1000. Т.е. вычислить не удалось даже на мощных компьютерах. Поэтому хотят новый алгоритм.
Но как показывает практика - зарубежные институты русским не выплачивают :)

Были прецеденты?
4. TODD22 18 06.09.17 12:49 Сейчас в теме
(3)
Были прецеденты?

На счёт институтов не скажу. Но недавно писали о том что россиянин выиграл в каком то конкурсе программистов(или машинное обучение) и ему приз не выплатили мотивируя тем что РФ находится на какой то там строке коррупционного рейтинга и участникам из стран с высоким рейтингом коррупции призовые не выплачивают. Ему приз выплатил mail.ru.
PowerBoy; корум; klinval; +3 Ответить
6. user605683_a_titeev 06.09.17 18:25 Сейчас в теме
(3) ну да, там рекурсия дикая с огромным расходом памяти... Интересно, сколько циклов 1с выдержит :)
7. HolodZar 07.09.17 08:11 Сейчас в теме
это блин прям террористический акт какой-то. сколько сейчас программистов начнут вместо работы расходовать своё мыслетопливо на головоломку :))))))))))))))
Nik_novosib; dimasstiy; GAMLET; +3 Ответить
8. Kosstikk 87 07.09.17 15:02 Сейчас в теме
Я бы скорее эту задачу отнес к математикам. Есть такой интересный ресурс "Проект Эйлера" http://euler.jakumo.org/problems.html
Где предлагается решать различного рода задачи, решение которых "стандартным" путем - не эффективно, так вот, когда увлекался - это происходило примерно так - нужно было найти какое-то красивое математическое решение задачи, после которого она вычислялась не 2 часа, а 5 секунд, далеко не продвинулся, но значимость математики в программировании тогда до меня дошла )
9. Tsprogrammist1 84 07.09.17 15:38 Сейчас в теме
какое количество фигур? при доске 1000 на 1000?
11. spacecraft 07.09.17 17:59 Сейчас в теме
(9) элементарно же. 1000 фигур.
13. spacecraft 07.09.17 19:16 Сейчас в теме
(11) Пересчитал по алгоритму. Для 1000 на 1000 только 999 ферзей можно разместить.
Может это вызывает проблему? Типо доказать, что нельзя 1000 разместить?
14. kauksi 211 08.09.17 08:44 Сейчас в теме
(13) рекомендую ознакомиться с библиографией по проблеме а потом кричать "элементарно"
http://liacs.leidenuniv.nl/~kosterswa/nqueens/index.html
15. spacecraft 08.09.17 09:11 Сейчас в теме
(14) давайте сначала определимся с понятиями. В новости было сказано про алгоритм расположения ферзей. Есть простой алгоритм гарантированного расположения ферзей на доске любого размера. Он гарантированно даст количество возможных фигур на доске.
На что вы ссылаетесь, это работы по поиску всех возможных вариантов расположения. Это несколько другое.
10. tailer2 07.09.17 17:36 Сейчас в теме
похоже на сетку простых чисел
12. spacecraft 07.09.17 18:01 Сейчас в теме
вообще не понимаю проблемы. алгоритм же простейший. Ограничение только на память, где хранить расположение фигур. Ну и кол-во рядов должно быть четное и равно кол-ву столбцов.
16. i.c.h 114 08.09.17 15:22 Сейчас в теме
Так Сергей (ildarovich) уже давно решил в минимализмах 1
17. tailer2 11.09.17 13:18 Сейчас в теме
ok
допустим (!) я решил эту шнягу (на 1с, разумеется)
как мне получить с них денег, будучи голимым резидентом сами знаете где
Оставьте свое сообщение

См. также

В России прирост стартапов по разработке ПО упал до ста новых компаний в год

Новость Аналитика ИТ-новость Стартапы

Некоммерческая ассоциация «Руссофт» провела исследование российского рынка разработки. Эксперты установили, что за последние пять лет в этой отрасли ежегодно появляется около 100 новых устойчивых компаний.

22.07.2021    931    VKuser24342747    2       

На московском хакатоне разработчики со всей России поборолись за миллионы рублей

Новость Искусственный интеллект ИТ-новость Стартапы Цифровая экономика

В Москве подведены результаты онлайн-хакатона Moscow City Hack. По итогам 72-часового конкурса победили получили крупные денежные призы и дорогостоящие гранты на обучение.

16.07.2021    748    VKuser24342747    1       

Исследование: компаниям не хватает сотрудников, разбирающихся в старых технологиях

Новость Аналитика ИТ-новость

Исследование Advanced Software показало, что многие крупные ИТ-компании испытывают сложности с передачей знаний о старых технологиях и не могут нанять специалистов для поддержки легаcи-проектов. 

08.07.2021    1172    user1015646    16       

Минцифры в этом году представит стратегию развития открытого ПО в России

Новость Законодательство

Министерство цифрового развития совместно с ИТ-бизнесом занимается разработкой стратегии развития open source в стране. Об этом рассказал заместитель министра связи Максим Паршин.

01.07.2021    755    VKuser24342747    0       

Исследователи рассказали, как уровень кибербезопасности снизился из-за пандемии

Новость Безопасность ИТ-новость

Из-за перехода на удаленку многие специалисты завели десятки новых аккаунтов. Эксперты IBM установили, что это негативно сказалось на уровне безопасности в интернете.

24.06.2021    2294    user1015646    0       

Минпросвещения начало эксперимент по внедрению электронных досье в детских садах

Новость ИТ-новость Цифровая экономика

Минпросвещения приступило к разработке системы, которая позволит собирать и хранить данные о школьниках и студентах. Цифровой профиль будет создан сразу же после зачисления ребенка в детский сад или первый класс.

11.06.2021    1916    VKuser24342747    0       

GitHub узнал, как совещания влияют на работоспособность программиста

Новость GitHub Аналитика ИТ-новость

GitHub провел исследование, чтобы выяснить, действительно ли отрыв от работы для обсуждения задач влияет на работу разработчиков. Анализ показал, что отвлечение в течение дня сильно снижает продуктивность сотрудника.

31.05.2021    3482    VKuser24342747    3       

Google показал фото новых офисов и рассказал о гибридном графике

Новость Google ИТ-новость

Google переводит сотрудников на гибридный график работы: три дня в неделю сотрудники будут работать из офиса, два дня в неделю – из дома. Поисковый гигант пересмотрел свои политики организации команд и показал обновленные офисы.

25.05.2021    5851    user1015646    0       

Осторожно, бонусы: компания устроила сотрудникам необычную проверку кибербезопасности

Новость Безопасность Интернет ИТ-новость

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

19.05.2021    2973    user1015646    4       

Минцифры переводит портал «Госуслуги» на отечественный софт

Новость Импортозамещение ИТ-новость Минкомсвязь Облачные технологии Цифровая экономика

В Министерстве цифрового развития рассказали о доступности бета-версии нового портала и планах дальнейшего развития. Наиболее заметные нововведения – новая ИТ-архитектура и полный отказ от поиска.

05.04.2021    8195    ЕленаЧерепнева    4       

Обладательница фамилии True полгода не может войти в аккаунт Apple iCloud

Новость Интернет ИТ-новость

Девушка по имени Рэйчел Тру (Rachel True) рассказала, что не может залогиниться в своей учетной записи Apple. Система авторизации iCloud преобразовывает ее фамилию в логический тип данных.

12.03.2021    10036    VKuser24342747    1       

Эксперты рассказали, почему вместе с Twitter замедлился GitHub и десятки других сайтов

Новость GitHub ИТ-новость Соцсети

Роскомнадзор впервые ограничил скорость доступа к сайту. Но, помимо Twitter, замедлились и другие ресурсы, например, GitHub, Reddit, Steam, Microsoft. Аналитики рассказали, почему так произошло.

11.03.2021    6154    user1015646    1       

Роскомнадзор замедлил работу Twitter в России

Новость Законодательство ИТ-новость Роскомнадзор Соцсети

Роскомнадзор с 10 марта начал замедлять работу Twitter в России. Причина ограничений – соцсеть игнорирует требования регулятора и не удаляет противоправный контент. 

10.03.2021    10110    SeiOkami    19       

Исследование: как пандемия изменила ожидания ИТ-шников от профессии

Новость ИТ-новость Цифровая экономика

Из-за пандемии коронавируса и ускоренной цифровой трансформации ИТ-специалисты испытывают повышенный стресс на работе. Большинство опрошенных с трудом переключается на личные дела в конце дня и чаще конфликтует с коллегами.

04.03.2021    6788    VKuser24342747    3       

Умер создатель Objective-C. Расскажем о его вкладе в развитие языков программирования

Новость ИТ-новость Языки программирования

Разработчик Брэд Кокс скончался на 76 году жизни. Вместе с Томом Лавом Кокс создал язык программирования Objective-C, который используют преимущественно для разработки приложений для macOS и iOS.

29.01.2021    6670    user1015646    3       

Разработчик может лишиться доступа к 280 млн долларов в биткоинах из-за забытого пароля

Новость Безопасность ИТ-новость

Новый год для мира криптовалют начался с подъема: биткоин пробил отметку в 40 тыс. долларов. Разработчик из Сан-Франциско Стефан Томас испытывает по этому поводу противоречивые чувства: он забыл пароль доступа к 7 тыс. биткоинов.

15.01.2021    4331    user1015646    7       

Сотрудники на удаленке чувствуют себя более измотанными, чем при работе в офисе

Новость ИТ-новость Новости компаний

Анонимный опрос, проведенный сервисом Blind, показал, что 68% технических работников на удаленке чувствуют себя более измотанными, чем когда они работали в офисе.

02.11.2020    5833    capitan    14       

Минэкономразвития предложило проактивное оказание госуслуг

Новость Автоматизация ИТ-новость Цифровая экономика

Портал госуслуг может начать предугадывать, какие сервисы понадобятся гражданам. Органы власти заранее подготовят необходимые документы для замены паспорта, прописки ребенка и других типовых задач.

04.09.2020    7711    VKuser24342747    0       

SuperJob проанализировал зарплаты выпускников российских ИТ-вузов

Новость ИТ-новость Образование

Сервис по поиску работы SuperJob составил список отечественных вузов, выпускники которых получают наиболее высокие заработные платы после окончания обучения. 

25.06.2020    9867    VKuser24342747    0       

Минфин раскритиковал планы Минкомсвязи по субсидированию онлайн-образования

Новость Образование

Министерство связи хочет выделить 300 млн рублей компаниям, предлагающим услуги онлайн-образования. Минфин опасается, что часть этих денег могут получить развлекательные и игровые сайты. 

22.05.2020    8405    VKuser24342747    1       

Боремся с «ленивой самоизоляцией»: цикл публикаций от Елены Дуюн на Infostart.ru

Новость Обучение, бизнес-тренинг, курсы

Организация работы в период пандемии – ценный опыт, которым нужно делиться. Продолжаем обсуждение вместе с бизнес-психологом, консультантом по подбору и развитию персонала – Еленой Дуюн. 

20.05.2020    14670    user997184    1       

Мир после коронавируса: российские компании не сохранят удаленку, США – наоборот

Новость Новости компаний

Многие компании вынуждены были полностью или частично перейти на удаленный формат работы. Но после снятия карантинных ограничений большая часть российских работодателей намерена вернуть сотрудников в офисы. В США ситуация противоположная.

15.05.2020    9689    user1015646    9       

Все.онлайн: в России запущен каталог бесплатных ресурсов для людей в самоизоляции

Новость Госдума Интернет

В России заработал портал, на котором собраны бесплатные ресурсы: развлекательные, образовательные и информационные. Они помогут провести время продуктивно, отдохнуть, заказать товары онлайн.

15.04.2020    8016    user1015646    0       

Минкомсвязи представило приложение для получения QR-пропусков на время карантина

Новость Минкомсвязь Мобильные приложения

В магазинах мобильных приложений появилась программа для получения QR-пропусков во время самоизоляции. В Минкомсвязи сообщили, что решение будет использоваться по всей России, кроме Москвы. 

14.04.2020    11365    VKuser24342747    2       

Опубликован список сайтов «бесплатного интернета»

Новость Интернет Минкомсвязь

Эксперимент продлится с 1 апреля по 1 июля 2020 года. Предполагается, что потоковое видео с сайтов при бесплатном доступе грузиться не будет.

10.04.2020    10589    AnastasiaKl    5