Паззл Eternity был решен в мае 2000 года двумя математиками из Кэмбриджа, Алексом Селби и Оливером Риорданом.
Как решали. Понятное дело, не руками собирали. Полное описание можно почитать здесь, а если кратко, то они поделили многоугольники на "плохие" и "хорошие". А потом использовали поиск в ширину с эвристикой. Решение вот:
Монктон на этом не остановился и выпустил новый паззл, Eternity II, в июле 2007.
Тут уже не многоугольники надо складывать, а разноцветные квадраты с рисунком. И надо получить один большой квадрат.
Селби с Риорданом ему помогли разрабатывать второй паззл и решить Eternity II сложнее, чем предыдущий. Но и денег за него дают уже два миллиона (все еще фунтов стерлингов). Первый дедлайн по решениям был в декабре 2008, полностью паззл не решил никто, дали приз за лучшее частичное решение.
Были какие-то инициативные программисты, которые пытались решить эту задачу распределенно, но потом как-то заглохли. Может с тех пор еще кто-то появился.
Не знаю как где, но в Москве Eternity II продается, видела его в магазинах рядом со всякими настольными играми. Популярностью не пользуется. И если вам нечем заняться на выходных... Ну, вы поняли :-)
Ссылки по теме:
E2: The (NP-Complete) Kids’ Game with the $2 Million Prize
