Logic puzzle: Driving around the United States

Question

For Super Bowl Sunday, here's a super-sized logic puzzle!

This was a practice puzzle for a hunt I participated in a few years ago.

There are ten delivery drivers driving around the United States of America. Here are their stories:

• The drivers traveled exclusively on roads, never left the contiguous forty-eight states, and did not visit the District of Columbia. Every state was visited by at least one driver.
• Every driver's route ended in a different state than its origin and never visited a state more than once.
• No two drivers visited the same number of states. The route that visited the most states visited a total of twelve.
• Every driver visited at least one state another driver also visited. Flo visited the most states visited by other drivers, with nine. Jill visited the least, with just one.
• The twenty origin and destination states were distinct. Of the origin states, only Alabama and Tennessee were visited by any other driver. None of the destination states were visited by another driver.
• Seventeen states were visited by more than one driver. Of these, exactly Idaho, Missouri, Ohio, Oregon, Wisconsin, and Wyoming were each visited by drivers of a single gender.
• Nine state borders were crossed by more than one driver and each was always crossed in the same direction.
• Paul and Flo drove through the same sequence of five states in a row — the longest such overlapping sequence.
• Only Ann, Bob, Jill, Lee, and Sue could have returned to their origin state without revisiting any states. Only Lee ended his journey in a state adjacent to the one he started in.
• Only Bob, Dave, and Jill passed through the fewest possible states between their origin and destination states.
• More states were directly accessible from Paul's origin state than were from any other driver's origin state. Only he and Sue began their journey by driving into a state with fewer states accessible from it than from their origin state.
• Only Bob, Jill, and Tess never drove from a state directly into another with the same number of letters in its name. Only Dave, Flo, and Mark drove through three states in a row with the same number of letters.
• Exactly half of the drivers visited a state that shares its name with the British colony that preceded it and all of them either began or ended their journey in such a state. Flo drove through eight such states, five of them in a row, in both cases the most of any driver.
• Only Flo drove into a state that is a sub-anagram of the state she was driving out of. Only Mark drove into a state that is a super-anagram of the state he was driving out of. Sue's origin state is a sub-anagram of Tess's destination state.
• Only Flo, Lee, and Mark visited a state named after a king or queen, with Mark and Flo each visiting four.
• More than half of the drivers ended their journey in a state that alphabetically follows their origin state. Of the destination states, Lee's was alphabetically first and Mark's was alphabetically last.
• Only Jill, Lee, and Mark visited no state that borders a foreign country (including maritime borders). The other seven all visited states that border Canada. Three visited states that border Mexico (two of whom originated in such a state).
• Every driver visited at least one state whose flag contain the state's name spelled out in full. Only Sue visited such states exclusively.
• Three drivers each visited three states containing double letters (and no driver visited more), but only Lee drove through three such states consecutively. Only Jill and Tess drove through no such states.
• Sue visited the most states without sales tax.
• Only Jill visited no state with a coastline, while only Bob visited such states exclusively. Exactly two drivers visited states on the Pacific Ocean, five visited states on the Atlantic Ocean, six visited states on the Great Lakes, and four visited states on the Gulf of Mexico (three of whom originated in such a state). No driver visited states on both oceans and only Ann visited states on both the Gulf of Mexico and the Great Lakes.
• Mark is unique both in passing through at least four states in a row in ascending alphabetical order and in passing through at least four states in a row in descending alphabetical order.
• Only Dave, Lee, and Sue crossed the Mississippi River.
• Two drivers tied for visiting the most states with two word names.

Helpful resources/facts:

• State borders: https://state.1keydata.com/bordering-states-list.php
• Thirteen colonies: New Hampshire, Massachusetts Bay Colony, Rhode Island and Providence Plantations, Connecticut, New York, New Jersey, Pennsylvania, Delaware, Maryland, Virginia, North Carolina, South Carolina, Georgia
• States named after kings and queens: North Carolina, South Carolina, Virginia, West Virginia, Maryland, Louisiana, Georgia
• States that border Canada: Washington, Idaho, Montana, North Dakota, Minnesota, Michigan, Ohio, Pennsylvania, New York, Vermont, New Hampshire, Maine
• States that border Mexico: California, Arizona, New Mexico, Texas
• States with a maritime border: Florida
• State flags: https://en.wikipedia.org/wiki/Flags_of_the_U.S._states_and_territories
• States without sales tax: Delaware, Montana, New Hampshire, Oregon
• States by coastline: https://en.wikipedia.org/wiki/List_of_U.S._states_and_territories_by_coastline
• Mississippi River: https://www.mississippirivercruises.com/images/MRC/MRC.gif

Answer 1

So I thought I'd help get people started, maybe even motivated.

Firstly, here's an editable spreadsheet. Feel free to make corrections. There may be more columns needed but this is at least a start!

Secondly, here's an editable map. It's a bit of a mess.

