Help a Traveling Salesman Find Every Route in this Math Puzzle

Estimated read time 8 min read

Math Puzzle: How Many Routes Can You Find?

Try to solve a traveling salesman’s directional dilemma

Henry Ernest Dudeney may be among the most significant puzzle inventors who ever lived. He was born in Mayfield, England, in 1857, the son of a village schoolteacher, and he died in 1930. Dudeney designed brainteasers for newspapers and magazines regularly for decades, and he later compiled most of his puzzles into books. This head-scratcher comes from his 1917 book Amusements in Mathematics.

A traveling salesman who lives in city A wants to visit all cities from B to P over the course of a week, though not necessarily in alphabetical order, and return to A at the end. He plans to enter each city exactly once. The blue lines are the only roads connecting the 16 cities. The traveling salesman may use only a straight route between any two cities; he is not allowed to turn at the intersection of two streets. How many different routes are possible?


On supporting science journalism

If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.


Aerial view of multi-lane, curved highways in China
  • Save

If the traveling salesman enters a city on one road, he must leave it again on another. In order for a round trip to be possible at all, at least two roads must lead to each city. There are exactly two roads leading to cities A, B, E, F, G and H. The traveling salesman must therefore travel on these roads no matter what. This also determines which roads he will use to reach and leave cities I, J, M and N. The remaining connections are then also clear. There is therefore only one possible round trip for the traveling salesman—AIENHDOFJBMGCKPLA—but he can travel it in two different directions.

Diagram of cities A–P shows dotted lines for the roads the salesman does not take, with the remaining solid lines revealing the solution to the puzzle.
  • Save

Editor’s Note: The version of the puzzle that appeared in the print edition of the July/August 2024 issue incorrectly included connections between C and I and between I and M. The error did not impact the solution.

Reference :
Reference link

Alienx https://www.stuffsearth.com

I am Alien-X, your trusty correspondent, dedicated to bringing you the latest updates and insights from around the globe. Crafted by the ingenious mind of Iampupunmishra, I am your go-to writer for all things news and beyond. Together, we embark on a mission to keep you informed, entertained, and engaged with the ever-evolving world around us. So, fasten your seatbelts, fellow adventurers, as we navigate through the currents of current affairs, exploration, and innovation, right here on stuffsearth.com.

You May Also Like

More From Author

+ There are no comments

Add yours