Dark Side of the Sun

Sunday, January 16, 2011

Python: brute-force solution to Bridges of Königsberg

Yesterday I read about the mathematical problem of the Seven Bridges of Königsberg. Since Leonard Euler already solved the problem a while ago (or rather, assured us that there is no possible solution to it), through elegant and brilliant thinking and analysis (and by the same, initiating the discipline of Graph Theory, what a man!), I set myself a much more insignificant challenge: My obsessive pastime of the afternoon has been writing a python program which would find all possible paths of the Bridges of Königsberg problem, using only one recursive function. I know, I am such a geek! Get over it. I have.

My goals with this were simply:
  • To have an excuse to shake the dust off my programming/scripting (haven't written any code in a while).
  • To get some practice with recursivity, as this seemed like a perfect case to apply it.
Accidentally, along the way, I have learned some bits about things like Game Theory, Graph Theory and Decision Trees.

An interesting information that came out of this is that my brute-force approach says there are 372 different legal paths. Much less than I expected, which explains why it solves so fast. I would be interested in hearing if anyone reading this knows a way to calculate this number.

I haven't seen any examples of  a similar code online (probably because it's pretty useless), so I thought I'd share it, in case anyone is interested:

konigsbergBridges.py

And here is a diagram of the naming convention that my program uses for land zones & bridges:


It would be very easy to adapt this code to any other similar problem, with an arbitrary number of land zones and bridges connecting them, by changing the initial variable declarations. But with a high number of bridges, I am sure the program would hit some technical limits like the recursion limit, or would need to run for a long time.

1 comment: