Click here to Skip to main content
15,867,141 members
Articles / Programming Languages / C#
Article

The Bridges of Königsburg

Rate me:
Please Sign up or sign in to vote.
4.68/5 (18 votes)
10 Aug 20064 min read 64.5K   194   28   8
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:

Image of Childhood Puzzle

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:

Image of Childhood Puzzle

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 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.

C#
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:

C#
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.

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(){
    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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Architect ERL GLOBAL, INC
United States 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.

Comments and Discussions

 
NewsBroken Link Pin
Luke Dyer14-Nov-07 3:18
Luke Dyer14-Nov-07 3:18 
GeneralRe: Broken Link Pin
Ennis Ray Lynch, Jr.14-Nov-07 4:32
Ennis Ray Lynch, Jr.14-Nov-07 4:32 
GeneralComputer program not always best solution Pin
up_late16-Aug-06 8:17
up_late16-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.

GeneralRe: Computer program not always best solution Pin
Ennis Ray Lynch, Jr.16-Aug-06 11:32
Ennis Ray Lynch, Jr.16-Aug-06 11:32 
GeneralRe: Computer program not always best solution Pin
sherifffruitfly30-Nov-08 20:50
sherifffruitfly30-Nov-08 20:50 
GeneralSome notes Pin
Ennis Ray Lynch, Jr.11-Aug-06 12:22
Ennis Ray Lynch, Jr.11-Aug-06 12:22 
GeneralRe: Some notes Pin
jwebbgrv15-Aug-06 7:56
jwebbgrv15-Aug-06 7:56 
GeneralRe: Some notes Pin
Ennis Ray Lynch, Jr.15-Aug-06 11:14
Ennis Ray Lynch, Jr.15-Aug-06 11:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.