The Traveling Salesman is a new puzzle for the iPhone. The object of the game is simply to find the shortest route between a set of cities, visiting each city once and returning to the starting city. In game are presented cities from each of the 50 states. Each state has four levels of difficulty for 200 puzzles in total.

The game is based on the classic computer science of combinatorial optimisation

World Leaderbord

Apple Store
Support & Suggestions

The Travelling Salesman Problem (a.k.a., Travelling Salesperson Problem, Travelling Salesman Problem, TSP), it's a long studied problem of combinatorial optimization. The problem continues to be of interest to researchers as the solution have practical implications for problems like integrated chip layout, and also the problem shows how human can "intuitively" come up with solutions faster than modern computers. The problem continues to be studied by organizations including Air Force Office of Scientific Research and the National Science Foundation.

SCREENSHOTS

New Mexico States Utah Maine Virginia

The TSP, one most devise a route to visit each city exactly once and returns to the starting point. If a person is planning a route between four cities, the person could start from any of the four. At the first city, ther person has three unvisited cities to choose from. The person will then visit one of these, have two cities remaining to visit. After visiting on of these two, the person will be required to visit the last unvisited city, and then return to the starting city. This mean the number of choices are 4*3*2*1=24. As the person completes a loop, it does not become relevant wich city the person started from. That is, the person could start at any one city and complet the exact same loop. This means for four cities we would have 3*2*1=6 choices. As both the forward itinery and reverse itinery have the same distaces, we can further cut the number of routes in half. This give us 3 choices for a four cities map. The generalized formula for finding the number of paths is (n-1)!/2. The following table show the number of possible routes for maps having between 3 and 20 cities.

  • 3       1
  • 4       3
  • 5       12
  • 6       60
  • 7       360
  • 8       2,520
  • 9       20,160
  • 10      181,440
  • 11      1,814,400
  • 12      19,958,400
  • 13      239,500,800
  • 14      3,113,510,400
  • 15      43,589,145,600
  • 16      653,837,184,000
  • 17      10,461,394,944,000
  • 18      177,843,714,048,000
  • 19      3,201,186,852,864,000
  • 20      60,822,550,204,416,000

The number of possibles routes increase exponentially as the number of cities increase. This poses a problem for computer programs which consider all the informations presented. Humans on the other hand are continuously presented with huge amounts of information, and they are able to ignore the majority of it and focusing on the task at hand. Understanding how humans solve the problem may help produce more effective computer programs to do the same