|Applet: The Seven Bridges of Konigsberg|
HO = Honey Bridge * BL = Blacksmith Bridge * WO = Wooden Bridge
ME = Merchants Bridge * GR = Green Bridge * CO = Connecting Bridge * HI = High Bridge
1) The eighteenth-century German town of Konigsberg, now the Russian city of Kaliningrad, was situated on two islands and the banks of the Pregel River. Konigsberg had seven bridges.
2) The people of the town believed, but could not prove, that it was impossible to tour the town, crossing each bridge exactly once, regardless of where the tour started or finished.
3) If you click on a button, it will take you across that bridge by the shortest path. For example, clicking on the WO button at the upper left of the applet will take you across the Wooden Bridge at the upper right.
4) Abbreviations used for the buttons are shown above the applet.
5) If you succeed, you will finish with one line across each bridge, and a continuous path with exactly two ends. No attempt has been made to stop you from multiple crossings.
6) If you want to start over, click the Refresh button on your browser to reset the applet.
McGraw-Hill Ryerson Mathematics of Data Management, Section 1.5, Example 3, Page 44.
1) One possible path could be to start at the upper left corner. Cross the Honey Bridge by pressing the HO button. This takes you across the Honey Bridge, where you have four choices. You can head for the Green Bridge, the Connecting Bridge, the Merchants Bridge, or the Blacksmith Bridge. Press the BL button for the Blacksmith Bridge. This brings you back up to the top of the applet, and gives you a choice of going back to the Honey Bridge, or to the Wooden Bridge. Since you have already crossed the Honey Bridge, you must head for the Wooden Bridge to achieve the desired route. Continue in this manner, selecting bridges that you have not yet crossed, in an attempt to solve the problem.
2) Select a different starting point and generate another path.
3) Any valid solution to the problem will be a continuous line with two ends, such that no bridge has more than one line crossing it.