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

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


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


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

Были прецеденты?
4. TODD22 19 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 86 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 206 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с, разумеется)
как мне получить с них денег, будучи голимым резидентом сами знаете где
Оставьте свое сообщение

См. также

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

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

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

25.06.2020    883    VKuser24342747    0       

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

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

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

22.05.2020    1081    VKuser24342747    1       

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

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

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

20.05.2020    2428    user997184    1       

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

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

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

15.05.2020    1975    user1015646    8       

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

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

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

15.04.2020    1714    user1015646    0       

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

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

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

14.04.2020    1802    VKuser24342747    2       

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

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

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

10.04.2020    2361    AnastasiaKl    5       

Александр Жаров ушел из Роскомнадзора ради должности гендиректора «Газпром-Медиа»

Новость Роскомнадзор

Александр Жаров больше не возглавляет Роскомнадзор. Его место займет Андрей Липов, который руководит управлением президента по применению информационных технологий. 

25.03.2020    2019    VKuser24342747    0       

В России обсуждают введение нового вида занятости – удаленной работы

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

Если поправки примут, работники смогут трудиться дома и в офисе по одному трудовому договору.

24.03.2020    2672    ЕленаЧерепнева    7       

На карантине: Google Chrome перестанет получать обновления до апреля

Новость Google

Google временно приостановила выпуск обновлений для Chrome. Команда разработчиков браузера переведена на удаленную работу и будет заниматься лишь исправлением проблем с безопасностью.

23.03.2020    2311    VKuser24342747    6       

Минкомсвязь не хочет компенсировать затраты операторов на «бесплатный» интернет

Новость Минкомсвязь Телекоммуникации

Доступ к сайту госуслуг и другим социально значимым ресурсам обещали сделать бесплатным с 1 марта. Но запуск проекта пришлось отложить: Минкомсвязь не успела согласовать нужные документы. 

17.03.2020    2390    user1015646    6       

Фельдшерам и учителям не хватило компьютеров для подключения к интернету

Новость Образование Цифровая экономика

Школам и фельдшерским пунктам не досталось компьютеров, положенных по проекту «Цифровая экономика». Заведения так и не получили возможность выхода в интернет. 

05.03.2020    2278    VKuser24342747    4       

Умер Ларри Теслер – разработчик, придумавший команды «копировать», «вырезать» и «вставить»

Новость Искусственный интеллект Языки программирования

Ларри Теслер , скончавшийся 16 февраля 2020 года, возможно, не является всемирно известным, как Стив Джобс или Билл Гейтс, но его вклад в упрощение использования компьютеров и мобильных устройств нельзя переоценить. Ведь именно он изобрел используемые по всему миру функции «вырезать», «копировать» и «вставить».

25.02.2020    2982    user-programmist    6       

Не на своем месте: суд оштрафовал Twitter и Facebook на 4 млн рублей

Новость Роскомнадзор Судебная практика

Роскомнадзор добился наказания для Twitter и Facebook. Суд принял решение оштрафовать каждую компанию на 4 млн рублей за отказ перенести данные о пользователях в Россию.

20.02.2020    2383    VKuser24342747    9       

ФАС попросит Apple и Google очистить смартфоны для российского ПО

Новость Google

Антимонопольная служба предложила привлечь Apple, Google и Microsoft к исполнению закона об обязательной предустановке российских приложений. Компании будут отвечать наравне с производителями и продавцами устройств. 

04.02.2020    3305    VKuser24342747    30       

Почтовый сервис Protonmail заблокирован в России

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

Спецслужбы считают, что через Protonmail, рассылались ложные сообщения об угрозах минирования на территории РФ.

03.02.2020    3670    Senator_I    68       

Чешские программисты бесплатно создали сайт, на который правительство хотело потратить 16 млн евро

Новость Государственные, бюджетные структуры Госзакупки Онлайн-торговля

Власти Чехии собирались потратить 16 млн евро на создание интернет-магазина для покупки талонов на проезд по платным дорогам. Местных разработчиков возмутил объем затрат: они организовали хакатон и за выходные бесплатно создали онлайн-магазин.

03.02.2020    4476    user1015646    31       

Лучше, чем Google: «Яндекс» возглавил рейтинг лучших работодателей для студентов в России

Новость Google Образование Яндекс

Сервис поиска вакансий FutureToday составил список лучших работодателей для студентов. На первом месте рейтинга в России – «Яндекс», который в этом году смог обогнать Google. 

31.01.2020    3524    user1015646    6       

Большие перемены: назначен новый министр по цифровому развитию и связи

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

Новым главой Министерства цифрового развития, связи и массовых коммуникаций стал Максут Шадаев. Он сменил на посту Константина Носкова, который сложил полномочия в связи с отставкой правительства.

28.01.2020    3555    user1015646    16       

Готовьте ваши миллиарды: утверждены новые требования к российским DNS

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

Минкомсвязи утвердило требования к операторам связи и интернет-сервисам, выполняющим функции DNS. Такие сервисы должны будут в течение года хранить информацию о пользователях и обеспечивать время отклика не более 100 мс.

28.01.2020    4992    user1015646    0       

Всем даром: доступ к сайтам госуслуг и госорганов станет бесплатным

Новость Интернет Телекоммуникации

Уже с 1 марта зайти на сайты государственных органов и госуслуг можно будет бесплатно. Ресурсы должны открываться, даже если у вас на счете «жирный минус», заявили в Минкомсвязи.

24.01.2020    3770    user1015646    4       

Российские банки перестанут собирать биометрические данные 

Новость Банки

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

23.01.2020    3952    user1015646    5       

Назначен новый руководитель Федеральной налоговой службы

Новость Налоги ФНС

После того, как Михаил Мишустин стал премьер-министром России, Федеральная налоговая служба получила нового руководителя. Налоговое ведомство возглавил Даниил Егоров.

22.01.2020    4266    ЕленаЧерепнева    22       

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

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

Министерство экономического развития (МЭР) предлагает выделить 2,1 млрд рублей на создание российской версии GitHub.

21.01.2020    3986    AnastasiaKl    8       

Путин пообещал «бесплатный» интернет и перевод нацпроектов на отечественное ПО

Новость Импортозамещение Интернет

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

17.01.2020    5540    AnastasiaKl    27