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. – Ian MacDonald Apr 2 '15 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 Apr 2 '15 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? – Ian MacDonald Apr 2 '15 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? – Joffan Apr 2 '15 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 Apr 2 '15 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 Apr 2 '15 at 20:47
• I shall poke at them tomorrow! – Golden Dragon Apr 2 '15 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 Apr 8 '15 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 :/ – Allan Apr 8 '15 at 14:46
• +1 but your max and min numbers look correct at first glance. – JLee Apr 8 '15 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)? – Allan Apr 9 '15 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? – Allan Apr 9 '15 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? – Allan Apr 9 '15 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 Apr 8 '15 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.