### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Enigma 1691: Factory part… | |

Jim Randell on Puzzle 52: Football on the Isl… | |

geoffrounce on Enigma 1691: Factory part… | |

Hugh Casement on Enigma 1070: Time to work | |

Jim Randell on Enigma 1070: Time to work |

### Archives

### Categories

- article (11)
- enigma (1,157)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,808 hits

Advertisements

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.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.