# A tour of 36 cities

Each of 4 people is touring 36 cities separately. Each of the 36 squares in the illustration below represents a city. To make the answers shorter, each city has been given a 1-character name, from A-Z, and 0-9

Note: Although this puzzle is possible to solve without computer programming knowledge, it's allowed and encouraged to use computer help.

Each city has been rated in the following 4 areas. The ratings go from -5 to 5.

A tour must include each of the 36 cities exactly one time, start at city A, and end at city 4. Each move must be either horizontal or vertical, along the small roads that connect the cities.

As the tour progresses, all of the ratings of previously-visited cities accumulate (are added together) for each of the four categories to produce four total scores- one for each of the four categories. For example, going from A to B would leave the person feeling a -9 (-4 + -5) for Money-making Potential for city B, and a 0 (-5 + 5) for Overall Happiness for city B. Then, moving from B to C, Money-making Potential is now at -11, and Overall Happiness is at -2.

Find four tours

1. Monroe believes that money is the root of all evil. Find him a tour such that one or more cities on that tour minimize his Money-making Potential. What is his favorite city (or cities) on that tour?

2. Hal is focused almost solely on being happy. Find him a tour such that one or more cities on that tour maximize Overall Happiness. What is his favorite city (or cities) on that tour?

3. Rose is into romance. Find her a tour such that one or more cities on that tour maximize Romance & Love. What is her favorite city (or cities) on that tour?

4. Arlene is an admirer of artistic beauty. Find her a tour such that one or more cities on that tour maximize Art & Architecture. What is her favorite city (or cities) on that tour?

Here is an example of a valid tour:
ABCDEFLKJIHGMNOPQRXWVUTSYZ0123987654

• I'm confused. If any tour is required to include all cities and addition is commutative, what is the purpose of any of these questions? All of the final values for each of the four attributes will always be identical. Commented Apr 2, 2015 at 19:36
• Good question. We are not interested in final values. Actually, they will all be zero. We are interested in finding a tour with a city that maximizes a particular score. Make sense?
– JLee
Commented Apr 2, 2015 at 19:45
• You're asking for a tour whose length is $\le 36$ and whose last stop satisfies (1), (2), (3), or (4). If this tour contains 4 as a stop, this must be the terminus of the tour. Correct? Commented Apr 2, 2015 at 19:48
• So, are you looking to hit the highest or lowest possible score for the relevant attribute en route, and is that what you mean by favorite city? Commented Apr 2, 2015 at 19:56
• @Ian MacDonald Almost, but not quite. The answer will be the tour which includes the city that you find maximizes or minimizes a particular rating. Make sense now?
– JLee
Commented Apr 2, 2015 at 20:41

Here are two routes that I believe maximize happiness for Hal

A B H G M S Y Z 0 1 2 W V U T N O I C D J P Q K E F L R X 3 9 8 7 6 5 4

A B C D J I H G M S Y Z 0 1 2 W V U T N O P Q K E F L R X 3 9 8 7 6 5 4

These routes both generate 23 happiness in city V

And here is a route that should maximize Art for Arlene

A G M S Y Z 0 U T N O P Q K J I H B C D E F L R X W V 1 2 3 9 8 7 6 5 4

This route generates 24 Art at cities J and I

• Correct. Damn you're fast. Now for the other 3...
– JLee
Commented Apr 2, 2015 at 20:47
• I shall poke at them tomorrow! Commented Apr 2, 2015 at 20:51
• I upvoted everyone, but I will mark this as the Accepted Answer, since Golden Dragon got 2 of the 4 questions. Props to Joffan for finding the lowest "Money-making potential" city, and props to Luke for finding the highest "Romance & Love" city.
– JLee
Commented Apr 8, 2015 at 2:23

I basically made a program that would solve this puzzle, and the end-result is a bunch of answers. If anyone feels like they have a lot of time and want to help me confirm all these answers go ahead :)

Fun Note: There are a total of 1050 ways to go from A to 4 and at the same time cover every single city once. I've posted them here.

A small note about the notation: The character in the brackets represents the city at which the critical point occurs.

Minimizing the amount of money

Lowest point possible is -32
(2) ABCIJDEFLKQRX398765Z012WVPOUTNHGMSY4

Maximizing the amount of money

Highest point possible is 20
(U) AGMSYZTNOU012WVPQKJIHBCDEFLRX3987654
(U) AGMSYZTNOU012WVPJIHBCDEFLKQRX3987654
(Y) AGMNOUTSYZ012WVPQKJIHBCDEFLRX3987654
(Y) AGMNOUTSYZ012WVPJIHBCDEFLKQRX3987654

Minimizing the amount of happiness

