Enigmatic Code

Programming Enigma Puzzles

Enigma 257: Hexa-draughts

From New Scientist #1404, 5th April 1984 [link]

This is an easy introduction to Hexa-draughts, which is played on a board with a “hexagonal” pattern of points extending as far as you like in all directions.

First you place a number of men on points on or below Row 0. That is your start position. Then you hop, as in draughts: one man A hops over an adjacent man B, landing on the point beyond, and removing B from the board. And so on, till only one man is left, as far as possible above Row 0.

The picture shows a start position with three men — the fewest needed to get a man to row 2; so we say M(2) = 3. The numbers in the circles and the arrows on them show the order and direction of hops.

Enigma 257

What is M(4)?

The setter added the following note:

If you find this interesting, you may like to seek M(5), M(6), and M(7). My best answers so far are 17, 38, and “probably impossible”. If you can do better, no prizes, but I should rather like to know M(8) is certainly impossible.

With this puzzle the prize offered for Enigma solutions was increased from £5 to £10.

When Enigma was launched the cover price of New Scientist was 35p, so the prize would buy 14.3 copies of the magazine. By 1984 the cover price of the magazine had risen to 90p, so the purchasing power of the £5 prize had dwindled to only 5.6 copies of the magazine. The increase of the prize to £10 brings it up to 11.1 copies.

At some point between 1996 and 2000 the prize was increased again to £15. When the final Enigma puzzle was published in 2013 the cover price of the magazine was £3.80 (actually the Christmas edition was £3.95), and the prize was £15, which would only buy 3.9 copies of the magazine. If the cover price to prize ratio from Enigma 1 had been maintained the prize would have been £55.

[enigma257]

Advertisements

5 responses to “Enigma 257: Hexa-draughts

  1. Jim Randell 10 February 2015 at 8:28 am

    This program works backwards from a starting position of a single man in the specified row (default: 4), and works backwards to find possible starting positions. It runs in 4.5s.

    from collections import defaultdict
    from enigma import flatten, Accumulator, printf
    
    # pieces are represented by a row number and a column number
    # in each row pieces can only occupy odd/even columns, the parity
    # alternates with the rows
    
    # ps - pieces, a dict mapping row to column numbers
    # n - number of pieces on the board
    # s - accumulator for minimal solutions
    def solve(ps, n, s):
      # find pieces in row > 0
      ms = flatten(((r, v) for v in vs) for (r, vs) in ps.items() if r > 0)
      # are we done?
      if not(ms):
        s.accumulate_data(n, ps)
        if n == s.value:
          printf("[{n} => {ps}]")
      elif (s.value is None or n < s.value):
        # move one of them
        for r in sorted(ps.keys(), reverse=True):
          for v in ps[r]:
            for d in (-1, 1):
              # replace (r, v) with (r - 1, v + d) and (r - 2, v + 2d)
              (v1, v2) = (v + d, v + 2 * d)
              if v1 in ps[r - 1] or v2 in ps[r - 2]: continue
              ps2 = ps.copy()
              ps2[r] = ps[r].difference([v])
              ps2[r - 1] = ps[r - 1].union([v1])
              ps2[r - 2] = ps[r - 2].union([v2])
              solve(ps2, n + 1, s)
    
    
    import sys
    N = (4 if len(sys.argv) < 2 else int(sys.argv[1]))
    M = (None if len(sys.argv) < 3 else int(sys.argv[2]))
    
    ps = defaultdict(set)
    ps[N].add(0)
    s = Accumulator(fn=min, value=M)
    solve(ps, 1, s)
    
    printf("M({N}) = {s.value} [{d}]", d=(None if s.data is None else dict((k, sorted(vs)) for (k, vs) in s.data.items())))
    

    Solution: M(4) = 9.

    The program finds 408 possible starting positions, one of them is shown below.

    Enigma 257 - Solution

    (In the final diagram the solid outlined pieces are moved to give the dashed outlined pieces which are then moved to give the final solid black piece, which is the required single piece in row 4).

    I’m not entirely happy with this program. As the game progresses backwards we have an increasing number of pieces on the board. (Each move (forwards) removes one piece from play), and so in a depth first search (which is what this program is), we could end up on an infinitely regressive path without reaching a solution. The program does start looking at moving pieces with a higher row number first (which makes sense because we want to clear the positive rows of pieces), and if it does find a solution it will then skip positions involving more pieces than the current best solution. You can provide this upper bound as a command line argument, but even this doesn’t make it suitable for exploring solutions to M(N) for N > 4 in a reasonable time.

    On the plus side, it is a fairly simple program, and it does solve the stated problem without too much fuss.

    • Hugh Casement 21 August 2015 at 9:25 am

      Jim,
      Were you able to confirm or refute that M(5) = 17 and M(6) = 38?
      Are M(7) and higher really infinite, or are there just too many possible starting configurations?

      • Jim Randell 21 August 2015 at 10:25 pm

        Fortunately my simple program was able to compute M(4) in a reasonable time. Unfortunately for the larger versions of the puzzle a more sophisticated approach would be needed, so I was unable to compute M(5) (or larger) using it.

  2. arthurvause 5 January 2016 at 10:45 am

    The puzzle is the hexagonal variation of “Conway’s Soldiers”, described in The Peg Solitaire Army, which confirms that M(8) is impossible, and give theorectical and achieved bounds for the number of men required for M(5), M(6), M(7).

    • Jim Randell 6 January 2016 at 7:34 pm

      Thanks for finding that. The paper “The Minimum Size Required of a Solitaire Army” (Bell, Hirschberg, Guerrero-Garcia, 2007) looks interesting, and I note that in 2008 the authors completed the calculation of M(7) = 145, and it took 47 hours of computer time. So I don’t feel so bad about the performance of my fairly simple program.

      For the record: M(1) = 2, M(2) = 3, M(3) = 5, M(4) = 9, M(5) = 17, M(6) = 36, M(7) = 145. Higher values are not possible.

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: