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

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


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


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

См. также

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

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

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

03.12.2021    7190    user1015646    3       

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

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

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

26.11.2021    6008    VKuser24342747    1       

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

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

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

25.11.2021    5621    VKuser24342747    1       

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

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

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

08.11.2021    4867    VKuser24342747    1       

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

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

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

22.10.2021    3170    VKuser24342747    0       

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

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

Минцифры сообщило о запуске интерактивной формы для Всероссийской переписи населения на едином портале Госуслуг. Впервые это мероприятие пройдет в цифровом формате.

15.10.2021    3971    VKuser24342747    12       

Mail.ru Group сменила название на VK ради более очевидной связи проектов компании

Новость Mail.Ru ИТ-новость Соцсети

Корпорация Mail.ru Group провела ребрендинг и сменила имя на VK в честь соцсети «ВКонтакте», которой владеет холдинг. Также обновлен логотип компании, в планах переименование и других продуктов.

14.10.2021    11108    VKuser24342747    1       

С 1 декабря в Москве стартует выдача электронных паспортов

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

Цифровые паспорта в России планируют выдавать уже с 1 декабря. Пилотным регионом станет Москва, а до 1 июля 2023 года проект распространят на всю территорию страны.

08.10.2021    10305    user1015646    12       

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

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

Платформа для проведения онлайн-соревнований All Cups провела опрос 1200 отечественных разработчиков, чтобы узнать, в каких отраслях они хотели бы развиваться как профессионалы в России и за границей.

30.09.2021    14420    VKuser24342747    1       

Свидетельства о рождении и смерти станут электронными

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

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

27.09.2021    12165    Senator_I    0       

Российский ИИ будет искать запрещенную информацию в сети

Новость Безопасность Интернет Искусственный интеллект ИТ-новость

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

23.09.2021    6000    VKuser24342747    6       

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

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

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

21.09.2021    6381    VKuser24342747    0       

ФНС добавила на Госуслуги сервис для получения выписок из ЗАГСов

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

Федеральная налоговая служба совместно с Министерством цифрового развития заявили о запуске нового сервиса на Едином портале госуслуг, который позволит получать актуальные сведения из ЗАГСа.

20.09.2021    7377    VKuser24342747    0       

На портале Госуслуг станет больше медицинских сервисов для граждан

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

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

15.09.2021    5883    VKuser24342747    3       

«Ростелеком» рекомендует не использовать сервисы DNS от Google и Cloudflare

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

«Ростелеком» разослал настоятельную рекомендацию использовать DNS провайдера или «Национальной системы доменных имен» (НСДИ) вместо аналогичных сервисов от иностранных ИТ-компаний.

15.09.2021    25249    VKuser24342747    1       

ИТ-специалисты обнаружили попытки Роскомнадзора блокировать Google и Cloudflare

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

Сразу несколько российских ИТ-исследователей нашли признаки тестирования блокировки DNS-сервисов Google и Cloudflare. По мнению экспертов, РКН использует для этого оборудование для суверенного интернета.

15.09.2021    4806    VKuser24342747    11       

И вот он настал… День программиста

Новость Инфостарт ИТ-новость

Сегодня 13 сентября, и мы традиционно поздравляем всех программистов с профессиональным, официально закрепленным на государственном уровне, праздником – Днем программиста!

13.09.2021    10460    AnastasiaKl    2       

В России появится робот для поиска нелегальных персональных данных в сети

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

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

09.09.2021    4565    VKuser24342747    1       

Биометрию начнут применять для водителей такси и пользователей каршеринга

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

Минцифры опубликовало проект постановления, в котором предлагает расширить список случаев сбора биометрии – у водителей такси, пользователей каршеринга, участников собраний и для пропуска на территорию организаций. Если постановление будет подписано, то изменения вступят в силу с 1 января 2022 года. Сейчас проходит общественное обсуждение проекта.

08.09.2021    5908    Senator_I    0       

У россиян пропал из электронной трудовой книжки стаж на ликвидированных предприятиях

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

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

08.09.2021    23425    VKuser24342747    15       

Google Play меняет систему рейтингов приложений

Новость Android Google ИТ-новость Мобильные приложения Рейтинг

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

02.09.2021    22371    user1015646    0       

Только треть россиян готова отказаться от бумажного паспорта в пользу цифрового

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

Исследование портала SuperJob показало, что из 10 россиян семеро не хотят менять свой бумажный паспорт на пластиковую смарт-карту. Максут Шадаев заявил, что в ближайшее время россиянам не нужно будет менять паспорт в обязательном порядке.

26.08.2021    6798    VKuser24342747    12       

Российский институт разработал технологию для создания интернет-сети на Крайнем Севере

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

Исследовательский институт создал технологию для беспроводного широкополосного интернет-соединения на расстоянии до 810 километров. Она может применяться в удаленных регионах России.

25.08.2021    10460    VKuser24342747    2       

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

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

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

18.08.2021    10927    VKuser24342747    0       

«Ростелеком» создаст онлайн-платформу для получения социальных выплат

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

Правительство назначило «Ростелеком» единственным исполнителем заказа на создание единой цифровой платформы для получения пенсий и соцподдержки. Запуск проекта намечен на 2023 год.

12.08.2021    10902    VKuser24342747    0