Eternity II puzzle

[1][2] It was developed by Christopher Monckton and marketed and copyrighted by TOMY UK Ltd as a successor to the original Eternity puzzle.

The puzzle was part of a competition in which a $2 million prize was offered for the first complete solution.

Each puzzle piece has its edges on one side marked with different shape/colour combinations (collectively called "colours" here), each of which must match precisely with its neighbouring side on each adjacent piece when the puzzle is complete.

In this case the position and orientation of five pieces is known, giving an upper bound of 4!

Optimisation of the number of colours has been investigated empirically for smaller puzzles, bearing out this observation.

A prize of $10,000 was awarded to Louis Verhaard from Lund in Sweden for a partial solution[7] with 467 matching edges out of 480.

This includes Christopher Monckton's intended solution, which remains unpublished.

In particular, unlike the original Eternity puzzle, there are likely only to be a very small number of possible solutions to the problem.

[4] Owen estimates that a brute-force backtracking search might take around 2×1047 steps to complete.

[12] Monckton was quoted by The Times in 2005 as saying: Although it has been demonstrated that the class of edge-matching puzzles, of which Eternity II is a special case, is in general NP-complete,[13] the same can be said of the general class of polygon packing problems, of which the original Eternity puzzle was a special case.

Like the original Eternity puzzle, it is easy to find large numbers of ways to place substantial numbers of pieces on the board whose edges all match, making it seem that the puzzle is easy.