Last week’s Micro Softy 12 concerned connecting 9 dots with four straight lines.  Before revealing the solution, I’d like to say a word about connecting dots in general.

Imagine a map of streets that must be traveled by a truck picking up garbage. To avoid wasting time and fuel, the driver’s best route traverses no street more than once. Such routes, when they exist, are called Eulerian paths. after the greatest mathematician of all time, Leonhard Euler (1707‒1783). However, Euler’s original solution to this problem was named the “Seven Bridges of Königsberg.”

An Eulerian path is possible when the number of streets branching out from every intersection is an even number. An intersection is where two or more streets meet. An example is on the left in Figure 1.  In the example figure every intersection that is not a start or stop point connects either 2, 4 or 6 streets. An Eulerian path is therefore possible. One such path is shown on the right in Figure 1.

Figure 1: When an Eulerian path ends where it begins, the path is called an Eulerian cycle.

An Eulerian path

This week’s Micro Softy challenges you to find a specific type of Eulerian path.  Think of a long string, laid down to follow a path. The path must be laid out so that the string never crosses itself. For the example in Figure 1, the string crosses itself a number of times.  

This type of non-overlapping Eulerian graph has practical applications. Think, for example, of laying a water pipe that must be exactly 2 feet below the surface. The plan for laying the pipe must be such that pipe paths do not cross.

One example is the envelope shape shown at the top left of Figure 2 below.  The non-overlapping string path is shown in red at the right. A second example is shown below that in the same figure:

Figure 2: Two examples of ways that a string can be configured so that it never overlaps itself.

And now, the Micro Softy…

This week’s Micro Softy has two parts. We’ll start with the three simple problems shown in Figure 3. For each, bend a string to follow the path without the string ever overlapping itself.

Figure 3: Simpler problems.

Once the puzzles in Figure 3 are mastered, let’s turn our attention to a more difficult problem: a stained-glass window. The dark lead strips that separate panes of colored glass in a stained-glass window are called cames. For the stained-glass window in Figure 4, can one long came be bent for the whole window? (The rectangular frame is not included.) As is the case for strings, we want no bumps so there can be no overlap in the path:

Figure 4: Can one long lead came strip be used for this stained-glass window?

The answers will be given in next Monday’s Micro Softy column.

Solution for Micro Softy 12:  Connect the Dots

Last week’s Micro Softy is a classic puzzle. Can nine dots in a rectangular 3 × 3 grid all be connected with four straight lines? Recall that the lines must be drawn without taking the pencil off the paper.

The answer is shown in Figure 5. When the original puzzle is given, the 9 dots are enclosed in a shaded box. A falsely inferred rule is that the lines must lie totally inside the square. But that was never said. As seen in Figure 5, the answer uses lines drawn outside the square:

Figure 5: Thinking outside the box.

The second question in Micro Softy 12 asked what common expression this puzzle gave rise to. Yes, it is the origin of the familiar phrase “Thinking outside the box.” I often explain a limitation of AI by saying is does not have the ability to “think outside of the box.”

Explaining the puzzle that gave rise to this expression without drawing is difficult, as you can see from this clip of an interview I had with Michael Medved:

Note: At Monday Micro Softy 11: What Happened to That Other Dollar?, you will also find links to the first ten Micro Softies. Have fun!