Sunday, November 02, 2008

Puzzle

A bunch of my friends were trying to find a route round this graph at the weekend. Yeah it was a crazy party.

A quick search showed the problem was one of finding the Eulerian path. And that the puzzle had no solution

"Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex"

If there is to be an Eulerian path for a given graph the graph must have lesser than three nodes with odd number of edges."

Code to check for these paths is found here

The code to test this puzzle is
print eulerPath({ 1:[2,2,3,3,4], 2:[1,1,3,4,4], 3:[1,1,2,4,4], 4:[1,2,2,3,3]})
print "test run to make sure code works "
print eulerPath({ 1:[2,2], 2:[1,1]})

1 comment:

Eddie said...

That looks like a girl with a slashed face.