Enigmatic Code

Programming Enigma Puzzles

Enigma 175: Hexagon-wiggling

From New Scientist #1320, 26th August 1982 [link]

Enigma 175

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 (a) has been wiggled with complete success according to these rules. Can you wiggle those at (b) and (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

One response to “Enigma 175: Hexagon-wiggling

  1. Jim Randell 11 March 2014 at 8:12 am

    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.

    from itertools import product
    from enigma import irange, printf
    
    N = 100
    
    # generate points
    def shape(n, r):
      points = set()
      for (x, y) in product(irange(0, n), repeat=2):
        if (x, y) not in r:
          points.add(x + N * y)
      return points
    
    moves = (+1, -1, +N, -N, +(N - 1), -(N - 1))
    
    def wiggle(ps, n, points):
      # are we done?
      if n == 0:
        yield ps
      else:
        # add a node
        p = ps[-1]
        for d in moves:
          if len(ps) > 1 and abs(d) == abs(ps[-1] - ps[-2]): continue
          q = p + d
          if q not in points: continue
          if q in ps: continue
          yield from wiggle(ps + [q], n - 1, points)
    
    def solve(points):
      best = None
      for p in points:
        for ps in wiggle([p], len(points) - 1, points):
          # can the path be closed?
          d = ps[-1] - ps[0]
          if d in moves and abs(d) != abs(ps[-1] - ps[-2]):
            print(ps + [ps[0]], '*')
            return ps + [ps[0]]
          elif best is None:
            print(ps)
            best = ps
      return best
    
    shapes = (
      shape(3, ((0, 0), (2, 3), (3, 2), (3, 3))),
      shape(4, ((0, 0), (0, 1), (1, 0), (3, 4), (4, 3), (4, 4))),
      shape(5, ((0, 0), (0, 1), (1, 0), (3, 5), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5))),
    )
    
    import sys
    args = ((1, 2) if len(sys.argv) < 2 else tuple(int(x) for x in sys.argv[1:]))
    
    for i in args:
      s = shapes[i]
      p = solve(s)
    

    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:

    Enigma 175 - Solution

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: