MindZine - Eternity Puzzle

What is the Eternity puzzle?

The Eternity puzzle is a polygonal jigsaw puzzle with an ingenious set of pieces, developed by Christopher Monckton. There are 209 pieces to be fitted into an outline. A prize of £1,000,000 was offered for a solution.

Is the puzzle solved?

Yes. A number of people solved the puzzle before the deadline. The solution found by me and my friend Oliver Riordan (and a couple of computers) was the first submitted, and won the prize.

Can you describe or show me the pieces or solution?

No, for reasons of copyright I have to be careful; the copyright owner guards his rights. A quick description of the puzzle is that it is a kind of jigsaw but with no picture on the pieces to guide you. There are 209 pieces and they are all made up of twelve half-equilateral triangles (which people call "drafters"). Each piece is different and has no symmetry. The object is to fit them into a twelve sided figure.

Can you tell me something about yourself?

I'm 32 and originally from North West London. My father is an accountant andmy mother a teacher. I went to the local primary school and then the CityofLondon secondary school before going to TrinityCollege, Cambridge to read mathematics.

You're a mathematician?

I did a Ph. D in maths at Oxford and Cambridge, as a student of Graeme Segal . My subject is the geometrical side of modern quantum field theory (very different from fiddling with polygons, actually). Then I spent one year in the USA as a teaching and research fellowship at the University of Texas, Austin, Texas. On my return I rejoined Cambridge as a research fellow in mathematics at New Hall, where I stayed for nearly five years.

But you had had enough?

Last year I decided to give up maths because I wasn't satisfied with my research work.

As a mathematician you are naturally good with computers?

Actually that doesn't always follow. But computers have been a fairly serious hobby for me since I was 10 (and first learnt to program at a club I used to go to each week).

Tell me more.

I did once write a program (called "Polygon") to play Othello, and entered it in the first Computer Games Olympiad in 1989. I believe that event was one of the forerunners of the present MSO. It managed to come first and also beat some of the top human players of the day. It was written in assembler on an Acorn.

Are you a mind sports-orientated person?

I've always liked "mind sports", although I'm not especially good at any of them. I've put most effort into Go, my favourite game: and I'm currently 3 dan in the UK. I've also played Chess, Othello, Bridge, and Poker. I'd like to write a good Go program.

Computer games?

Not in the same way. I was once briefly linked with Eidos, the computer games publisher. Actually when I was involved with them they were a video editing company and nothing to do with computer games at all. I knew Stephen Streater from Cambridge and during some holidays I worked with him on video editing software which helped him (and others) create and float Eidos.

Well, that's a pretty broad background. Back to the puzzle solution. How did it go?

The object is to fit the 209 pieces into a twelve sided figure which is aligned to a triangular-type grid. The problem is discrete in that there are only a finite number of places you can put each piece. So it is in principle something you can attack by trying enough combinations.

If you try to put the pieces in without much thought, you'll find yourself getting stuck at maybe 150 pieces. As you place more pieces you have less freedom to place the next piece because you have fewer pieces in hand to choose from. So one needs to find a strategy that maximises the freedom to move at the later stages.

How hard is it, really?

For the specialists: it is not hard to show that in general this sort of tiling problem is NP-complete. See e.g., http://www.egroups.com/message/eternity/3988.

Which means?

Roughly it's easy - if you know the answer - and otherwise a bit unreasonable.

More exactly, it's easy to check the solution once it's proposed. Otherwise the number of possible candidate solutions for a general tiling problem with 209 pieces is almost as large as the total number of conceivable ways of combining 209 objects. And there might be no specially intelligent way of cutting down that search space.

But you can also see that as saying it all depends on what kind of "tiles" you use as pieces. Squares are easy, everyone can do equilateral triangles or regular hexagons. After that much, this is a big subject called tesselation about which whole books are written.

The worst case is pretty bad, and if one could solve it in reasonable amounts of computer time, for whatever types of pieces to tile together, that would unexpectedly solve many other problems. The one that's always quoted is the "Travelling Salesman", for some reason, but there are knapsack problems and many other famous ones.

And then there's some interesting middle ground. You could say that's why Eternity was intriguing. The pieces all fitted on a triangular background (isometric graph paper) but were certainly neither too easy to get all placed together, nor entirely devoid of simplifying structure.

How did you come to the puzzle?

In June 1999 the puzzle was launched and my brother Matthew bought me a copy, for my birthday. I didn't really think about it until November 1999 when David Moore and Mark Owen visited my house and sneakily typed the pieces into my computer while I was out for the evening. When I got back they got me involved with it. I was quite intrigued. I assumed that a puzzle with such a large prize would be unsolvable, but after looking into it a bit, it seemed that it might be doable.

How did you set about it?

We noticed there was a discussion group on Eternity on the internet (http://www.egroups.com/messages/eternity) and that a few of the people there had made what looked like quite a lot of progress, in that they had placed 206 or 207 pieces by then. That was interesting because it suggested that it might both be doable and not yet done. Of course we couldn't know that there weren't other people somewhere in the world who had already solved it who just hadn't posted to that discussion group.

At some point you started to work with Oliver Riordan.

Oliver was in the US at this time. He returned in January 2000 and I asked him to help me out with Eternity. He's an old friend.

And also a mathematician?

He's a research combinatorialist, making his field rather closer to this sort of puzzle than mine is. He's 28, educated at St Paul's public school and Cambridge. He did a PhD with Bela Bollobas and then a year in the States at Memphis, Tennessee before returning to Cambridge to take up a research fellowship at Trinity College. He's has been there since 1997.

But the race was on?

Soon after that (1st February) someone called Luigi Cerutti announced on the discussion group he'd found a 208-piece partial solution. Not only that - it had a piece-shaped hole (not the right piece of course). That clearly meant something: if he could repeat that 1000 times he would probably get a solution. It seemed the rest-of-the-world was very close, and we spent most of the next few months expecting him or someone else to announce a solution and spoil our fun. Even when we finally found a solution on May 15th we thought he or someone else might already have one. But apparently not - we were the lucky winners, although we had to wait several long months before we could finally be sure of this.

In fact we learnt very recently (around 28th October 2000) that the person who was to turn out to be our closest rival had already placed 208 pieces by September 1999! (Of course one should realise that the last piece may well be the hardest. It depends on your method, but it could be that you need to find 1000 208-piece partial solutions before you expect to come across a complete solution.)

How exactly did you apply computer power?

I'm currently in the process of writing up a fairly detailed description of our methods. That should be ready in a day or two from my website http://www.archduke.demon.co.uk but may not be all that interesting to non-Eternity aficionados. Here are some links for the real fans:

For the time being various silly pictures of me, Oliver, the puzzle, and associated props can be found at http://www.myles.co.uk/eternity/eternitypic03.zip and http://www.egroups.com/message/eternity/6610.

A good description of the puzzle plus other links can be found at Brendan Owen's page which is http://www.geocities.com/ResearchTriangle/System/1104/index.html

There is a discussion board/mailing list at http://www.egroups.com/messages/eternity

And now it's all public knowledge, what have you found out about the opposition?

An angle that has been missed by all other reports is that there is one other known solver of this puzzle (the inventor doesn't count because it is easy to create the puzzle simultaneously with its solution). He's the person I referred to before to as "our closest rival", his name is Guenter Stertenbrink and he comes from Germany. He solved it at the beginning of July 2000. He's a former chess player - a correspondence-chess GM. For some more background on him, see for example http://www.egroups.com/message/eternity/5414 and http://www.egroups.com/message/eternity/5798.