Skip to content
Vamshi Jandhyala

Books · The Riddler

Chapter 236

Can You Escape This Enchanted Maze?

Riddler Express

An enchanted maze is drawn as words arranged in hexagons. Navigating between hexes, a consonant forces a left turn (60∘60^\circ or 120∘120^\circ) and a vowel (Y counts) forces a right turn; you may never go straight or reverse, you restart if you leave the figure or enter the grey hex, and you must pass the letter “M” before finishing. Can you reach the “Win!” hex?

The Riddler, FiveThirtyEight, July 26, 2019(original post)

Status

Solving this maze requires the published hexagonal figure: the exact positions of every lettered hex, their adjacencies, and the location of the grey hex and the “Win!” exit. That layout is given only as an image, with no machine-readable coordinates, so the turn-by-turn navigation cannot be reconstructed from the text alone. The puzzle does have a definite answer (the column shows a winning route, one of which spells DAADQANMADQANYCENSEKUEKEESALFI), but it is an image-dependent path-finding puzzle rather than a derivable computation.

The Express is therefore deferred from the worked-solution standard, in the same category as the earlier image-only grid puzzles (the gerrymandering maps and the colour-edge maze). If the hex adjacency graph were transcribed, the turn rules would make it a short directed-graph search.

Riddler Classic

There are 4848 contiguous U.S. states, each sharing a border with at least one other. Plan a trip visiting as many states as possible, with the rule that you may cross each border (each adjacency) at most once. You may revisit a state, as long as you do not re-enter or leave it across a border you have already used. How many states can you visit?

The Riddler, FiveThirtyEight, July 26, 2019(original post)

Solution

Turn the map into a graph: each state is a vertex, each shared border an edge. A trip that crosses each border at most once is a trail (a walk with no repeated edge), and we want the trail touching the most distinct states. The cleanest way to touch every state is a trail that never even repeats a vertex, which is a Hamiltonian path through the graph.

Such a path exists, so the answer is the whole map: all 48 states.\boxed{\text{all } 48 \text{ states}}. One concrete route runs up the New England coast, down the Atlantic seaboard, across the South, up through the Midwest, out to the Mountain West and Pacific Northwest, and back through the Southwest; the computation below produces an explicit ordering. Because 4848 is the total number of states, no trip can do better, and a Hamiltonian path achieves it, so 4848 is both the maximum and attainable. (If you allow revisiting states, you can keep crossing unused borders far longer: one solver found a trail touching 9191 not-necessarily-distinct states, but the count of distinct states is capped at 4848.)

The computation

Encode the adjacency graph of the 4848 states and search for a Hamiltonian path by backtracking, ordering candidate next-states by fewest remaining options first (Warnsdorff’s heuristic) with an alphabetical tiebreak so the result is reproducible. Finding a path of 4848 distinct states proves the maximum is reached.

adj_raw = {
"AL":"FL GA MS TN","AR":"LA MO MS OK TN TX","AZ":"CA NV NM UT",
"CA":"AZ NV OR","CO":"KS NE NM OK UT WY","CT":"MA NY RI",
"DE":"MD NJ PA","FL":"AL GA","GA":"AL FL NC SC TN",
"IA":"IL MN MO NE SD WI","ID":"MT NV OR UT WA WY","IL":"IA IN KY MO WI",
"IN":"IL KY MI OH","KS":"CO MO NE OK","KY":"IL IN MO OH TN VA WV",
"LA":"AR MS TX","MA":"CT NH NY RI VT","MD":"DE PA VA WV","ME":"NH",
"MI":"IN OH WI","MN":"IA ND SD WI","MO":"AR IA IL KS KY NE OK TN",
"MS":"AL AR LA TN","MT":"ID ND SD WY","NC":"GA SC TN VA",
"ND":"MN MT SD","NE":"CO IA KS MO SD WY","NH":"MA ME VT",
"NJ":"DE NY PA","NM":"AZ CO OK TX","NV":"AZ CA ID OR UT",
"NY":"CT MA NJ PA VT","OH":"IN KY MI PA WV","OK":"AR CO KS MO NM TX",
"OR":"CA ID NV WA","PA":"DE MD NJ NY OH WV","RI":"CT MA","SC":"GA NC",
"SD":"IA MN MT ND NE WY","TN":"AL AR GA KY MO MS NC VA",
"TX":"AR LA NM OK","UT":"AZ CO ID NV WY","VA":"KY MD NC TN WV",
"VT":"MA NH NY","WA":"ID OR","WI":"IA IL MI MN","WV":"KY MD OH PA VA",
"WY":"CO ID MT NE SD UT"}
adj = {k: set(v.split()) for k, v in adj_raw.items()}
assert len(adj) == 48 and all(s in adj[t] for s in adj for t in adj[s])

def hampath(start):
    path = [start]; used = {start}
    def dfs(u):
        if len(path) == 48: return True
        for v in sorted(adj[u] - used, key=lambda x: (len(adj[x] - used), x)):
            path.append(v); used.add(v)
            if dfs(v): return True
            path.pop(); used.discard(v)
        return False
    return path if dfs(start) else None

pth = hampath("ME")
print(len(pth), "distinct states:", len(set(pth)) == 48)
print(" ".join(pth))
# 48 distinct states: True
# ME NH VT MA RI CT NY NJ DE MD PA WV OH MI IN IL WI MN ND MT SD IA NE KS CO
# WY UT ID WA OR CA NV AZ NM OK TX LA AR MO KY VA NC SC GA FL AL MS TN

The search returns a path through all 4848 states with no border crossed twice, so the answer is 4848.