[Search] Search   [Recent Topics] Recent Topics   [Members]  Member Listing   [Groups] Back to home page 
Editorial for Hamilton Maze Puzzle #5542 by Johan
Forum Index -> Editorials
Author Message


Joined: 22/12/2006 20:08:51
Messages: 1046

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:

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).

Thanks for reading!


Joined: 31/07/2009 06:59:16
Messages: 146

Thanks for sharing that nice detailed explanation of this puzzle Johan. I often use the method of testing various assumptions to try solving puzzles of all kinds, and when one assumption is proven wrong this helps me to proceed toward the correct path. This is not just "trial-and-error," but rather the process of elimination. This often helps me in solving tricky alphametics puzzles, where numbers have been replaced by letters. Thanks again!


Joined: 22/12/2006 20:08:51
Messages: 1046

For this Valentine's Day I made a video in which I solve this puzzle step by step (largely based on the original post).


Apologies for the rather poor sound quality. A combination of a poor microphone, my Dutch accent and my new braces. It does have subtitles though.
Forum Index -> Editorials
Go to:   
Powered by JForum 2.1.6 © JForum Team