Lowest point possible is -25
(3) ABCDEFLKJIOPQRX398765Z012WVUTNHGMSY4
(3) ABCDEFLKJIOPQRX39876012WVUTNHGMSYZ54
(3) ABCDEFLKJIOPQRX398712WVUTNHGMSYZ0654
(3) ABCDEFLKJIOPQRX398712WVU065ZTNHGMSY4
(3) ABCDEFLKJIOPQRX3982WVUTNHGMSYZ017654
(3) ABCDEFLKJIOPQRX3982WVU01765ZTNHGMSY4
(3) ABCDEFLKJIOPQRX3982WV1765Z0UTNHGMSY4
(3) ABCDEFLKJIOPQRX3982WV1760UTNHGMSYZ54
(3) ABCDJIOPQKEFLRX398765Z012WVUTNHGMSY4
(3) ABCDJIOPQKEFLRX39876012WVUTNHGMSYZ54
(3) ABCDJIOPQKEFLRX398712WVUTNHGMSYZ0654
(3) ABCDJIOPQKEFLRX398712WVU065ZTNHGMSY4
(3) ABCDJIOPQKEFLRX3982WVUTNHGMSYZ017654
(3) ABCDJIOPQKEFLRX3982WVU01765ZTNHGMSY4
(3) ABCDJIOPQKEFLRX3982WV1765Z0UTNHGMSY4
(3) ABCDJIOPQKEFLRX3982WV1760UTNHGMSYZ54
(3) ABCIOPQKJDEFLRX398765Z012WVUTNHGMSY4
(3) ABCIOPQKJDEFLRX39876012WVUTNHGMSYZ54
(3) ABCIOPQKJDEFLRX398712WVUTNHGMSYZ0654
(3) ABCIOPQKJDEFLRX398712WVU065ZTNHGMSY4
(3) ABCIOPQKJDEFLRX3982WVUTNHGMSYZ017654
(3) ABCIOPQKJDEFLRX3982WVU01765ZTNHGMSY4
(3) ABCIOPQKJDEFLRX3982WV1765Z0UTNHGMSY4
(3) ABCIOPQKJDEFLRX3982WV1760UTNHGMSYZ54
(3) ABCIOPJDEFLKQRX398765Z012WVUTNHGMSY4
(3) ABCIOPJDEFLKQRX39876012WVUTNHGMSYZ54
(3) ABCIOPJDEFLKQRX398712WVUTNHGMSYZ0654
(3) ABCIOPJDEFLKQRX398712WVU065ZTNHGMSY4
(3) ABCIOPJDEFLKQRX3982WVUTNHGMSYZ017654
(3) ABCIOPJDEFLKQRX3982WVU01765ZTNHGMSY4
(3) ABCIOPJDEFLKQRX3982WV1765Z0UTNHGMSY4
(3) ABCIOPJDEFLKQRX3982WV1760UTNHGMSYZ54

Maximizing the amount of happiness

Highest point possible is 23
(V) ABCDJIHGMSYZ012WVUTNOPQKEFLRX3987654
(V) ABHGMSYZ012WVUTNOPQKJICDEFLRX3987654
(V) ABHGMSYZ012WVUTNOPJICDEFLKQRX3987654
(V) ABHGMSYZ012WVUTNOICDEFLKJPQRX3987654
(V) ABHGMSYZ012WVUTNOICDJPQKEFLRX3987654

Minimizing the amount of love

Lowest point possible is -21
(P) ABHGMNTSYZ0UVWQPOICDJKEFLRX398217654

Maximizing the amount of love

Highest point possible is 32
(2) AGMNOIHBCDJKEFLRX398712WQPVUTSYZ0654
(2) AGMNOIHBCDJKEFLRX398712WQPVU065ZTSY4
(2) ABHGMNOICDJKEFLRX398712WQPVUTSYZ0654
(2) ABHGMNOICDJKEFLRX398712WQPVU065ZTSY4

Minimizing the amount of art

Lowest point possible is -30
(V) AGHBCDEFLRX398712WVPQKJIONMSYZTU0654
(V) AGHBCDEFLRX398712WVPQKJIONMSTU065ZY4
(V) AGHBCDEFLRX398712WVPQKJIOUTNMSYZ0654
(V) AGHBCDEFLRX398712WVPQKJIOU065ZTNMSY4
(X) AGHBCDEFLRQKJIOPV12WX398765Z0UTNMSY4
(X) AGHBCDEFLRQKJIOPV12WX398760UTNMSYZ54
(X) AGHBCDEFLKJIOPV12WQRX398765Z0UTNMSY4
(X) AGHBCDEFLKJIOPV12WQRX398760UTNMSYZ54
(X) AGHBCDJIOPV12WQKEFLRX398765Z0UTNMSY4
(X) AGHBCDJIOPV12WQKEFLRX398760UTNMSYZ54
(X) AGHBCIOPV12WQKJDEFLRX398765Z0UTNMSY4
(X) AGHBCIOPV12WQKJDEFLRX398760UTNMSYZ54

Maximizing the amount of art

Highest point possible is 24
(J) AGMSYZ0UTNOPQKJIHBCDEFLRX3982WV17654
(J) AGMNTSYZ0UOPQKJIHBCDEFLRX3982WV17654

• Hmmm... I probably messed something up them :/ Commented Apr 8, 2015 at 14:46
• +1 but your max and min numbers look correct at first glance.
– JLee
Commented Apr 8, 2015 at 14:48
• I think I know where the problem is. Did you cover every single city once (i.e. the length of all the paths are 36)? Commented Apr 9, 2015 at 10:16
• Nevermind, there are much much (much) more than 1770 ways to go from A to 4 if you don't consider the requirement that you must cover every city once. Maybe we troubleshoot by testing out our programs on a smaller puzzle (ex. 5x5) and then comparing our answers? Commented Apr 9, 2015 at 12:29
• Well if we're getting different answers, then either one (or both) of our programs are wrong... Are you sure that of your 1770 ways, none are duplicates? Commented Apr 9, 2015 at 15:29

I reckon Monroe can sink to the lowest depths of economic potential with

ABCIJDEFLKQRX398765Z012WVPOUTNHGMSY4

now reaching the minimum in

his favorite city 2, at -32

• Yes, good find.
– JLee
Commented Apr 8, 2015 at 2:20

Here's a shot at Rose by manual labor. She can achieve love with this route:

AGMNOIHBCDJKEFLRX398712WQPVUTSYZ0654

She hits her peak in cities 2 and W, at which point she has 32 romance points in the old satchel.