The Bridges of Königsburg

• Download project files - 16.2 Kb

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.

• Königsburg Bridges
• The Seven Bridges of Konigsburg
• Applications of Elementary Graph Theory
• Google

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.

public class LegalGraph{
    public List<Quadrant> quadrants = new List<Quadrant>();
    public LegalGraph(){
        //Create all 6 quadrants and put them in the hash
        Quadrant quad0 = new Quadrant(0);
        Quadrant quad1 = new Quadrant(1);
        Quadrant quad2 = new Quadrant(2);
        Quadrant quad3 = new Quadrant(3);
        Quadrant quad4 = new Quadrant(4);
        Quadrant quad5 = new Quadrant(5);

        quadrants.Add(quad0);
        quadrants.Add(quad1);
        quadrants.Add(quad2);
        quadrants.Add(quad3);
        quadrants.Add(quad4);
        quadrants.Add(quad5);

        //Foreach quadrant we will now create the relationship
        Bridge bridge = null;
        bridge = new Bridge(quad0, quad1);
        bridge = new Bridge(quad0, quad1);
        bridge = new Bridge(quad0, quad2);
        bridge = new Bridge(quad0, quad2);
        bridge = new Bridge(quad0, quad3);
        bridge = new Bridge(quad0, quad3);
        bridge = new Bridge(quad0, quad4);
        bridge = new Bridge(quad0, quad5);
        bridge = new Bridge(quad0, quad5);
        bridge = new Bridge(quad1, quad2);
        bridge = new Bridge(quad1, quad3);
        bridge = new Bridge(quad1, quad4);
        bridge = new Bridge(quad2, quad4);
        bridge = new Bridge(quad2, quad5);
        bridge = new Bridge(quad3, quad4);
        bridge = new Bridge(quad4, quad5);
    }//end LegalGraph
}//end LegalGraph

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

public class Bridge{
    private Quadrant q0;
    private Quadrant q1;

    public Quadrant Q0{
        [System.Diagnostics.DebuggerHidden()]
        get{
            return this.q0;
        }//end get
    }//end Q0
    public Quadrant Q1{
        [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();
    }

    public Bridge(Quadrant q0, Quadrant q1){
        q0.Bridges.Add(this);
        q1.Bridges.Add(this);
        this.q0 = q0;
        this.q1 = q1;
    }//end Bridge
}//end Bridge

The Quadrant class is even simpler:

public class Quadrant{
    private List<Bridge> bridges = new List<Bridge>();
    private int quadrant;

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

    public int Q{
        [System.Diagnostics.DebuggerHidden()]
        get{
            return this.quadrant;
        }//end get
    }//end Quadrant
    public override string ToString() {
        return quadrant.ToString();
    }
    public Quadrant(int quadrant) {
        this.quadrant = quadrant;
    }
}//end class Quadrant

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.

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.

private void PlaySolutions(){
    foreach(Quadrant q in graph.quadrants){
        ThreadPool.QueueUserWorkItem(new WaitCallback(ThreadGo), q);
        //ThreadGo(q);
    }//end foreach
}//end PlaySolutions

private void ThreadGo(object q){
    DateTime now = DateTime.Now;
    if(q is Quadrant){
        Bridge[] list = new Bridge[16];
        HelpPlaySolutions(list, 0, (Quadrant)q);
    }
    OnThreadFinished((Quadrant)q, 
      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 good place to find answers to hard problems: Google.