Tantrix: Solve one, solve them all

We've seen how Tantrix rotation puzzles can show what we mean by the question "Is P=NP?"

It turns out Tantrix rotation puzzles are also something called 'NP-complete'. That means it is one of a special kind of problem. NP-complete problems are the really hard ones. Some are also really important to be able to solve quickly. For example, suppose you are a taxi driver and wanted your SatNav to be able to quickly work out the fastest circular route that went via a whole series of places you wanted to visit (in any order), getting you back home. Simple as it sounds, it is an NP-complete problem. It can’t be done quickly even by a fast computer. The best that can be done is to come up with a good answer - using what's known as a 'heuristic'. There are lots of ways of coming up with such good answers - using Swarm Intelligence is one way for example. The point is none can give guarantee the best answer.

NP-completeness is important because if you could come up with a quick algorithm for solving one NP-complete problem, computer scientists know how to convert such an algorithm into one that solves all the other NP problems...P would equal NP...Trouble is no one has so far done it...