Euler and Hamilton: A programming exercise Mystery Cache

To jump straight to the puzzle, scroll down to the last section, titled "The Puzzle". Between here and there is an superfluous essay on graph theory.

The Seven Bridges of Königsberg

Leonhard Euler (pronounced "oiler"; 1707 – 1783) is considered by many people (include myself) to be the greatest mathematician of all time. One of the most significant problems that he solved is called The Seven Bridges of Königsberg. Königsberg (now called Kaliningrad, in what is now Russia) was a city with seven bridges that spanned the Pregel River, connecting the two banks as well as two islands within the river. Denizens of the city wondered if it was possible to devise a walk that would cross each bridge exactly once.

The bridges of Königsberg

Euler proved that no such walk was possible. He abstracted away the physical details of the problem, such as the length of the bridges, by representing each land mass as a single node and each bridge as an edge. An edge serves only to represent a connection between two nodes. With this representation, the mathmatical field of graph theory was born.

Abstract bridges of Königsberg

Next, Euler modelled a walk across the bridges of Königsberg as a path made up of the nodes, always following an edge to get from one node to the next. Euler observed that whenever a walk entered a node via an edge, it must also leave that node via a different edge (except for the start and end nodes). This means that the edges must come in pairs. That is, for all nodes except the start and end, there must be an even number of edges attached to it. Because each of the four nodes in Königsberg has an odd number of edges, no such walk is possible. A tour that visits each edge of a graph exactly once is became known as an Eulerian path.

Graphs

In mathematics, a graph (not to be confused with unrelated concepts like plots in the x-y plane or visualizations like bar charts) is a set of objects, represented as nodes (also called vertices), where some pairs of objects are related in some sense. These relations are represented as edges between the nodes.

A graph with five nodes and six edges

Graphs are often used to represent things in the real world. Navigation software represents roads as edges that connect intersections. Social scientists study the friend graph of social networks, both in real life and on sites like Facebook, where nodes represent people and edges represent friendships.

Königsberg as a graph

The graph of Königsberg is unusual in that some nodes have multiple edges between them. Such a graph is called a multigraph. Most graph theory, and the rest of this description, instead focuses on simple graphs, which have at most one edge between any two nodes.

Hamiltonian paths

Recall than an Eulerian path is a path that visits each edge exactly once. What about a path that visits every node at least once? This is called a Hamiltonian path, after William Rowan Hamilton, who invented a game that involves finding a Hamiltonian path on the edges of a dodecahedron.

The icosian game

Unlike the simple test for determining whether a graph has an Eulerian path, determining whether an arbitrary graph has a Hamiltonian path is NP-complete, meaning there is no known way to solve it efficiently.

Weighted graphs

Graph representations can be even more useful if we allow edges to have a cost associated with them, rather than just representing the existence of a connection between two nodes. Graphs whose edges have costs, or weights, are called weighted graphs. Weighted graphs are a more realistic representation of things in the natural world, such a roads and shipping routes. On a graph that represents cities as nodes and highways as edges, the cost of an edge could be the distance of the highway that it represents.

When you drive from point A to point B, it's natural to think of the cost of your trip as the total distance you have driven, which is the sum of the distances of each road you took. Similarly, the cost of a path on a weighted graph is defined as the sum of the weights of the edges along that path. Closely related to the problem of finding a Hamiltonian path in a graph is the longest path problem: finding the longest path (path with greatest cost) you can take in a graph, given that you don't visit a node more than once.

Representing graphs

In computing, there are several ways to represent a graph. In this puzzle we will use the adjacency matrix. The adjacency matrix of a graph with n nodes is the n*n matrix that has a 1 in position (i, j) if there is an edge between node i and node j, otherwise it has a 0.

Consider the example graph from before:

The adjacency matrix for this graph is:

To represent a weighted graph, cells of the adjacency matrix contain the weight of that edge, rather than just a 0 or 1. Here is an example of a weighted graph and its matrix:

The longest Hamiltonian path in this graph is ABDCE with a weight of 16. ABCD has weight 17, but it is not Hamiltonian.

The puzzle

Consider the following adjacency matrix of a weighted graph:

Your task is to find the longest path in this graph that starts at node g and visits each node at most once. Because the graph is complete (there is an edge between every node), the longest path is automatically Hamiltonian. When finished, you will have a 14-letter path that begins with g. Take the SHA-256 hash of the first seven letters of the path to get the latitude. Take the SHA-256 hash of the last seven letters to get the longitude.

Here is some inspirational music you can listen to while you work on this puzzle.

You can validate your puzzle solution with certitude.

Acknowledgments

Thank you to penguinphloppers for beta-testing this puzzle.