Let's end the suspense.. there was a big catch with the previous puzzle: it was impossible to solve!
As you may have suspected, the reason is mathematical, and it boils down to the fact that the puzzle actually corresponds to the dual graph of another graph, this one lacking an essential property: an Eulerian path. Even though it may appear different at first, this is actually quite similar to the well-known problem of the Seven Bridges of Königsberg, which was solved by Euler in 1735.
To explore what it means in more details, let's first consider the first, easy problem and its dual graph. The dual graph (in red) models the topology of the regions implicitly formed by the edge network of the blue graph: it tells which region connects to which. Notice that the space surrounding the blue graph, being a single region, corresponds to the top red node, reachable by all the red nodes lying in a region with "outside facing (blue) walls":
Starting at the top red node (i.e. "outside", in terms of the dual graph), there exists a path (that can be followed with the arrows) with which we will eventually follow every red edges, without visiting any one twice: this is an Eulerian path (since this path is starting and ending at the same node, it's actually more precisely an Eulerian circuit). A path in this graph corresponds to a "pencil path" across the blue edges (or "walls") of the puzzle graph:
Now while trying to solve the previous, impossible puzzle (in blue), you were in reality trying to find an Eulerian path within its dual graph (in red):
which was proven impossible by Euler in this particular case, because it does not satisfy the (necessary and sufficient) condition of having zero or two (red) nodes of degree two. Specifically, as can be seen, it has four nodes of odd degree.
Just for fun, let's do the opposite, and try to cast the graph of the Königsberg problem into a form suitable for another interactive puzzle applet. From the simple and compact graph that can be derived from the bridge and island structure, it's not immediately clear how to do this (at least not in terms of the straight segments that the applet requires, as far as I can see):
But if we simply rearrange the edge between the top and bottom nodes, it becomes easy:
which yields this (impossible, you've been warned this time!) puzzle (click anywhere on the grid to place the cursor, and drag any of its ends through the segments; you can press "r" to reset, "b" or right-click to move back, or use the yellow and blue buttons at the top):
(The applet was created with Processing.js)
I'd say this one is more suspect as a puzzle, in the sense that you can rapidly almost feel its impossibility.. in a way that the previous, more complicated one was better able to conceal.
Maybe that explains why, even after my father had told me it was impossible, I kept trying to solve it stubbornly, fascinated by its paradoxical nature.
I saw this post and memories flooded back of my own notebooks filled with this problem. I had a teacher introduce me to the problem in Grade 5, but he never mentioned it was impossible. In boring meetings sometimes I would still attempt to prove that there was no solution.
ReplyDeleteAfter I saw your post I tried to avoid looking up Euler's proof, and I came up with my own, based on graph theory as well. In my understanding, if you want to visit every edge exactly once, any node of odd degree must be at the start or the end of the path, but not both. This is because you have to enter and leave any node that is not the final or start node, which implies that you can only visit a multiple of two nodes.
Since there are more than two nodes with odd degree, this is impossible. It isn't sufficient to have two or less nodes with odd degree, but it works for this situation.
I really, really feel a strong relief after solving this. Thanks!