Forums
Author Message
Johan

Joined: 22/12/2006 20:08:51
Messages: 1010
Online

Number: Puzzle #5542
Genre: Hamilton Maze
Author: Johan
Appeared at: February 14, 2017
Warning: This post contains spoilers.

The puzzle
Draw a single loop that goes through every node exactly once. At bridges, the line is allowed to cross itself.

How to solve it
A first observation is that since every node must be visited, any node with exactly two adjacent edges forces both these edges to be used. There are 5 such nodes in this puzzle.

For the second observation, consider the red line in the image above. It indicates that the top left component is connected to the rest of the puzzle by means of three edges. Since the loop must enter the component as often as it leaves it (and must in fact enter it), we know that exactly two of these three edges must be used.

Now consider the possibility that the edge crossed out with the short red line in the image above is not part of the solution. It would follow that the green edges are part of the solution. This is problematic, given that we know we can't escape the top left component anymore. Hence, our assumption that the crossed out edge was not part of the solution, was wrong. We can safely assume it is part of the solution.

By repeatedly marking edges which can no longer be used, because we already chose two edges adjacent to a node, and choosing two edges adjacent to a node when only two possible edges remain, we end up in the situation below. The edge crossed out with a red line can not be used, because it would create a small loop. The green edge was chosen to connect the top left component.

In order to connect the top part to the bottom part, we must use the green edges in the next image:

Assume for a moment that the red edge is part of the solution. If we try to connect the two endpoints in the upper left, we will have to choose exactly one of the two remaining nodes, and leave the other unused. Therefore, we can conclude that the red edge is not supposed to be used.

From here on, it is more of the same: We make sure that for every node we choose exactly two edges and we avoid creating smaller loops, until we see this:

Afterthoughts
In case you wonder how you could know in advance that the assumptions used here would be the ones to quickly lead to useful contradictions, or that some particular components' inter-connectivity would be helpful to focus on, the answer is that often you don't know until you try.

Use your intuition to identify possible weaknesses in the puzzle's defense - places that might give way when you apply a little bit of logic. The more the puzzle resists, the more pressure you will have to apply, sometimes even building assumption upon assumption (backtracking).