### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,114)
- misc (2)
- project euler (2)
- puzzle (29)
- site news (43)
- tantalizer (29)
- teaser (3)

### Site Stats

- 166,224 hits

Programming Enigma Puzzles

11 March 2014

Posted by on **From New Scientist #1320, 26th August 1982** [link]

The rules for hexagon-wiggling are simple. You start with a hexagonal pattern of dots, lying in the junctions of a regular 60° grid. You then begin at any dot, and follow path from dot to dot along the grid lines. You must wiggle at every dot you come to you; that is, each leg of the path must lie at 60° or 120° to the previous leg. Your path must include every dot. Finally, the path should, if possible, be re-entrant.

The hexagon at

has been wiggled with complete success according to these rules. Can you wiggle those at(a)and(b)?(c)

The term “re-entrant” is used here to denote that the path is closed (i.e. a loop or circuit that can be started at any point, rather than an open path with a beginning and an end).

[enigma175]

Advertisements

%d bloggers like this:

I considered the nodes to be laid out on an triangular gird (with 60° between the axes). I represent the nodes by an integer. The point (x, y) is represented by (x + N × y) for sufficiently large N that we don’t suffer from “wraparound” issues. The program uses N=100, which is sufficiently large for the relatively small shapes of the problem, and translates the point (x, y) to the integer y0x, which is easy to decode (for points with single digit co-ordinates, which is all that is required for this problem).

Moves are then also represented by integers, by calculating the difference between the destination node and the source node. For example moving parallel to the x-axis: (x, y) -> (x+1, y) is represented by +1, (x, y) -> (x-1, y) is represented by -1. Moving parallel to the y-axis is represented by +100 and -100, and moving along the x+y=n direction is represented by +99 and -99. These represent the six possible moves from each point (providing there is a destination point in the required direction). Moves along the same axis have the same magnitude (absolute value).

Then a straightforward search gives the solution. The program attempts to start a path from each node, which is a bit wasteful, but if the path can be closed it is returned immediately, and so, in this case, only paths from the first point will be considered. However, if there is no closed path then the program will exhaustively try to construct all possible paths from each node, and this number of candidate paths could be reduced by symmetry, but for the relatively small shapes given in the puzzle it is not really a problem.

This Python 3 program finds a solution for (a) in 50ms, for (b) in 5.1s and for (c) in 2.0s.

Solution:The hexagon (b) can be wiggled but not using a closed path. The hexagon (c) can be wiggled using a closed path.Here are the paths my program finds, but there are other solutions: