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

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


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


Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. a_titeev 16 06.09.17 12:24 Сейчас в теме
Епрс. Такое на собеседованиях дают.
Вот - https://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens#Python
Или я чего-то не понял?
2. a_titeev 16 06.09.17 12:26 Сейчас в теме
А. Там 1000 на 1000 клеток хотят с нужной производительностью. Понятно.
Но как показывает практика - зарубежные институты русским не выплачивают :)
3. klinval 305 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 209 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с, разумеется)
как мне получить с них денег, будучи голимым резидентом сами знаете где
Оставьте свое сообщение

См. также

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

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

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

29.01.2021    2412    user1015646    3       

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

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

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

15.01.2021    1544    user1015646    7       

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

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

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

02.11.2020    2761    capitan    13       

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

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

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

04.09.2020    4110    VKuser24342747    0       

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

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

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

25.06.2020    5813    VKuser24342747    0       

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

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

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

22.05.2020    4880    VKuser24342747    1       

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

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

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

20.05.2020    8290    user997184    1       

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

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

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

15.05.2020    5334    user1015646    9       

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

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

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

15.04.2020    4621    user1015646    0       

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

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

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

14.04.2020    7168    VKuser24342747    2       

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

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

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

10.04.2020    6648    AnastasiaKl    5       

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

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

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

25.03.2020    5871    VKuser24342747    0       

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

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

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

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

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

Новость Google

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

23.03.2020    7285    VKuser24342747    6       

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

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

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

17.03.2020    5979    user1015646    6       

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

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

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

05.03.2020    5480    VKuser24342747    4       

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

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

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

25.02.2020    6300    user-programmist    6       

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

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

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

20.02.2020    5174    VKuser24342747    9       

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

Новость Google

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

04.02.2020    5640    VKuser24342747    30       

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

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

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

03.02.2020    6911    Senator_I    68       

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

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

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

03.02.2020    7065    user1015646    31       

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

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

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

31.01.2020    6437    user1015646    6       

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

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

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

28.01.2020    7720    user1015646    16       

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

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

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

28.01.2020    8473    user1015646    0       

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

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

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

24.01.2020    7718    user1015646    4