Eight Digits Puzzle

The applet below is a game board for a puzzle. The task is to place eight digits 1 through 8 into eight circles, but there is a caveat. Some of the circles are connected as shown and, for this reason are considered neighbors. The numbers should be placed so that no two successive digits are placed into neighboring circles.

The applet keeps for you the count of the assigned digits. You should only decide where to place the next digit. You do that by clicking on the circle of your choice. You can remove the last placement either by clicking on the corresponding circle or by pressing the "Step back" button at the bottom of the applet. The applet also warns you whenever you place two successive digits into neighboring circles.

Please try switching to IE 11 (Windows) or Safari (Mac), for no other browser nowadays runs Java applets. If asked whether to allow the applet to load, click Yes - the applet is signed with a security certificate from a trusted company. But, regardless, there is an explanation below.

What if applet does not run?

Solution

References

M. Gardner, The Unexpected Hanging and Other Mathematical Diversions, Chicago University Press, 1991
M. Gardner, The Colossal Book of Short Puzzles and Problems, W. W. Norton & Company, 2006, p. 6

Up to reflection and rotation there is only one solution. There are two key observations:

The two center circles are neighbors to six other locations. All other circles have fewer neighbors.
Except of 1 and 8, other digits appear in two "forbidden" pairs. For example, 3 could not stand next to 2 and 4, whereas 8 could not stand next only to 7.

It is therefore clear that both 1 and 8 must, between them, split the two center circles. All other digits will by necessity run into either successors and predecessors.

From here on it's all trial and error, unless you move to the complementary diagram.

The diagram can of course be looked at as a graph whereas the digits are being assigned to its nodes. Our graph is not complete: some edges are missing. We may consider the complementary graph: a graph with the same nodes and the edges missing at the outset. In terms of the complementary graph, the task is to find a Hamilton path on the graph and assign the digits to the nodes of the path in their natural order. Since the center nodes in the complementary graph have only 1 neighbor each, these two nodes must serve as the head and the tail of the path. Other than that, there are just a few choices to make. These are still made by trial and error, but there appear fewer choices than in the original graph.

71537243