Bridges, graphs and magic squares

Both puzzles show the charm of how things are arranged. One asks whether you can cross every bridge exactly once. The other is a square of numbers whose rows, columns and diagonals all add up to the same total.

Bridges of Konigsberg (the site’s “Bridges of Konigsberg”)

The old city of Königsberg had seven bridges linking a river’s banks and islands. Could you take a walk crossing each bridge exactly once? Euler answered that you cannot. He is said to have reported this to the academy of sciences in Russia in 1735, with the paper published in 1741.

Forget the shape of the roads, look at the connections

Euler’s idea was to replace each land area with a dot and each bridge with a line. The lengths and curves of the roads are forgotten. What matters is only what connects to what. A subway map does the same thing: it draws connections, not real distances.

The condition for crossing every line once then becomes clear. A route that uses every line exactly once exists when the whole picture is connected and the number of dots with an odd number of lines is 0 or 2. With 0, you can come back to where you began. With 2, you start at one of them and finish at the other.

In Königsberg, the four land areas have 5, 3, 3 and 3 bridges, all odd, so it is impossible. For the four diagrams on this site, the program tried every order of crossing to check which can be done and which cannot. Only two of the four can.

What Euler did not say

Euler stated the opposite direction, that meeting the condition really does allow a route, without proving it. The first complete proof is said to be in Hierholzer’s paper of 1873. People sometimes say “Euler proved everything,” but that is not accurate.

This solution is regarded as the beginning of graph theory. Looking only at connections, without length or shape, is also called a forerunner of topology.

Later, wars and other events destroyed some of the real bridges. Some sources say five bridges remain today, and that a route crossing each exactly once is possible in that layout. The number and names of the bridges differ between sources.

Magic Square (the site’s “Magic Square”)

A magic square places the numbers 1 to n × n in a square, with no repeats, so that every row, every column and both diagonals add up to the same total. On this site the target is 15 for 3 × 3 and 34 for 4 × 4.

3 × 3 has essentially one square

There are 8 ways to fill a 3 × 3 magic square, but turning and flipping turns any one into any other. So there is only one shape. The centre is always 5. This site’s program went through all the cases to check.

In China this shape has been called the “Luoshu.” In the legend, when the sage Yu was taming a flood, a turtle came out of the Luo River with dots from 1 to 9 on its shell. That is a legend. Old books mention “the River Chart and the Luo Writing,” but it is said that the arrangement is clearly a 3 × 3 square of numbers only from around the start of the common era or later. It also cannot be said for sure that the Luoshu is the oldest magic square in the world.

A year hidden in Dürer’s engraving

On the wall in the background of Albrecht Dürer’s engraving “Melencolia I” (1514) there is a 4 × 4 magic square. Its rows, columns and diagonals all add up to 34. In the middle of the bottom row sit 15 and 14, so you can read the year, 1514, there.

Every 4 × 4 magic square must total 34. Add 1 to 16 and you get 136; with 4 rows, 136 ÷ 4 = 34. A 4 × 4 square with the same total is also said to be carved on a wall of an Indian temple of the 12th century, so Dürer’s was not the first in the world.

880 squares of size 4 × 4

Using the numbers 1 to 16, there are 880 magic squares of size 4 × 4 when squares that match after turning or flipping count as the same. The French mathematician Frénicle de Bessy of the 17th century counted them, and his work was published after his death, in 1693. He did it in an age without computers. This site’s program has not recounted the 880, so it is given here as the number from the sources listed below. Compared with the single shape for 3 × 3, you can see how quickly the count jumps at 4 × 4.

How to think about them

• Bridges: Before crossing, count how many bridges meet at each land area. If the number of areas with an odd count is not 0 or 2, you can safely give up.
• Magic Square (3 × 3): The centre is 5. Make pairs of opposite cells that add up to 10.
• Magic Square (4 × 4): The target is 34. Once a row is chosen, work out the missing number backwards.

The 4 × 4 board is a free exploration mode. If you put a number you have already used into another square, its old square is cleared.