15,608,181 members
Articles / Programming Languages / C#
Article
Posted 10 Aug 2006

63.2K views
28 bookmarked

# The Bridges of Königsburg

Rate me:
Solving the impossible! A solution to The Bridges of Königsburg.

## Introduction

When I was a small child, my grandfather introduced me to a puzzle to which he claimed there is a solution. First, he draws the following on a piece of paper:

Then he described the rules. Draw a line through an edge, without crossing one twice. If you cross all of the edges, you have solved the puzzle. A sample failed solution:

I spent the rest of my childhood looking for a solution (Albeit not too hard the NES had just been released).

After solving the problem and realizing that there is no solution, I did a web search on Google for unsolvable problems. It turns out that Leonard Euler had come with the same solution centuries ago, using a way more elegant method. I am humbled by his brilliance. That is also how I learned that this problem is called The Bridges of Königsburg. I will not detail his solution as other mathematicians have done a much better job. I will provide links for the lazy, however.

## My Historical Solutions

Originally, I attempted to solve this problem with no programming background, using 16 embedded `for` loops. I will not write the code here out of courtesy, however, a timing illustrated that the run time was in the eons. This was on a PII 233 Mhz machine. I tried the code in VB6, Java, and then C++, in hopes of a speed increase :).

A few months and a computer science course later, I designed an algorithm using n-ary trees and a complicated set of rules to prune the tree. Before I pruned the tree, the machine started thrashing and had a run time of about 100 years. After much thought and a few months sabbatical from the problem, I pruned the tree during execution. This method was written entirely in C++, and after all tweaking was done, it ran in less than a minute on my PII 233 Mhz machine! I was happy the problem was solved, wish I still had the code!

## My Current Solution

I have always wanted to rewrite this problem using my experience as a guide. The other night I had an epiphany. In my C++ solution, I had used a massive series of `if` statements to determine if the node in the n-ary tree was valid. It occurred to me that if I designed a graph that could only traverse valid paths, all I would have to do is traverse all paths. It should be much quicker. As a personal note: my original solutions each took well over 100 hours; the one I am about to present only took me one to design. Anecdotal evidence proves that experience does matter.

In a break from what I usually do, I have included the complete source with this article. Therefore, I will only go over some fun little snippets.

The class below generates the entire graph based on the diagram. I sectioned the illustration into quadrants, and called each edge a bridge. The bridge constructor will assign the bridge to the quadrants in the constructor, so while the code may appear to be useless, it is actually important to create all the bridges.

C#
```public class LegalGraph{
public LegalGraph(){
//Create all 6 quadrants and put them in the hash

//Foreach quadrant we will now create the relationship
Bridge bridge = null;
}//end LegalGraph
}//end LegalGraph```

The bridge class is simple. The `ToString` method was written to help in debugging.

C#
```public class Bridge{

[System.Diagnostics.DebuggerHidden()]
get{
return this.q0;
}//end get
}//end Q0
[System.Diagnostics.DebuggerHidden()]
get{
return this.q1;
}//end get
}//end Q1

[System.Diagnostics.DebuggerHidden()]
public override string ToString(){
return q0.Q.ToString() + "_" + q1.Q.ToString();
}

this.q0 = q0;
this.q1 = q1;
}//end Bridge
}//end Bridge```

The `Quadrant` class is even simpler:

