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.

Enigma 1338

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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: