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

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

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

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

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

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

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

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

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

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

  1. uran

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

  2. nscr

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

    • PavaEai

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

      • nscr

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

        • PavaEai

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

          • nscr

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

      • nscr

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

  3. PavaEai

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

  4. RaiD

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

  5. amd212

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

  6. Ultimatemind

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

    • resurrected

      Для 1000х1000 ещё не найдено решение, институт Клэя обещает 1M за него.
      Решается долгим перебором для <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:unic8811@gmail.com]
    Sent: 03 September 2017 20:52
    To: Ian Gent ; St Andrews University Press Office ; Francesca Rossi ; Telephone Office ; ITS General Enquiries ; admissions ; dragomir.radev@yale.edu; Development Office
    Subject: Additional information

    • bari

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

    • dejli

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

      • mr Vanya

        "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

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

    • victor2017

      По моему это представлено как базовый случай ("base case").

      • victor2017

        А нет, Вы правы, это решение но это по аналогии Гамильтоновой path по моему типа конечный результат от пункта А до Б на картинке пункт "Б" но "А" это один ферзь, то есть раставить от одного до восьми ферзей алгротим нужен, да по моему это так.

  11. Dimchanski

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

  12. RikasEpta

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

  13. victor2017

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

  14. rewen

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

  15. victor2017

    По моему это действительно очень похоже на "travelling salesperson" проблему. Если представить что позиция кагдого ферзя это "node" то получается соотношение каждого ферзя между другим и можно проделать "путь" между каждого из них исходя из правила что они не могут атаковать друг друга. Это они взаимно друг с друом дожны координировать чтоб никто из них не атаковал другого. Проблема получается не polynomial тогда, больше как exponential?

  16. victor2017

    Дерево решений (decision tree)?

    • victor2017

      На мой вгляд, чтоб доказать любую P≠NP проблему лучше использовать теорию графов и показать что любой путь требует non-polynomial время. Мнения?

  17. rewen

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

  18. rewen

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

  19. Joe

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

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

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