четверг, апреля 30, 2009

Паззл Eternity II

Паззлов 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

14 коммент.:

Diman комментирует...

Предлагаю распространять данный пазл в исправительно-трудовых учреждениях нашей Родины.

sasha комментирует...

Начните с Tetravex (http://en.wikipedia.org/wiki/Tetravex).

badcoder комментирует...

Интересно )

Анонимный комментирует...

Если не секрет, где Вы его видели? Хотя бы примерно. Очень хочу купить.

Извините за анонимность, блога нет.
С уважением, Саша.

Алёна комментирует...

2Саша:Если не секрет, где Вы его видели? Хотя бы примерно. Очень хочу купить.Москва, рядом с метро Братиславская есть торговый центр Бум. В нем есть филиал Детского Мира. Вот там видела.

Анонимный комментирует...

Спасибо Вам огромное.

С уважением, Саша.

Mark комментирует...

А интересно, миллион за первый им выплатили? ;)

Иннициативным программистам видимо кто-то объяснил, что без толкового математика им не обойтись, ибо если алгоритму на работу требуется 10^100 лет, то распределение ее на 10^10 компьютеров позволит ее решить всего за 10^90 лет, что, конечно, интересней, но не сильно.

Алёна комментирует...

2Mark:А интересно, миллион за первый им выплатили? ;)Да.
Я не думаю, что они стали бы помогать делать второй, если бы за первый им не заплатили :-).

Mark комментирует...

Логично. Хотя мне почему-то сразу вспомнилась история пятнашек :)

Впрочем в http://games.groups.yahoo.com/group/eternity_two/ какая-то активность наблюдается, хотя, если я правильно понял, месяц назад она сильно убавилась... и математики у них там тоже водятся...
Может уже нашли эффективный алгоритм и решили :)

Mark комментирует...

Надо будет купить в бумаге и подарить кому-нибудь ;)

Анонимный комментирует...

=)
Интересно правда..

А цель собрать ? Или собрать и рассказать как собрал ?

Павел.

Алёна комментирует...

2Павел:А цель собрать ? Или собрать и рассказать как собрал ?Насколько я помню, достаточно просто собрать.

Анонимный комментирует...

А Eternity II вообще имеет решение? Может они один "неправильный" квадрат в набор кладут, какой резон им расставаться с 2 млн.? :-)

Алёна комментирует...

2Анонимный:

А Eternity II вообще имеет решение?

Насколько мне известно, существование решения (и вроде как не одного) доказано.

Может они один "неправильный" квадрат в набор кладут, какой резон им расставаться с 2 млн.? :-)

Организатор всего этого дела вообще человек странный. И довольно богатый, кстати.