applets.

Seven Bridges

← All apps

About Seven Bridges

Can you go for a walk that crosses every bridge exactly once? Can you draw a figure without lifting your pen or going over a line twice? They are the same question, and this app is about its answer.

KÖNIGSBERG: click a piece of land to stand on it, then click bridges to cross them. The page keeps track of your walk and tells you when you are stuck. SHOW AS A GRAPH turns the map into dots (the land) and lines (the bridges) and counts the bridges at each dot. Under BUILD, click a bridge to knock it down or put it back, or a dashed spot to build a new one; TODAY shows the bridges that stand on the same sites now.

PEN PUZZLES: pick a figure and trace it. Click a dot to start, then click lines (or drag along them) one after another. HINT counts the lines at each dot; SHOW ME draws it for you, or says why it can't be done.

DRAW: click the paper for a dot, drag from one dot to another for a line (drag from a dot to empty paper for a new dot and a line together). Two dots can be joined more than once. MOVE drags dots about, RUB OUT removes what you click. The page says at once whether your drawing can be walked, and SHOW ME finds a walk.

ROUTE: a gritter (or a postman) must go down every street and come back to the depot. Streets can be driven twice, but every extra metre costs. SOLVE finds the shortest round trip; DRIVE IT shows it.

The map of Königsberg here is a stylised plan made for the app, not a survey: the river, the island and the seven bridges are in the right relation to each other, but the shapes and distances are invented.

THE STORY

Königsberg in Prussia stood on the river Pregel, which ran round the island of Kneiphof (with the cathedral on it) and, just upstream, round a second piece of land, the Lomse. Seven bridges joined the four pieces of land. The townspeople are said to have wondered whether a Sunday walk could cross each bridge once and only once; nobody managed it.

Leonhard Euler, then at the Academy in St Petersburg, heard of the problem and in 1736 wrote to the mayor of Danzig, Carl Ehler, about it. His paper, Solutio problematis ad geometriam situs pertinentis ("The solution of a problem relating to the geometry of position"), was presented to the Academy in 1735 and printed in the Academy's volume for 1736 (it came out in 1741). He showed that the shapes and distances don't matter, only which land each bridge joins. Each time you pass through a piece of land you use two bridges, one in and one out, so every piece of land except the start and the finish needs an even number of bridges. In Königsberg the island had five and the other three pieces three each: four odd counts, so the walk is impossible. It is often called the first theorem of graph theory, though Euler drew no graph: he labelled the land A to D and the bridges a to g.

Euler showed that a walk needs at most two odd pieces of land, and said, without a proof, that this is also enough. That it is enough (with at most two odd dots, and everything joined, a walk always exists) was proved by Carl Hierholzer, whose paper appeared in 1873, shortly after his death. Fleury gave another method, for drawing a figure without lifting the pen, in 1883.

Königsberg was heavily bombed in 1944 and taken by the Red Army in 1945; it became Kaliningrad in Russia. Two of the seven bridges did not survive the war, and two more were later replaced by one modern road bridge crossing the island. With the three others, five crossings stand on Euler's sites: two pieces of land now have two bridges and two have three, so a walk across each once is now possible, but it has to start on one island and end on the other.

"Das ist das Haus vom Nikolaus" (this is the house of St Nicholas) is a German children's rhyme with one syllable for each line of the House puzzle, drawn without lifting the pen. The postman problem was posed by the Chinese mathematician Meigu Guan (Kwan Mei-Ko) in 1960, which is why it is called the Chinese postman problem; Jack Edmonds and Ellis Johnson gave a fast general method in 1973.

HOW IT WORKS

The rule. Count the lines at each dot (its degree). If the drawing is all in one piece and every dot is even, there is a round walk (an Euler circuit) from any dot back to itself. If exactly two dots are odd, there is a walk from one of them to the other (an Euler path), and it must start at an odd dot. With four or more odd dots there is none. There can never be just one odd dot: every line has two ends, so the degrees add up to an even number.

Finding the walk (Hierholzer's method). Start at a dot (an odd one if there are two) and keep walking along unused lines until you are stuck. You can only get stuck at the start (or at the other odd dot). If lines are left, some dot on your walk still has unused lines: walk a closed detour from there and splice it into the walk. Repeat until every line is used. SHOW ME draws each piece in its own colour, then numbers the joined-up walk.

The shortest round trip. If every corner is even, the gritter drives each street once. Otherwise the odd corners need a street repeated: pair them up and, for each pair, drive a shortest way between them twice. The page works out the shortest way between every two corners (Floyd and Warshall's method), tries every pairing (with 8 odd corners there are 7 × 5 × 3 = 105) and keeps the cheapest. The doubled-up map has every corner even, so Hierholzer's method gives the round trip. The street lengths are invented.

FURTHER WATCHING AND READING

Town
Clicks
Bridges crossed0 of 7
Standing on–