Исследователи уверены, что для этого понадобится около тысячи лет.
Учёные из Сент-Эндрюсского университета в Великобритании бросили вызов всем, кто хочет попробовать разгадать шахматную загадку. Приз за решение загадки — миллион долларов.
«Задача о восьми ферзях» существует с 1850 года и заключается в том, чтобы расставить на стандартной 64-клеточной шахматной доске восемь ферзей так, чтобы ни один из них не атаковал другого. Вероятность решения задачи напрямую зависит от размера доски: на поле 1000 на 1000 клеток программе понадобится больше тысячи лет, чтобы разгадать головоломку.
Сотрудники университета предложили придумать алгоритм, способный решить задачу, либо доказать, что решение невозможно. Главное — это не менять размер поля, установленный на 64 клетках.
Комментарий недоступен
В чём фишка? Ферзей можно ставить только буквой Г друг к другу. Помещается только 4 на поле 8х8
Там, в общем, фишка в том, что современный метод решения такой задачи при помощи софта - обычный перебор вариантов, что, соответственно, плохо сказывается на масштабируемости задачи.
Смысл конкурса именно в разработке программы, которая будет решать задачу очень быстро по алгоритму, который можно будет использовать и при увеличении поля (при упомянутом поле 1000×1000 современные компьютеры, вроде, справиться в принципе не смогут).
Такой алгоритм, по словам авторов, можно будет использовать при решении практических организационных задач на больших предприятиях, и стоить такой алгоритм сам по себе будет дорого, если он в принципе возможен.
Сами авторы считают, что он невозможен. Поэтому такая награда.
Это вообще необоснованное утверждение с их стороны. Попахивает пиаром. Они доказали что NP полным является алгоритм который может дополнить уже существующую неполную расстановку ферзей до полной. Ну типа на доске 30х30 уже стоит 10 ферзей и надо поставить ещё 20 чтоб они друг друга не били. И совершенно не очевидно что алгоритм который может расставить 30 ферзей на пустой доске сможет решать эту задачу о дополнении быстрее чем полным перебором. Кроме того на практике нам нужно решать NP трудные задачи куда больше размерности чем 1000. Хотя это конечно уже от конкретной задачи зависит, кикието сложнее других.
Я тоже не понял сложности. В поле 16х16 ставя буквой Г, 8 ферзей спокойно умещаются.
Если ставить буквой Г в одном направлении — сложность появляется после первых 4х. Дальше пришлось штриховать, но больше 7 так и не смог поставить
Наверное, я неправильно понял, но вот что у меня вышло. Никто никого не атакует.
Комментарий недоступен
Ох лол, я почему-то подумал 64 на 64.
потому что ты миша
Поставил 7. Блэт
Алё, для 8х8 доски решено уже давным давно. Помещается 8 ферзей, мой 9-ний сын решит. А вот для большой да, можно подумать.
А можно твой сын потом мне расскажет ответ, потому что я уже сорок минут не могу это решить.
Мой сын решил
Его решение
Комментарий недоступен
Для 8 ферзей и 64 клеток эта задача решена сто лет назад. В статье говорится о доске 1000*1000
Сотрудники университета предложили придумать алгоритм, способный решить задачу, либо доказать, что решение невозможно. Главное — это не менять размер поля, установленный на 64 клетках.
Комментарий недоступен
Крайнюю правую съедает нижняя левая. Переделывай.
вообще, для 8*8 есть 92 известных решения
Комментарий недоступен
Если на четырех досках количество фигур удваивается, а не учетверяется, я это загадку решил и алгоритм придумал.
А если учетвиряется - решения у загадки не может быть даже в теории.
Я абсолютно серьезно сделал это. Но я должен понять правила.
Если кол-во фигур учетверяется они никак не смогут быть по одной на паралель. Но если удваивается, я решил это говно. TJ помоги! Если я получу свой миллион, куплю всем пожизненные комментарии!
На 4 досках удваивается, т.к. 4 доски 8х8 дадут доску 16х16 и задачу надо решать для 16 ферзей.
Вопрос ещё в том, что будет, если размер доски не является степенью двойки. Тогда решение через удвоение/учетверение может не работать
Если на доске 32X32 у меня 32 ферзи, я победил?
Да, 32 ферзя.
А если доска 29х29, то решение тоже есть?
Нет, решение есть только для досок, кратных 4.
У них в задаче 1000х1000 это кратно 4.
"Главное — это не менять размер поля, установленный на 64 клетках", так что вообще всё ок.
Это откуда? В статье, на которую дается ссылка, говорят именно о разработке программы для быстрого решения этой задачи.
Да, я чот попутал, спасибо
Комментарий недоступен