Tantrix: P=NP?

You can find computer science everywhere - even in popular Solitaire games and puzzles. Most people play games like Tetris, Battleships, Mastermind, Tantrix and Minesweeper at some point. In fact all these games have a link to one of the deepest, fundamental problems remaining in Computer Science. They are all linked to a famous equation that is to do with the ultimate limitations of computers.

The sciences have many iconic equations that represent something fundamental about the world. The most famous is of course Einstein's E=mc², which even non-scientists have heard of. The most famous equation in computer science is 'P=NP'. The only trouble is no one has yet proved whether it is true or not! There is even a million dollar prize up for grabs for anyone who does, not to mention great fame!

P=NP boils down to the difference between checking if someone's answer to a puzzle is correct, as against having to come up with the answer in the first place.

You are so NP!

Computer Scientists call problems where it is easy to check answers 'NP problems'. Ones where it's also easy to come up with solutions are 'P problems'. So P=NP, if it were true, would just mean that all problems that are easy to check are also easy to solve.

Let's take Tantrix rotation puzzles to see what it is all about. Tantrix is a popular domino-type game using coloured hexagonal pieces like the ones in the image. The idea of a Tantrix rotation puzzle is that you place some tiles randomly on the table in a connected pattern. You are then not allowed to move the position of any piece. All you can do is rotate them on the spot. The problem is to rotate the pieces so that all the coloured lines match where tiles meet - red to red lines, blue to blue lines and so on.

Have a go at the Tantrix rotation puzzle above before you read on.

Easy to check?

A solution is here if you want to check it. In fact you can quickly check any claimed rotation puzzle 'solution'. All you do (the checking 'algorithm') is look at each tile in turn and check each of its edges does match the edge of the tile it touches, if any. If you find a tile edge that doesn't match then the 'solution' isn't a solution after all. How long would that take to check? With say a 10 piece puzzle there are 10 pieces to check each with 6 edges so in total that is 10x6 = 60 things to check. That wouldn't take too long. Even with 100 pieces it would be only 600 things to check - 10 minutes if you could check an edge a second. So Tantrix rotation puzzles are NP puzzles - they can be checked quickly.

But can you solve it?

The question is: "Are rotation puzzles P puzzles too?" Can they always be solved quickly if you or a computer were clever enough? You may have found that puzzle easy to solve. It is much harder to come up with a quick way that is guaranteed to solve any rotation puzzle I give you. One way would be to methodically work through every combination of tile rotations to see if it worked. That would take a long time though.

There are 6 positions for the first piece (ways to rotate it), but for each of those 6 positions the second piece could be in 6 positions too ... and so on for each other piece. Altogether for a 10-tile puzzle there are 6x6x6x6x6x6x6x6x6x6 (i.e., over 60 million) positions to check looking for a solution (and we might have to check them all). If you could check one position a second, it would take you around 700 days non-stop (no eating or sleeping). That is just for a 10-tile puzzle...now for a 100-tile puzzle - I'll leave you to work that out.

It is not what computer scientists call "quick".

How clever do you have to be?

If P=NP is true it would mean there is a quick way of solving all Tantrix rotation puzzles out there, if only someone were clever enough to think of it. If P=NP is not true then it might just not be possible however clever you are. Trouble is no-one knows if it's true or not...

To find out more about Tantrix links to computer science and what are known as NP-complete problems, read on.