Паззлов Eternity две штуки, сначала расскажу о первом, потом плавно перейду ко второму. Итак в 1999 году Кристофет Монктон запустил в продажу паззл Eternity за решение которого предлагал миллион фунтов стерлингов. Паззл этот состоял из 209 многоугольников, которые надо было сложить в двенадцатиугольник.
Паззл Eternity был решен в мае 2000 года двумя математиками из Кэмбриджа, Алексом Селби и Оливером Риорданом.
Как решали. Понятное дело, не руками собирали. Полное описание можно почитать здесь, а если кратко, то они поделили многоугольники на "плохие" и "хорошие". А потом использовали поиск в ширину с эвристикой. Решение вот:
Монктон на этом не остановился и выпустил новый паззл, Eternity II, в июле 2007.
Тут уже не многоугольники надо складывать, а разноцветные квадраты с рисунком. И надо получить один большой квадрат. 
Селби с Риорданом ему помогли разрабатывать второй паззл и решить Eternity II сложнее, чем предыдущий. Но и денег за него дают уже два миллиона (все еще фунтов стерлингов). Первый дедлайн по решениям был в декабре 2008, полностью паззл не решил никто, дали приз за лучшее частичное решение.
Были какие-то инициативные программисты, которые пытались решить эту задачу распределенно, но потом как-то заглохли. Может с тех пор еще кто-то появился.
Не знаю как где, но в Москве Eternity II продается, видела его в магазинах рядом со всякими настольными играми. Популярностью не пользуется. И если вам нечем заняться на выходных... Ну, вы поняли :-)
Ссылки по теме:
E2: The (NP-Complete) Kids’ Game with the $2 Million Prize
четверг, апреля 30, 2009
Паззл Eternity II
Подписаться на:
Комментарии к сообщению (Atom)
Atom feed
14 коммент.:
Предлагаю распространять данный пазл в исправительно-трудовых учреждениях нашей Родины.
Начните с Tetravex (http://en.wikipedia.org/wiki/Tetravex).
Интересно )
Если не секрет, где Вы его видели? Хотя бы примерно. Очень хочу купить.
Извините за анонимность, блога нет.
С уважением, Саша.
2Саша:Если не секрет, где Вы его видели? Хотя бы примерно. Очень хочу купить.Москва, рядом с метро Братиславская есть торговый центр Бум. В нем есть филиал Детского Мира. Вот там видела.
Спасибо Вам огромное.
С уважением, Саша.
А интересно, миллион за первый им выплатили? ;)
Иннициативным программистам видимо кто-то объяснил, что без толкового математика им не обойтись, ибо если алгоритму на работу требуется 10^100 лет, то распределение ее на 10^10 компьютеров позволит ее решить всего за 10^90 лет, что, конечно, интересней, но не сильно.
2Mark:А интересно, миллион за первый им выплатили? ;)Да.
Я не думаю, что они стали бы помогать делать второй, если бы за первый им не заплатили :-).
Логично. Хотя мне почему-то сразу вспомнилась история пятнашек :)
Впрочем в http://games.groups.yahoo.com/group/eternity_two/ какая-то активность наблюдается, хотя, если я правильно понял, месяц назад она сильно убавилась... и математики у них там тоже водятся...
Может уже нашли эффективный алгоритм и решили :)
Надо будет купить в бумаге и подарить кому-нибудь ;)
=)
Интересно правда..
А цель собрать ? Или собрать и рассказать как собрал ?
Павел.
2Павел:А цель собрать ? Или собрать и рассказать как собрал ?Насколько я помню, достаточно просто собрать.
А Eternity II вообще имеет решение? Может они один "неправильный" квадрат в набор кладут, какой резон им расставаться с 2 млн.? :-)
2Анонимный:
А Eternity II вообще имеет решение?
Насколько мне известно, существование решения (и вроде как не одного) доказано.
Может они один "неправильный" квадрат в набор кладут, какой резон им расставаться с 2 млн.? :-)
Организатор всего этого дела вообще человек странный. И довольно богатый, кстати.
Отправить комментарий