The Konigsberg Bridge Problem. Can You Solve It?

[Snsl153]

It's simple really. Cross all seven bridges once and only once. You can start at any point on the map. :)

[AviatorTom]

Nope, it's not possible with an odd number of bridges. It only works if there are an even number of bridges.

https://sikademy.com/answer/computer-science/discrete-mathematics/describe-konigsberg-bridge-problem-rew5/#:~:text=The%20Konigsberg%20Bridge%20Problem%20is%20a%20graph%20theory,of%20this%20problem%20is%20the%20number%20of%20bridges.

[Snsl153]

Correct! :)
I was kind of hoping that some people would not be aware of this fact, and would attempt to solve it anyway.

[KostasKouvalis]

You're half right, because it's still possible with 5 bridges. So the problem isn't that there is an odd number of bridges, the problem is that that odd number happens to be 7.

https://youtu.be/nZwSo4vfw6c

[AviatorTom]

Thanks for the mho

[007kingifrit]

i attempted it, couldn't figure it out. see now why it can't be done

[Deathraider]

You can’t. Every island, every time you enter, you must also leave, meaning there must be an even number of bridges for each island. The only exception is the starting and ending island, which means at most two island can have an odd number of bridges. All islands have an odd number of bridge. Therefore this is impossible.

[The_Shadow_Dweller]

Hello!
I am not able to solve it.

Would you be kind enough to tell me, either here or in DMs as to how to solve the problem?
I would be much inclined to hear your solution, as it may be in any way.

Thank you.

Sincerely,
The_Shadow_Dweller

[Snsl153]

As others have already pointed out, the problem can't be solved. I already knew this, but I thought I'd post this problem just for a bit of light-hearted fun :)

[DaveJord]

I didn't get it, why would you have to cross all seven bridges, you can get to any place you want to go in any direction without having to cross more than 2 bridges.

If the goal is just to cross all 7 without having to cross any one bridge more than once then its impossible because there is an odd number of bridges, you would need a even number of bridges.

So in order to do it you would have to be able to start and finish at the same place... which you can not do without crossing one of the bridges more than once. I know by looking at it, that it totally seems possible but there isn't any solution to the question that would make that possible... but at the same time its a waste of time because you can get to any location you want in the shortest distant and time possible without ever having to cross more than two bridges.

[KostasKouvalis]

Not necessarily, because it would work with 5 bridges

[DaveJord]

@KostasKouvalis Sure if you say so, but thats not the question... and not nesscarily but thanks for coming out.

[KostasKouvalis]

You said it wouldn't work because it's an odd number, which isn't true, because it works with 5 just not with 7.

[DaveJord]

@KostasKouvalis sure I understand the words your saying.

[andreasderjuengere]

Done

[The_Shadow_Dweller]

Can you DM me as to how you solved it?

[NathanDavis]

brilliant

[Guffrus]

Very nice, this guy fucking smashed it.

[Daniela1982]

Cross and cross out are not the same.

[Snsl153]

No, the idea it to draw a continuous line that crosses all of the bridges, not mark them with X's.

[andreasderjuengere]

''Snsl'': Who would have thought that :)

[andreasderjuengere]

@Daniela1982 See these X's as TRANS crossings if you like. But when you see my 'solution' as a transgression... does that not count, then?

[MTC29]

In fact, only six bridges can be crossed once: 1-5-6-2-4-7.

The real problem is that after crossing bridge you are now "trapped" at the lower part of the map and since you can only cross a bridge once (1 and 5 have already been used), you are swimming across the river to get home.

[WindAtMyBack]

Super easy. It took me about 5 seconds to figure it out. But I'm good at these type of puzzles. There is a simple trick to it.

[WindAtMyBack]

Oh wait, I went too fast and screwed up. :) This one can't be done.

[Snsl153]

No, there is no "trick" at all. It's actually impossible to solve.

[WindAtMyBack]

There is a trick to these type of puzzles. This particular one is a little bit different than the ones I used to do. But it's similar. I think some of the same rules will apply.

I don't think you can prove they can be solved without doing it. But in some cases you can prove they can't be solved. You look for even and odd number of vertices. If it has odd number vertices, you have to start or end at them. If it has more than two, it can't be done.

Knowing the start point is a big part of solving it. Most of the rest gets easy with practice. There are certain types of patterns that you use.

Your puzzle has four land masses. Each of them has an odd number of vertices. So it can't be done. If you add one more bridge anywhere, then it can be solved. One bridge changes two land masses from odd to even (one on each side of the bridge). That leaves two odd numbers which can be solved.

[TheSpaceGnome]

You do it by crossing the river.

[Snsl153]

I think we have a winner! :) <3

[Snsl153]

Oh wait, no. Just before you get to bridge 3, you go for a swim. There's no bridge there. Sorry, no prize. :(

[TheSpaceGnome]

The answer is that you have to swim or use a boat to do it.

[exitseven]

This is a problem in IT. There is a process called convergence that happens in a switch. Each node is visited exactly once. I have not done this since grad school but I could probably find my notes.

[normalice]

I remember there being an explanation for why it is not possible but don't remember the explanation.

[boggboss]

Pretty sure it's not possible

[crossdressingrihno]

It's possible

[boggboss]

Without further info I'll have to call lies on that 1

[crossdressingrihno]

You just need to cross all 7 bridges

[crossdressingrihno]

Think of it this way

[crossdressingrihno]

What is the definition of "cross"

[crossdressingrihno]

Does cross necessarily mean you must go from side to the other

[crossdressingrihno]

I'm being cheeky if you can't tell

[Snsl153]

Correct. It's not possible, and this was actually proven back in the late 19th century by a mathematician whose name I cannot now recall.

[FunkyMonkee]

The only way it could be done is if I take a pencil and cross out each bridge one at a time.

[KostasKouvalis]

I heard about this riddle and completely forgot about it until you posted it.
It's called Kaliningrad now.

[Anonymous]

There you go. All bridges crossed. Solved!

[BeMuse]

Graph theory on GaG huh...

[Lost_in_the_Woods]

Yes.
It's easy if you're a good swimmer.

[Waldoe]

cute.. can't be done, thanks for playing

[EnglishEuropean]

Yes, the solution is that it can't be done.

[Anonymous]

Seems to be a play on words here

[Adronicus]

1,5,2,4,7,6,3

[FunkyMonkee]

How would you get from 5 to 2 without crossing at least one other bridge?

[Adronicus]

@FunkyMonkee doesn't say I have to be able to make it off after, just cross each bridge once :p

[FunkyMonkee]

And?

[jimmy2]

Start at 7 end at 4