Tantrix Puzzles

Tantrix Rotation Puzzles are simple but fiendishly difficult solitaire puzzles that give a way of understanding some simple but fiendishly difficult computer science about how complex problems really are in terms of how much computation is needed to solve them.

Tantrix rotation puzzles involve taking a set of randomly placed hexagonal tiles of the kind shown and trying to rotate them on the spot (nothing moves position) in a way that makes all coloured lines match on all adjacent edges. See if you can solve the 5 tile puzzle on the right to get the idea.

To do Tantrix puzzles first get a Tantrix set (you can also do some games and puzzles online at tantrix.com – there are lots of different ways to use a set). Lay out some tiles at random then off you go.

Tantrix rotation puzzles are a good way to explore some important theoretical computer science: part of what is known as complexity theory. First try and solve some puzzles. Then think about whether you can devise an algorithm that guarantees to always solve them. You possibly can, but it is probably very slow. Then see if you can come up with a way you can check your solutions definitely are right. Only then read on.

Is P = NP?

Solving any individual puzzle may be easy or hard. Finding a fast algorithm that solves all rotation puzzles (ie finds solutions) quickly is fiendishly difficult (that is why they are good puzzles!). No one so far has ever done it.

However, checking a given solution to see if it is a correct solution is fast and simple. Just check each edge of each tile in turn.

This is what the most famous equation in computer science is about.

Is P = NP?

It is phrased as a question because no one knows whether it is true or false.

What does it mean? Coming up with a solution to a Tantrix rotation puzzle is known as an NP problem. It is a kind of problem for which all known perfect algorithms (ones guaranteed to find solutions) are incredibly slow.

Checking if you have a solution, on the other hand, is a P problem: it is easy to create a quick algorithm to do.

The equation is asking whether it is the case that if for any problem (like our Tantrix rotation puzzles) where checking answers is quick, there is also a quick way to come up with answers in the first place? If this is always the case then the equation is true and P= NP. If not then the equation is false.

No one knows the answer. Come up with a fast and guaranteed way (ie algorithm) to solve Tantrix rotation puzzles and you would likely become very famous. You would also likely be rich. They are also a kind of problem called NP-complete. If anyone solves any NP-complete problem in the sense of coming up with a fast but perfect algorithm, then computer scientists could turn it into an algorithm that would also solve every other NP-complete problem…and that means being able to solve some very, very important real problems quickly that currently are just infeasible.