# 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]

### 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
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
# p - current path
# t - target node
# n - number of edges to traverse
# are we done?
if n == 0:
if p[-1] == t:
yield p
else:
# extend the path
s = p[-1]
# remove the edge
# and traverse the remaining edges
yield from path(adj2, p + [d], t, n - 1)

# find a hamiltonian circuit
# p - current path
# n - number of nodes to visit
# are we done?
if n == 0:
if p[0] == p[-1]:
yield p
else:
# extend the path
s = p[-1]
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

# 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