I'm not sure this is possible given the constraints. Figuring out where I've gone wrong in my logic may help! But here's the issue. The key is mark and flo.

1. They are both east of the Mississippi.
2. Mark goes from Virginia to West Virginia (only way to go into a super anagram) and no-one else does.
3. Flo goes from New Hampshire to Main (only sub anagram) which ends her run.
4. Mark and Flo both need to visit four states names after royalty. There are 6 east of the Mississippi so they will overlap two of them.
5. Mark and Flo both need to visit three states in a row with the same number of letters in their name.
6. For Mark, he cannot visit Florida. And he will go from Virginia to West Virginia. So either it's Delaware->Maryland->Virginia or Illinois->Kentucky->Virginia.
7. We can eliminate Illinois->Kentucky->Virginia, since it then goes to West Virginia and cuts off access to three states names after royalty (NC, SC, Georgia).
8. So Mark's route includes Delaware->Maryland->Virginia->W. Virginia.
9. Now Flo will need to get up from the bottom royal states to Maine. And will need to hit Alabama-Georgia-Florida to get three states in a row with the same number of letters.
10. There are now very few options for Mark to get the four states that go in decreasing order.
11. In fact, I can only see the following for Mark: Delaware->Maryland->Virginia->W. Virginia->Ohio->Michigan->Indiana->Illinois->Kentucky->Tennessee->North Carolina.
12. The ending can't be Georgia (only other possibility) because that's behind Maine alphabetically.
13. In principle, Mark could start one state earlier (Pennsylvania/New Jersey), but I think the 12 state driver will have to be Flo.
14. So, back to Flo. She can't go through Ohio. Mark's already gone there and it is a single-gender state.
15. That leaves Flo to do the following: Alabama/Florida->Florida/Alabama->Georgia->North Carolina->Virginia->Kentucky->W. Virginia->Pennsylvania->New York->Vermont/Massachusetts->New Hampshire->Maine. That's 12 States, so there's no wiggle room.
16. That means that South Carolina must be visited by Lee.
17. Lee will visit Louisiana (he's the only one), Tennessee and Missouri, South Carolina and one of Illinois and Mississippi. He's also going to have to stop next to his starting position.

Answer 2

I tried solving this puzzle, and have come to a concise proof that no valid solution exists.

I invite everyone to try to find any point where this proof is not valid, because I would greatly prefer to be wrong.

More specifically than proving no valid solution to the overall puzzle exists, I will prove that no valid solution for Mark's path exists.

Given facts about Mark's path:

A. Mark goes through 4 royalty states (4 of North Carolina, South Carolina, Virginia, West Virginia, Maryland, Louisiana, Georgia).

B. Mark does not cross the Mississippi.

C. Mark never visits a state that borders a foreign country (including maritime borders).

D. Mark goes from a state into a superanagram state.

E. Mark drives through 3 states in a row with the same number of letters.

F. Mark drives through at least 4 states in a row in ascending alphabetical order and at least 4 states in a row in descending alphabetical order.

Deduction:

1. Mark be on the east side of the Mississippi, because only 1 royalty state (LA) is accessible from the West.

2. There are only two pairs of superanagram/subanagram neighboring states: Maine & New Hampshire, and Virginia & West Virginia. The former is ruled out for bordering Canada, so Mark must have traveled from Virginia to West Virginia.

3. East of the Mississippi, there are only 4 groups of states that could be traveled through in a row with the same number of letters: AL-GA-FL (reorderable), DE-MD-VA, MD-VA-KY, VA-KY-IL.

4. Of these 4 groups, AL-GA-FL is ruled out because FL has a foreign border, and MD-VA-KY is ruled out because Mark goes from VA to WV.

5. If Mark goes IL-KY-VA-WV, then Mark can never go south of KY and VA, since he's blocked by the Missippi. As a result, Mark would never be able to reach more than 3 royalty states (MD, VA, WV). Thus, Mark goes DE-MD-VA-WV.

6. Since Pennsylvania and New York border Canada, Mark can't reach another royalty state prior to Delaware. Thus, Mark must reach another royalty state after West Virginia.

7. Since Pennsylvania and Ohio border Canada, Mark must go to Kentucky after West Virginia.

8. After Kentucky, Mark must go to Tennessee in order to be able to reach another royalty state (SC, NC, GA, LA).

9. From Tennessee onward, Mark must visit 4 states in descending (reverse) alphabetical order. These 4 states must be among the set (TN, NC, SC, GA, AL, MS, LA).

10. The only way to do so is TN-NC-GA-AL.

11. But now Mark has visited 5 royalty states (MD, VA, WV, NC, GA) which contradicts the puzzle stipulations.

Thus, there is no valid path for Mark.

Again, I invite everyone to find any flaw in this proof, because I'd love to solve the puzzle, but as far as I can tell the puzzle is unsolvable.