Eternity II

The Eternity II Puzzle

So we received the puzzle that to-date, no one has been able to solve. For those of you not familiar with the puzzle, it a 256 piece puzzle with 23 different patterns on the pieces. The goal of the puzzle is to assemble the puzzle so that all of the edges align with they gray pattern on the edges. Oh yeah, when this came out on 2007, the first person to solve it my Dec 30th 2010 would be awarded 2 million dollars. The date has come and gone, and no one solved it. If you think it would be a simple issue of getting a bunch of computers together to try each possible placement, it wont happen. The number of possibilities is :


Here is a small 4x4 example (The actual puzzle is 16x16)

4x4 Example of how the pieces go together correctly and a "solved" pattern.

So there are a lot of smart people out there working on this project. Here are a couple of links to work I find will be basing my work off of:


Trying to solve using Genetic Algorithm (why I am doing this)
http://spectrum.library.concordia.ca/7487/1/Niang_MASc_S2011.pdf

Using Tabu Search
http://www2.lifl.fr/meta10/proceedings/meta20100_submission_161.pdf

Basics Heuristics of automatic puzzle solving by a robot
http://www.parc.com/content/attachments/global_approach_automatic_4365_parc.pdf

Edge Matching
http://peekaboo-vision.blogspot.de/2012/05/graphcuts-for-python-pygco.html

Quantum Computing Approach
http://www.dwavesys.com/en/dev-tutorial-e2.html

Open source Generic Genetic Algorithm Project
http://code.google.com/p/genericga/

How to implement a GA in C#
http://www.c-sharpcorner.com/UploadFile/mgold/GeneticAlgorithm12032005044205AM/GeneticAlgorithm.aspx

Tabu Search
http://en.wikipedia.org/wiki/Tabu_search

Tabu Search Program
http://code.google.com/p/eternity-tabu/downloads/detail?name=eternity

Travelling Salesman Problem
http://en.wikipedia.org/wiki/Travelling_salesman_problem

Eternity II C# solver
http://www.codebrain.co.uk/work/eternity2.aspx



I will be updating this page with the progress!