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

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


Автор:
Редактор ленты новостей


Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. a_titeev 26 06.09.17 12:24 Сейчас в теме
Епрс. Такое на собеседованиях дают.
Вот - https://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens#Python
Или я чего-то не понял?
2. a_titeev 26 06.09.17 12:26 Сейчас в теме
А. Там 1000 на 1000 клеток хотят с нужной производительностью. Понятно.
Но как показывает практика - зарубежные институты русским не выплачивают :)
3. klinval 328 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 85 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 99 08.09.17 15:22 Сейчас в теме
Так Сергей (ildarovich) уже давно решил в минимализмах 1
17. tailer2 11.09.17 13:18 Сейчас в теме
ok
допустим (!) я решил эту шнягу (на 1с, разумеется)
как мне получить с них денег, будучи голимым резидентом сами знаете где
Оставьте свое сообщение

См. также

ФНС рассказала о темпах выдачи электронных подписей по новым правилам

Новость ИТ-новость ФНС

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

18.10.2022    1707    ЕленаЧерепнева    0       

Минобороны предоставит сотрудникам ИТ-компаний отсрочку от частичной мобилизации

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

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

27.09.2022    1865    VKuser24342747    10       

Граждане смогут управлять своими персональными данными через Госуслуги

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

Минцифры намерено создать реестр, в котором будут представлены все согласия на обработку персональных данных. Россияне получат к нему доступ через Госуслуги и смогут отзывать собственные разрешения.

16.09.2022    1334    VKuser24342747    1       

В дипломах выпускников колледжей появятся QR-коды со сведениями о компетенциях

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

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

23.08.2022    1008    VKuser24342747    0       

Банки обяжут идентифицировать клиентов через биометрическую систему

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

Центробанк планирует установить обязательное условие регистрации новых клиентов – прохождение идентификации через единую биометрическую систему (ЕБС). Регулятор считает действующие методы регистрации ненадежными.

22.07.2022    1827    VKuser24342747    0       

Минцифры запустило на «Госуслугах» сервис с информацией о мерах поддержки ИТ-отрасли

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

В новом разделе можно узнать о действующих льготах и преференциях, а также ознакомиться с последними новостями о реализации проектов поддержки и нормативными документами.

10.06.2022    1931    VKuser24342747    0       

Минцифры запустит цифровые кафедры в более чем 100 вузах России

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

Глава Минцифры Максут Шадаев рассказал о старте программы дополнительного обучения студентов, школьников и взрослых, в ходе которой они смогут овладеть цифровой специальностью.

10.06.2022    2243    VKuser24342747    0       

Госдума одобрила к первому чтению упрощенное получение ВНЖ для ИТ-специалистов

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

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

08.06.2022    2021    VKuser24342747    7       

На сайте «Госуслуги» заработал справочник по льготной ипотеке для ИТ-специалистов

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

На портале работники ИТ-индустрии могут узнать, имеют ли право на получение кредита, где можно его оформить и на каких условиях. Льготная ипотека предоставляется в рамках поддержки ИТ-отрасли.

02.06.2022    2586    VKuser24342747    4       

Правительство переведет большую часть госуслуг в онлайн до конца 2023 года

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

Правительство подготовило концепцию поэтапного перехода к цифровому формату предоставления госуслуг. Россияне смогут воспользоваться сервисами в режиме 24/7.

21.04.2022    3897    VKuser24342747    0       

В России будут готовить киберспортсменов – с нормативами по бегу и приседаниям

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

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

24.01.2022    8743    user1015646    5       

«Госуслуги» интегрируют с государственной биометрической системой

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

Заходить на сайт «Госуслуг» станет проще. Единую систему идентификации и аутентификации (ЕСИА) сервиса интегрируют с «Единой биометрической системой» (ГИС ЕБС) – Минцифры заключило соответствующий контракт с «Ростелекомом».

24.01.2022    7915    user1015646    0       

