The Unsolvable Puzzle, and How It Was Solved


The Hardest Puzzle Ever Solved

In 1985, Lord Christopher Monckton started working on a puzzle, a puzzle that ened up being of the most difficult puzzles ever devised. He spent the next 14 years working on it. He called it the Eternity puzzle.

But he wasn’t just a puzzlemaker [and viscount, and politician, and computer programmer, journalist, professional homophobe, public speaker and whatever a hereditary peer is], he was also a clever marketer. See, he offered a million pound prize for anyone who can solve it. And at the time, prize money games were popular: Who wants to be a millionaire’s board game was a best seller, and game shows had been peaking in popularity. And this game found a way to bring the promise of riches to the masses. And it worked. It became the best selling puzzle of all time, selling over 500,000 copies.

The puzzle seemed simple enough. 209 green plastic piees, each comprised of six triangles arranged in random formations. It was a packing puzzle, you had to arrange those 209 peices to fit perfectly into the dodecahedronal board. Only, there was no picture on the faces of the pieces to guide you, and since the pieces were all made of simple trianangles, you can never know if two pieces that fit together belonged together until you reached the last piece.

But this puzzle wasn’t just difficult.

From the start, Lord Monckton designed the puzzle to be impossible. To make sure it was impossible, he wrote a program to try to solve it. Since he knew his program wouldn’t be the most efficient, he made the puzzle bigger and bigger until it would take hundreds of millions of billions of years for a computer to solve.

Only, Lord Monckton had made a mistake when designing this puzzle.

After he ran simlulations to solve smaller puzzles, he made the assumption that simply making the puzzle bigger would make it harder to solve, and this was true … to a point. But after the puzzle reaches about 70 pieces, the opposite turned out to be true. As the puzzle grows past 70 pieces, the number of possible solutions grows exponentialy, and the ratio of solutions to nonsolutions tipped against his favor.

But despite that flaw, the puzzle was still virtually unsolvable.

When a person tries to solve it, they typically get stuck after placing around 150 pieces.

But Lord Monckton didn’t account for Mathmaticians trying to solve it. In fact, he actually thought it was impossible for mathematics to help solve it.

“It won’t be a computer which solves it and it won’t be a mathematician either.” Lord Monckton said in an press release.

But he was wrong on both accounts.

Two cambridge mathematicians, Alex Selby and Oliver Riordan eventually the puzzle. Alex was given a copy of the puzzle for his birthday, and after seeing someone post a near solution on a mailling list, he was convinced it was actually possible. And he recruited help from his former colleague, Oliver, who happened to be one of the top mathematicians in the world.

But we already established that the brute force method woudn’t work, even running on a thousand supercomputers, so how could they approach solving this problem?

Well, Alex was a computer programmer, and solving it without a computer never crossed his mind. It was simply a matter of making a solving program efficient enough to overcome the millions of billions of year bottleneck you’d run into with the brute force method.

To explain the first optimization they made, let’s imagine you’re loading luggage into the back of a car. What’s the best approach to do that? Well, you take the most awkwardly shaped luggage, and find a place to put it first. And it just so happened, that was the apporach Alex and Oliver started with. But which pieces were the easiest to place? Well, it turns out, you can’t tell at all by just looking at the abstract green blobs.

To answer that question, they used turned to a computer, using the brute force approach. But not with the full 209 pieces, but with random subsets of 24 pieces. By solving mini versions of the puzzle, they found the pieces which were hardest to place: every time a piece was part of a solveable grid, that piece’s score went up. After repeating that proccess millions of times, they had accurate estimtes for how easy to place each piece was. They found wavey pieces with lots of knobs are hardest to place, and pieces with straight lines are easiest.

At the same time, they took note of which region shapes were easiest to fill, and assigned them scores too using the same method. Now, armed with that knowledge, they could describe the probability of solving any given region of the puzzle with their remaining pieces.

But that alone wasn’t enough to solve the problem.

At the same time, the creator of the puzzle, Lord Monckton, was releasing hints periodically for the puzzle, telling the world where specific pieces belong in his solution. By solving other puzzles released by his company, they would mail you the location of certain pieces in the official solution.

But Alex and Oliver knew something most others failed to realize: these hints weren’t any help. See, we already know there is an exponetial number of solutions to this puzzle, and knowing where a few pieces might go is going to limit you more than help.

If you were fishing in the pacific ocean, and someone told you the exact location of a single fish in the atlantic, well that’s not going to get anybody to leave the pacific. Espcially if you think there are more total fish in the pacific.

The next innovation they made was to have their solver try to solve the hardest region of the puzzle first. The region of the puzzle most likely to have the fewest solutions meant they would fail faster on each iteration, thus speeding up the program significantly.

But even with these optimizations, the program would still be too slow to expect to find a solution. They needed a way to know when a solution wouldn’t be found ahead of time.

So, Alex and Oliver broke the puzzle into even smaller shapes. They looked at each 11 triangle grid, and found every possible path you can make between them two edges of it. They stored these results in tables, and now the program can determine instantly if those small shapes were fillable. Adding another short cut into the program.

When Alex began this journey, he was unemployed, and decided to take on this puzzle full time. And seven months after he began, he succeeded. His computer notified him of a solution. At first, he didn’t believe it. But when he told Oliver, who was away on a weekend trip while the solution was found, he also didn’t believe it. Alex spent the better part of a day verifying that the solution was real before it sunk in. For the first time since beginning the proccess, he took out the plastic puzzle that his brother had gifted him, and assembled the pieces into the cardboard frame. They had done it. They had a solution.

They were millionaires, they won. They solved the most difficult puzzle ever devised.

See, if you ask Alex, he says they got lucky. At least, they think they did. It’s possible there are more solutions than they realized, or their solver was more efficient than they thought, but regardless, they found it.

Lord Monckton had to sell his house to pay the prize money. He thought And Oliver used that prize money to buy himself a house. And Alex? Well, he probably wasn’t in a hurry to find a job after winning that much money.

Thanks for watching. If you’re interested in watching videos about weird games, please be sure to subscribe.

Leave a Reply

Your email address will not be published. Required fields are marked *

Up Next:

Why is there a Mormon Version of the Settlers of Catan?

Why is there a Mormon Version of the Settlers of Catan?