Шахматная задачка стоимостью миллион долларов

4 Сентября 2017 в 18:45, Владимир Кузнецов 14 647 просмотров 30

Одна из самых древних настольных игр шахматы позволяет не только развить тактическое мышление, но и усовершенствовать другие полезные навыки. К примеру, существует масса логических задачек по расстановке фигур на шахматной доске в определенной последовательности. И за решение одной из них исследователи из Сент-Эндрюсского университета (Великобритания) предлагают миллион долларов.


Разбогатеть поможет вариация загадки под названием «задача о восьми ферзях». В оригинале формулировка звучит следующим образом: расставить на стандартной шахматной доске размером 64 на 64 клетки 8 ферзей так, чтобы ни один из них не находился под ударом другого. То есть, исходя из того, что ферзь бьёт все клетки, расположенные по вертикалям, горизонталям и диагоналям, на «пути» каждого из них не должно быть других фигур. При должном старании найти решение сможет практически любой человек и было бы странно, если бы за решение именно этой задачи ученые давали бы миллион (тем более, что известна задачка еще с середины 19 века). Сложности начинаются тогда, когда мы решим увеличить количество клеток и фигур на поле.

Логично предположить, что чем больше поле — тем сложнее найти решение. И тут ученые решили подключить к поиску решения компьютер. Но столкнулись с другой проблемой: когда размер доски переваливает за 1000 на 1000 клеток, компьютер зависает. Поэтому эксперты предложили всем желающим разработать алгоритм для решения задачи, либо доказать, что его не существует вовсе. По мнению исследователей, тот, кто будет способен написать подобную программу, сможет и модифицировать ее и для решения других более важных задач.

Основано на материалах «РИА-Новости»

Шахматная задачка стоимостью миллион долларов

Приложение
Hi-News.ru

Новости высоких технологий в приложении для iOS и Android.

30 комментариев

  1. uran

    Есть же бездельники (отправлено из приложения Hi-News.ru)

  2. nscr

    Поставить зеркала со всех четырех сторон.

    • PavaEai

      nscr, И как же в этом случае ферзь отраженный сам себя не бьет? (отправлено из iOS приложения Hi-News.ru)

      • nscr

        PavaEai, Да я просто наугад ляпнул ; ))) Типа если их позиции во всех четырех зеркалах не совпадают.

        • PavaEai

          nscr, Как мысль хорошо, но тут не рабочий вариант. Да сдвигать клетки будет такой вариант (отправлено из iOS приложения Hi-News.ru)

          • nscr

            PavaEai, Я думаю при критическом увеличение количества клеток использование клеток в расчете позиции теряет смысл, с таким же успехом ферзи могут стоять на пустом поле и бить во все стороны хаотично. (ща меня побьют ; ))) )

      • nscr

        PavaEai, Ну или прилепите к ним лазеры : )

  3. PavaEai

    Звучит слишком просто. Первокурсник мехмата решит задачу мне кажется. Надо попробовать, алгоритмы поиска пути я писал достойные, а тут еще и платят за это) (отправлено из iOS приложения Hi-News.ru)

  4. RaiD

    Я думаю ии справиться (отправлено из приложения Hi-News.ru)

  5. amd212

    DeepBlue решит за пару миллисекунд :-)

  6. Ultimatemind

    Сама задача решена давно 1000х1000, вопрос в том как заставить компьютер, не знающий результата, мгновенно найти его.

  7. qwer12342011

    Если честно, то я уже расставлял фигуры в квадрате 1000000 на 1000000. Поместилось на доске в аккурат 1000000 ферзей....

  8. Ce3apyc

    Победителем окажется чемпион по тетрису;)

  9. RiotMakeR

    мною было доказано, что такого алгоритма быть не может и вот, что в ответ я получил из того института:
    Thank for your interest in the St Andrews researchers’ work on the n-Queens Completion problem.

    There has been some confusion about the $1m prize offered by the Clay Mathematics Institute in America. Professor Ian Gent has written some comments about this point which were quoted by the Clay Mathematic Institute in a news item about this work, which might clarify matters.

    We have copied Prof Gent in on this reply.

    http://claymath.org/events/news/8-queens-puzzle



    From: Anton Troyan [mailto:[email protected]]
    Sent: 03 September 2017 20:52
    To: Ian Gent ; St Andrews University Press Office ; Francesca Rossi ; Telephone Office ; ITS General Enquiries ; admissions ; [email protected]; Development Office
    Subject: Additional information

    • bari

      RiotMakeR, Короче, пендостанцы как всегда всех на....бали.

    • dejli

      RiotMakeR, А можно перевод для особо одаренных (отправлено из приложения Hi-News.ru)

      • mr Vanya

        dejli, "What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists"
        Для получения миллиона надо либо доказать что есть алгоритм решающий задачу расстановки n-Queens для любого n в полиномиальное время, либо опять-таки доказать что такого полиномиального алгоритма находящего решения нет.

        Что конкретно доказал Riotmaker в ссылках не указывается.

  10. Shoma05

    Вам не кажется что решение есть на картинке уже ?

    • Fotnstar

      Shoma05, Там же написано, что решение есть и уже давно. И да, решение на картинке показано.

  11. Dimchanski

    Что то я не пойму в чём сложность... не обязательно ведь так размещать... есть вариант гораздо проще разместить

  12. RikasEpta

    А какой практический смысл этого?)

  13. rewen

    Алгоритм прост и знаком любому кто хоть немного с бейсиком знаком ,, if then,, + таймер + запрет и функция перевыполнения до максимально возможной канцентрации ферзей на заданной территории что и будет конечным результатом данного цикла, колличество клеток не имеет значения, так как при каждом новом ферзе сокращается колличество клеток на которые можно поставить фигуру, цыкл работает не на наращивание вариантов а в обратном направлении, .
    Код не воспроизведу поэтому и за лямом не пойду)

  14. rewen

    Постите за каламбур,, скорее антиграфов,, т. К. Точки не должны соединяться при определенных условиях или наоборот соединяться со всеми возможными(при том что из точки выходит 8 лучей) кроме следующей n*

  15. rewen

    Я может что то упустил а сколько ферзей надо расставить на поле 1000х1000

  16. Joe

    На стандартной шахматной доске 64 клетки - 8х8 (отправлено из приложения Hi-News.ru)

Новый комментарий

Для отправки комментария вы должны авторизоваться или зарегистрироваться.