Унылые пользовательские соглашения-многостраничники могут исчезнуть

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

Прочитать до конца пользовательское соглашение и понять все юридические формулировки в нем способен только действительно упорный человек. Но вскоре соглашения могут стать короче и понятнее – в США разрабатывают соответствующий законопроект.

18.01.2022    5529    user1015646    0       

Стартап с российскими корнями оценили в 17,5 млрд долларов США

Новость ИТ-новость Управление проектами

Стартап Miro, основанный выходцами из России, привлек 400 млн долларов США в рамках инвестиционного раунда С. В целом же компанию оценили в 17,5 млрд долларов.

12.01.2022    9490    user1015646    2       

Банк России с января начнет собирать обезличенные данные о денежных переводах россиян

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

Центробанк с 2022 года ужесточит контроль потенциально нелегальных платежей между физлицами. Некоторые банки сообщили о необходимости передавать личные данные граждан, но ЦБ отрицает эту информацию.

30.12.2021    15774    VKuser24342747    3       

Жители России смогут получить зарплату через СБП

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

Система быстрых платежей, запущенная в начале 2019 года, позволяет моментально переводить деньги, оплачивать товары и услуги. В 2022 году СБП начнут использовать и для выплаты зарплат – правда, пока лишь в пилотном режиме.

27.12.2021    14281    user1015646    3       

Госдума начала рассмотрение закона о базовом доходе для семей с детьми

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

В Госдуму внесен законопроект, который устанавливает обязательные выплаты для семей, в которых воспитываются дети до 18 лет. Платежи будут рассчитываться в зависимости от числа членов семейства.

22.12.2021    15465    VKuser24342747    8       

«Google Диск» не позволит расшаривать файлы, нарушающие правила сервиса

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

Сервис «Google Диск» ввел ограничение на доступ к загруженным файлам, если они нарушают политику компании. Пользователи получат уведомление, если их контент не соответствует правилам хранилища.

21.12.2021    21293    VKuser24342747    3       

В России может появиться право на отказ от интернета

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

Совет при президенте по правам человека (СПЧ) представил Концепцию по защите прав и свобод человека и гражданина в цифровом пространстве. Одно из положений документа – возможность отказаться от сетевого взаимодействия.

17.12.2021    19207    VKuser24342747    30       

На Госуслугах появилось проактивное информирование по сервисам ОМС

Новость ИТ-новость Медицина Минкомсвязь Мобильные приложения Цифровая экономика

Фонд обязательного медицинского страхования (ФОМС) совместно с Минцифры запустил услугу уведомления граждан о процессе получения медицинских услуг по ОМС.

07.12.2021    13162    VKuser24342747    1       

Крупные коммерческие сервисы подключают авторизацию через Госуслуги

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

Аккаунт на Госуслугах можно использовать, чтобы авторизоваться на популярных онлайн-площадках. Такую возможность уже открыли «Авто.ру», HeadHunter и ЦИАН.

03.12.2021    27947    user1015646    4       

«Яндекс» подключит регистрацию в своих сервисах через Госуслуги

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

Для доступа к профилю пользователи «Яндекса» смогут использовать Единую систему идентификации и аутентификации (ЕСИА), которая доступна для владельцев учетной записи на портале Госуслуг.

26.11.2021    19889    VKuser24342747    1       

Минцифры не будет превращать некоторые госуслуги в суперсервисы

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

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

25.11.2021    13516    VKuser24342747    1       

Правительство разрешило сервисам такси и каршеринга собирать биометрию водителей

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

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

08.11.2021    11843    VKuser24342747    1       

Минцифры запустит на Госуслугах сервисы для школьников и студентов

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

Минцифры намерено разрешить создавать учетную запись на едином портале Госуслуг для детей младше 14 лет. Кроме того, ведомство предложит студентам сервис электронных зачетных книжек.

22.10.2021    10605    VKuser24342747    0