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

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


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


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

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

На счёт институтов не скажу. Но недавно писали о том что россиянин выиграл в каком то конкурсе программистов(или машинное обучение) и ему приз не выплатили мотивируя тем что РФ находится на какой то там строке коррупционного рейтинга и участникам из стран с высоким рейтингом коррупции призовые не выплачивают. Ему приз выплатил mail.ru.
PowerBoy; корум; klinval; +3 Ответить
5. TODD22 18 06.09.17 12:51 Сейчас в теме
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 216 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с, разумеется)
как мне получить с них денег, будучи голимым резидентом сами знаете где
Оставьте свое сообщение

См. также

Госдума утвердила законопроект о бессрочное праве на кредитные каникулы

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

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

21.07.2023    749    VKuser24342747    0       

2

Открываем рубрику «Книжный клуб»: подборка полезных книг для разработчиков

Новость Развлечения, искусство, спорт Конкурс ИТ-Новость Сообщество

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

06.02.2023    9099    a_a_burlakov    46       

41

Мем недели: нейросеть ChatGPT написала диплом российскому студенту. И он его защитил

Новость Развлечения, искусство, спорт Искусственный интеллект

Студент одного из российских вузов Александр Жадан рассказал, как написал дипломную работу с помощью нейросети ChatGPT. Чат-бот генерировал текст диплома, а Александр формулировал запросы и редактировал текст нейросети.

03.02.2023    5382    user997184    6       

3

Правительство изменило условия предоставления льготной ипотеки ИТ-специалистам

Новость ИТ-компания ИТ-льготы ИТ-Новость Минцифры

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

31.01.2023    5784    VKuser24342747    9       

1

Минцифры открыло прием заявок на отсрочку от весеннего призыва

Новость ИТ-льготы ИТ-Новость Минцифры

Собирать информацию для передачи в Министерство обороны ведомство будет до 6 февраля. Право на отсрочку имеют ИТ-специалисты, работающие в аккредитованных компаниях.

24.01.2023    7105    VKuser24342747    0       

2

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

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

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

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

1

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

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

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

27.09.2022    5389    VKuser24342747    10       

4

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

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

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

16.09.2022    7832    VKuser24342747    1       

4

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

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

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

23.08.2022    6032    VKuser24342747    0       

1

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

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

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

22.07.2022    5383    VKuser24342747    0       

0

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

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

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

10.06.2022    5566    VKuser24342747    0       

2

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

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

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

10.06.2022    6703    VKuser24342747    0       

1

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

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

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

08.06.2022    5429    VKuser24342747    7       

1

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

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

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

02.06.2022    6603    VKuser24342747    5       

2

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

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

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

21.04.2022    8476    VKuser24342747    0       

4

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

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

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

24.01.2022    12940    user1015646    5       

2

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

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

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

24.01.2022    13172    user1015646    0       

0

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

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

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

18.01.2022    8374    user1015646    0       

3

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

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

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

12.01.2022    13255    user1015646    2       

4

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

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

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

30.12.2021    19048    VKuser24342747    3       

0

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

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

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

27.12.2021    18628    user1015646    3       

1

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

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

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

22.12.2021    18898    VKuser24342747    8       

3

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

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

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

21.12.2021    25820    VKuser24342747    3       

1

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

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

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

17.12.2021    22704    VKuser24342747    30       

1

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

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

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

07.12.2021    16829    VKuser24342747    1       

1