C#
```public class Quadrant{
private List<Bridge> bridges = new List<Bridge>();

public List<Bridge> Bridges{
[System.Diagnostics.DebuggerHidden()]
get {
return this.bridges;
}//end get
}//end Bridges

public int Q{
[System.Diagnostics.DebuggerHidden()]
get{
}//end get
public override string ToString() {
}
}

Now for the beef. The `HelpPlaySolutions` method is a recursive method to traverse all possible bridges. Originally, each call passed a clone of a generic list but I think this solution is more elegant. Also, note, there is almost no logical checking required to see if a bridge is passable other than seeing if a bridge was already crossed. This is why I like the graph solution. This solution is multithreaded, so it just fires an event when a win scenario has been reached.

C#
```private void HelpPlaySolutions(Bridge[] bridges, int index, Quadrant q){
if(index == 16) {
//Win
OnWin(bridges);
}
else{
/*
* For each remaining bridge cross it, only if it hasn't been
* crossed before. The magical nature of the graph ensures that all
* moves are, in fact, legal if they have not been made before
*/
foreach(Bridge b in q.Bridges){
if(!Exists(bridges, index, b)) {
bridges[index] = b;
if(b.Q0 == q)
HelpPlaySolutions(bridges, index + 1, b.Q1);
else
HelpPlaySolutions(bridges, index + 1, b.Q0);
}//end if contains
}//end foreach
}//end if
}//end HelpPlaySolutions```

By modifying the code below, you can run the code either sequentially, or by using the thread pool. `PlaySolutions` loops through every available starting quadrant.

C#
```private void PlaySolutions(){
}//end foreach
}//end PlaySolutions

DateTime now = DateTime.Now;
Bridge[] list = new Bridge[16];
}
Guid.NewGuid().ToString(), DateTime.Now - now);
}```

## Conclusion

My solution is barely elegant when compared with Euler's. I pounded and pounded with a progressively bigger hammer, and ultimately solved the solution using brute force. And when I say solved, I mean proved in all cases using brute force that there is no unique path that traverses all bridges. There are two lessons to be learned from this:

• A progressive series of well thought out algorithms can solve a large problem
• Don't believe everything your grandfather tells you

One final note: I call this current solution a solution by virtue. The problem solved itself by virtue of the design. Any solution that eliminates work by design rather than by explicit code is by virtue.

Even one more final note: I didn't have the time to test this solution as thoroughly as I would have liked, so if there is a glaring error that I missed, feel free to point it out rather than proclaiming that my solution will never work because I made one tiny technical error in the code.

## Points of Interest

A list of licenses authors might use can be found here

Written By
Architect ERL GLOBAL, INC
United States
My company is ERL GLOBAL, INC. I develop Custom Programming solutions for business of all sizes. I also do Android Programming as I find it a refreshing break from the MS.

 First Prev Next
 Broken Link Luke Dyer14-Nov-07 3:18 Luke Dyer 14-Nov-07 3:18
 Re: Broken Link Ennis Ray Lynch, Jr.14-Nov-07 4:32 Ennis Ray Lynch, Jr. 14-Nov-07 4:32
 Computer program not always best solution up_late16-Aug-06 8:17 up_late 16-Aug-06 8:17
 I know I'm stating the obvious here, and I know you did this for fun, but it is trivial to prove this problem cannot be solved just by observation. Your link "Applications of Elementary Graph Theory" explains how. To somebody with a basic background in graph theory, even a pencil and paper aren't necessary. I run into these occasionally - a computer program can exhaustively enumerate all the possibilities in a mere 100 CPU hours, but application of a little theory can produce the same solution without any programming whatsoever in about 30 seconds. I see this as a cautionary tale - programmers need to seek wisdom, in the form of theory and algorithms, outside their own field before they start coding.
 Re: Computer program not always best solution Ennis Ray Lynch, Jr.16-Aug-06 11:32 Ennis Ray Lynch, Jr. 16-Aug-06 11:32
 Re: Computer program not always best solution sherifffruitfly30-Nov-08 20:50 sherifffruitfly 30-Nov-08 20:50
 Some notes Ennis Ray Lynch, Jr.11-Aug-06 12:22 Ennis Ray Lynch, Jr. 11-Aug-06 12:22
 Re: Some notes jwebbgrv15-Aug-06 7:56 jwebbgrv 15-Aug-06 7:56
 Re: Some notes Ennis Ray Lynch, Jr.15-Aug-06 11:14 Ennis Ray Lynch, Jr. 15-Aug-06 11:14
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Mar-23 4:01 Refresh 1