# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1338: Country walks

From New Scientist #2497, 30th April 2005

The picture shows villages A to K and all but one of the lanes between them. The missing lane does not cross any other lane.

I remember that it is possible to reach a friend’s village by starting at my village, going for a walk along the lanes, and using every lane exactly once.

I also remember that it is possible to start at my village, go for a walk along the lanes, and pass though each of the other villages exactly once before returning to my own village.

Which two villages are joined by the lane which was missed out of the picture?

[enigma1338]

Advertisements

### One response to “Enigma 1338: Country walks”

1. Jim Randell 21 March 2014 at 8:20 am

A path that visits each edge of the graph exactly once is known as a Eulerian Path [ http://en.wikipedia.org/wiki/Eulerian_path ]. In order for such a path to exist the start and end vertices must have odd degree, and the remaining vertices must have even degree. (Or if the start and end vertices are the same all vertices must have even degree).

A path that visits each vertex of the graph exactly one and returns to the starting vertex is known as a Hamiltonian Circuit [ http://en.wikipedia.org/wiki/Hamiltonian_path ].

This Python program considers the graph given in the diagram and adds an extra edge to see if that produces a graph with exactly two vertices of odd degree. If so it looks for a Eulerian Path on the graph, and a Hamiltonian Circuit.

It’s a Python 3 program (as it uses the yield from ... construct) and runs in 68ms.

```from itertools import combinations
from enigma import first, printf

# shortcut labels
(A, B, C, D, E, F, G, H, I, J, K) = nodes = 'ABCDEFGHIJK'

# the graph of the diagram
adj0 = {
A: (B, D, G, K),
B: (A, C, C, H),
C: (B, B, D, I),
D: (A, C, F, J),
E: (F, J),
F: (D, E, K),
G: (A, H),
H: (B, G, I, I),
I: (C, H, H),
J: (D, E, K),
K: (A, F, J),
}

# regions through which the missing lane can run
regions = (
(A, D, F, K),
(A, B, C, D),
(A, B, G, H),
(A, D, G, H, I, J, K),
(B, C),
(B, C, H, I),
(H, I),
(D, E, F, J),
(E, F, J, K),
)

# find a eulerian path
# adj - the graph
# p - current path
# t - target node
# n - number of edges to traverse
def path(adj, p, t, n):
# are we done?
if n == 0:
if p[-1] == t:
yield p
else:
# extend the path
s = p[-1]
for d in adj[s]:
# remove the edge
adj2 = dict(adj)
adj2[s] = list(adj[s])
adj2[s].remove(d)
adj2[d] = list(adj[d])
adj2[d].remove(s)
# and traverse the remaining edges
yield from path(adj2, p + [d], t, n - 1)

# find a hamiltonian circuit
# adj - the graph
# p - current path
# n - number of nodes to visit
def circuit(adj, p, n):
# are we done?
if n == 0:
if p[0] == p[-1]:
yield p
else:
# extend the path
s = p[-1]
for d in adj[s]:
if d not in p[1:]:
yield from circuit(adj, p + [d], n - 1)

# count the number of edges, and number of nodes
n = sum(len(v) for v in adj0.values()) // 2
m = len(nodes)

# add an edge between two nodes
for (s, f) in combinations(nodes, 2):
# check lane doesn't cross other lanes
if not any(s in r and f in r for r in regions): continue

# make a new graph
adj = dict(adj0)
adj[s] += (f,)
adj[f] += (s,)

# find nodes of odd degree
odd = list(k for (k, v) in adj.items() if len(v) % 2 == 1)
if len(odd) != 2: continue

# try to find a eulerian path between the odd nodes
p = first(path(adj, odd[:1], odd[1], n + 1))
if not p: continue

# try to find a hamiltonian circuit
c = first(circuit(adj, odd[:1], m))
if not c: continue

printf("[s={s} f={f} odd={odd} path={p} circuit={c}]", odd=''.join(odd), p=''.join(p[0]), c=''.join(c[0]))
printf("missing lane between {s} and {f}")
```

Solution: The lane missing from the map joins I and K.

The home villages are F and J, but we don’t know which is which as the path can be traversed in either direction (F to J or J to F), and the circuit can start and end at any node.