Written By Stuart Cam.

Project Page: C# Eternity II Solver on Codeplex

Subversion URL: https://eternity2.svn.codeplex.com/svn

It was a cold and overcast Boxing Day and everyone was enjoying a glass of their favourite beverage around the fire. My cousin-in-law had received an interesting present from his parents. A simple black box adorned with colourful letters and tiles: Eternity II - Solve The Puzzle And Win $2,000,000. Stacked on top were two smaller boxes of similar description.

The rules? Fill the puzzle board with the provided coloured tiles ensuring that the sides match each neighbour or edge-colour.

I watched as he opened one of the smaller boxes, snapped the 36 tiles free and began placing them on the board. Some 20 minutes later he yelled 'finished!' and rushed to the computer. He typed the tile locations into the companion web site and received the location of a single tile on the larger 256 tile puzzle. 'That should make things easier', he said.

Next was the puzzle of 72 tiles. It would take the rest of the day before he finished.

I'm not holding much hope for him finishing the 256 tile puzzle soon!

As a software developer I figured that it'd be more interesting to write a computer program to solve Eternity II style puzzles. I've put together a simple C# program which generates and then solves random boards:

The program implements a simple back-tracking algorithm (in pseudo-code):

- Randomly generates a valid board.
- Jumbles the tiles and removes them from the board.
- Places a tile onto the board in a valid position - i.e. the sides match neighbouring tiles or edge-colours.
- If there are no possible tiles left that fit the board then the previous tile is removed and alternatives are tried.
- Repeat from 3. until the board is full.

You can choose from:

- Spiral / Reverse Spiral Solver will place tiles from the outside-in or inside-out in a spiral motion.
- Row Solver will place tiles from top to bottom in rows.
- Random Solver will place tiles in random positions.

This innocuous little program would spark hours of research culminating in the conclusion that attempting to solve
the 256 tile Eternity II puzzle is *probably* a complete waste of time!

Q: What do travelling salesmen and the Eternity II puzzle have in common?

A: They are both NP Complete problems
*but more importantly, smart salesmen sell Eternity II puzzles for $50 each and offer a $2,000,000 prize!*

Although any given solution to the Eternity II puzzle can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows.

As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly is one of the principal unsolved problems in computer science today.

Finding an efficient algorithm to solve the Eternity II puzzle would also entitle you to various other prizes, not to mention notoriety in computer science and mathematics circles. The Clay Mathematics Institute is offering a significant prize to this and many other Millenium Problems.

But just how big is the Eternity II puzzle problem?

For the 256 tile puzzle there are: 256! × 4^{256} = 1.15 × 10^{661} possible tile combinations.

Slightly less when you consider that some tile positions are given to you through solving the companion puzzles.

Lets say that a desktop PC can iterate through those combinations at somewhere between 10-100 million tile placements per second. By the time you've completed the puzzle the sun will be a cold grey rock.

Below are some speculative thoughts on how to solve the Eternity II puzzle.

Targeting the software to run on a modern graphics GPU might
buy you some extra number crunching horsepower. However, 1.15 × 10^{661} is such a large number
that even a million-fold increase in computing power isn't going to translate into a tangible improvement.

Splitting the task up into smaller problems which can be offloaded into a distributed computing environment is a marginally better approach to solving the problem. If you can participate in finding aliens or curing cancer why not attempt to solve the Eternity II puzzle with your computers idle-time? However, without a better algorithm the improvement isn't all that better than the above GPU approach.

Clearly the best approach is to implement a superior algorithm. The problem is that most NP-Complete algorithms are better through approximation, whereas the Eternity II puzzle requires a definite solution. Perhaps a genetic algorithm or neural network might help?

The original Eternity puzzle was solved through the exploitation of vulnerability in how the polygons could be combined. Perhaps there is an exploit in the Eternity II puzzle in relation to the frequency and orientation of certain tile colours? Does the puzzle exhibit any chirality?

Perhaps the most out-of-the-box thinking would be to ditch the computer and start experimenting with chemical and biological alternatives. Nanotechnology scientists have already programmed DNA strands with edge-affinity to assist in building structures, could the same technique could be applied to the Eternity II puzzle?

Common sense would suggest that by solving the companion puzzles and being given the locations of tiles on the main puzzle board would make the solution easier. Wrong! Whilst the Eternity II puzzle may have multiple solutions the knowledge of where specific tiles must fit constrains the solution set, making the puzzle harder to solve.