3
$\begingroup$

Leonhard Euler proved that it is impossible to solve this puzzle:

wikimedia

The challenge is to take a walk around the area depicted, and cross each bridge (yellow) exactly once. Using topology, Euler proved that it is impossible to walk each bridge exactly once.

Are there any similar challenges? I would like to try to solve a more complex one.

$\endgroup$
  • $\begingroup$ I've seen a variant 'pass each door exactly once without crossing your own path'. I can't find it currently though. $\endgroup$ – SF. May 17 '14 at 14:48
5
$\begingroup$

It would be easy to make an impossible puzzle like this. First, draw some rivers and temporarily number the areas that there are (not required, just used for reference in this answer):

rivers

Then, draw some bridges and count how many of the areas have an odd amount of bridges going out:

bridges

The red numbers are how many bridges there are that come out from that area. Since areas 1, 2, 4, and 6 have an odd number of bridges, this puzzle is complete! This is because there has to be exactly zero or two areas with an odd number of bridges for the walk to be possible.

To answer your question literally, no, there is no "list" or "collection" of these puzzles, since each one would be so similar and solved the same way that it would be pointless. The real puzzle is figuring out why there has to be zero or two nodes with an odd number of entry/exits (which is also discussed in the Wikipedia article linked above).

$\endgroup$
3
$\begingroup$

this is the Eulerian path problem

If there are more than 2 points with an odd number of bridges then the problem is impossible, when here are exactly 0 or 2 such points then it is possible, with 2 odd points you start at one and then end up at the other, with 0 you come back where you start.

The solution for the path is simple,

Start at a point with an odd number of bridges and add it to your path and remove it from the set, from there move further by picking any bridge forward, repeat until there are no more bridges at your current point.

Then at a point you passed and there are still bridges to cross split your path there and go over a bridge until you eventually come back to that point. Reconnect the path with the one you just followed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.