I believe the Traveling Salesman problem was solved - sometime in the 80's.
'Quick Route - A Puzzle That Requires Thought To Solve', has a bunch of easy problems with just 4 points and 5 points. After that, it gets very difficult. There are 102 levels and I've solved 14 of them. Surprisingly, there is an addictive element to this puzzle game.
Very Cool: whatever route you draw, if it's not correct, the program tells you what % longer it is than what the optimal route is. I've drawn one route that was a mere .2% longer.