Math Puzzle: How Many Routes Can You Find?

Try to solve a traveling salesman’s directional dilemma

By Heinrich Hemme edited by Sarah Lewin Frasier

Diagram shows circles representing cities A–P and blue lines connecting each circle to two or more others.

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?

View puzzle with solution at this link.

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.

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.

It’s Time to Stand Up for Science

If you enjoyed this article, I’d like to ask for your support. Scientific American has served as an advocate for science and industry for 180 years, and right now may be the most critical moment in that two-century history.

I’ve been a Scientific American subscriber since I was 12 years old, and it helped shape the way I look at the world. SciAm always educates and delights me, and inspires a sense of awe for our vast, beautiful universe. I hope it does that for you, too.

If you subscribe to Scientific American, you help ensure that our coverage is centered on meaningful research and discovery; that we have the resources to report on the decisions that threaten labs across the U.S.; and that we support both budding and working scientists at a time when the value of science itself too often goes unrecognized.

In return, you get essential news, captivating podcasts, brilliant infographics, can't-miss newsletters, must-watch videos, challenging games, and the science world's best writing and reporting. You can even gift someone a subscription.

There has never been a more important time for us to stand up and show why science matters. I hope you’ll support us in that mission.

Thank you,

David M. Ewalt, Editor in Chief, Scientific American