Friday, February 17, 2012

An Eulerian Hoax

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.

Monday, February 13, 2012

Troubling Bridges

A long time ago, my father taught me a simple drawing game over which I would obsess for quite a while. It went like this: you first draw a certain shape (preferably with an ink pen), and you then try to cross through all the line segments at once, with a single stroke (i.e. without raising what is preferably a pencil) and without visiting a given segment twice.

I tried to recreate the spirit of this game (in memory of my father perhaps) as an experiment to learn the Processing.js platform. To test the game mechanics, you can try an easy puzzle first (click anywhere on the grid to place the cursor, and drag any of its ends through the segments, with the goal of turning them all green; you can press "r" to reset, "b" or right-click to move back, or use the yellow and blue buttons at the top):

This was of course trivially easy.. but what about this slight modification, for which I once filled entire notebooks of trials? (I'm not kidding!):

You can try it for yourself:

A few attempts will probably convince you that it's much harder.. but can you see why? In a next post, I'd like to say more about it. I also plan to describe the code and algorithms I have devised, as I greatly enjoyed my first contact with Processing, and I have many good things to say about it. I'm also thinking that this simple pixel grid world engine could be reused to build some other childhood-inspired games..

Don't miss the following conclusion!