Seven Bridges of Königsberg Puzzle

The Seven Bridges of Königsberg is an unsolvable puzzle made famous by Leonhard Euler. Here it is as a playable game, so you you can test for a solution:

The goal is to to take a walk through the city crossing each bridge once and only once. You can attempt the puzzle in the HTML5 frame above by clicking and dragging the Mini Euler over the bridges. He will leave a path to show which bridges you have crossed. The puzzle is unsolvable regardless of which land mass you start on.

The puzzle arose from the actual layout of the city of Königsberg (now Kaliningrad, Russia) in Euler’s time. Euler’s proof that the puzzle is unsolvable laid the foundations of graph theory. He thought of the problem in the abstract, with each land mass as a vertex and each bridge an edge.

Euler figured out that for the puzzle to be solvable, each vertex must have an even number of edges (except that the starting vertex and ending vertex can have an odd number of edges). In Königsberg, the four land masses (the north and south banks of the river and two islands) each had an odd number of bridges touching them, so what is now called an Euler walk was not possible there.