Enigmatic Code

Programming Enigma Puzzles

Enigma 328: Nine men went to mow

From New Scientist #1476, 3rd October 1985 [link]

Enigma 328

Nine men went to mow, went to mow a meadow. Write “9” in one of the meadows. Eight men left the ninth in the meadow and went through a gate into the next. Write “8” in the meadow they went into. Seven men left the eighth behind and went through a gate. Write “7” in the meadow they went into. Carry on in this way until you have “6”, “5”, “4”, “3”, “2” and “1” duly inscribed in the remaining meadows. You must use a gate each time and never enter the same meadow twice.

That gives you a three-digit number on each of the three lines. Try adding the top number to the middle number and see if they sum to the bottom number. If not, bad luck — you’ll have to sing the song all over again.

When you have got it right, please give the completed grid.

This puzzle had previously been published in New Scientist #1018 as Tantalizer 467.

[enigma328]

Advertisements

4 responses to “Enigma 328: Nine men went to mow

  1. Jim Randell 15 January 2016 at 7:59 am

    This Python 3 program generates all possible arrangements of the grid, and then checks to see if the first two rows sum to the third.

    It runs in 55ms, so there seems little point in optimising it.

    Run: [ @repl.it ]

    from enigma import irange, nconcat, printf
    
    # consider the following indices into the grid:
    #
    # 0 1 2
    # 3 4 5
    # 6 7 8
    
    # adjacency matrix
    adj = [
      (1, 3), # 0
      (0, 2, 4), # 1
      (1, 5), # 2
      (0, 4, 6), # 3
      (1, 3, 5, 7), # 4
      (2, 4, 8), # 5
      (3, 7), # 6
      (4, 6, 8), # 7
      (5, 7), # 8
    ]
    
    # generate completed grids with <n> at index <i>
    def generate(grid, i, n):
      # place n at index i
      grid[i] = n
      # are we done?
      if n == 9:
        yield grid
      else:
        # move to an adjacent square
        for j in adj[i]:
          if grid[j] == None:
            yield from generate(grid, j, n + 1)
      # empty the square
      grid[i] = None
    
    # where to start
    for i in irange(0, 8):
      grid = [None] * 9
      for g in generate(grid, i, 1):
        # look for cases where the top row plus the second row equals the third row
        (a, b, c) = (nconcat(g[j::3]) for j in (0, 1, 2))
        if a + b == c:
          printf("{a} + {b} = {c}")
    

    Solution: The completed grid is shown below:

    Enigma 328 - Solution

  2. Jim Randell 16 January 2016 at 8:09 am

    Here’s an alternative solution, which starts by solving the substituted sum problem (using the SubstitutedSum() solver from the enigma.py library), and then checks the adjacency condition. It’s a shorter, but slightly slower program. It runs in 90ms.

    from enigma import SubstitutedSum, irange, tuples, printf
    
    # consider the following indices into the grid:
    #
    # 0 1 2
    # 3 4 5
    # 6 7 8
    
    # adjacency matrix
    adj = [
      (1, 3), # 0
      (0, 2, 4), # 1
      (1, 5), # 2
      (0, 4, 6), # 3
      (1, 3, 5, 7), # 4
      (2, 4, 8), # 5
      (3, 7), # 6
      (4, 6, 8), # 7
      (5, 7), # 8
    ]
    
    # digits
    digits = list(irange(1, 9))
    
    # solve the problem as a substituted sum
    p = SubstitutedSum(['012', '345'], '678', digits=digits)
    for s in p.solve():
      # map digit -> index
      m = dict((v, int(k)) for (k, v) in s.items())
      # and check the adjacency conditions
      if not all(m[b] in adj[m[a]] for (a, b) in tuples(digits, 2)): continue
      # output the solution
      p.solution(s)
    
    • geoffrounce 17 January 2016 at 3:26 pm
      # permutation values for the sum
      # a b c
      # d e f
      # g h i
      
      from itertools import permutations
      
      for p in permutations((1,2,3,4,5,6,7,8,9)):
          a,b,c,d,e,f,g,h,i = p
          
          # find the required sum
          if (100*a + 10*b + c) + (100*d + 10*e + f) \
             == (100*g + 10*h + i):
      
              # check permutation values are in Jim's adjacency matrix
              if a in (1, b+1, d+1) and b in (1, a+1, c+1, e+1) and \
              c in (1, b+1, f+1) and d in (1, a+1, e+1, g+1) and \
              e in (1, b+1, d+1, f+1, h+1) and f in (1, c+1, e+1, i+1) and \
              g in (1, d+1, h+1) and h in (1, e+1, g+1, i+1) and \
              i in (1, f+1, h+1):
                  # the solution
                  print(a,b,c,'+', d,e,f, '=',g,h,i)           
      # Output
      # 1 2 9 + 4 3 8  = 5 6 7 
      
      • geoffrounce 7 February 2016 at 11:40 am
        % A solution in MiniZinc
        % required sum for the three lines is abc + def = ghi
        
        include "globals.mzn"; 
        
        set of int: meadow = 1..9;
        var meadow : a;  var meadow : b;  var meadow : c;
        var meadow : d;  var meadow : e;  var meadow : f;
        var meadow : g;  var meadow : h;  var meadow : i;
        
        constraint all_different([a,b,c,d,e,f,g,h,i]);
        
        solve satisfy;
        
        % conditions for the adjacency matrix
        constraint i = 1 \/ i = f+1 \/ i = h+1;
        constraint h = 1 \/ h = i+1 \/ h = g+1 \/ h = e+1;
        constraint g = 1 \/ g = h+1 \/ g = d+1;
        constraint f = 1 \/ f = c+1 \/ f = e+1 \/ f = i+1;
        constraint e = 1 \/ e = h+1 \/ e = b+1 \/ b = d+1 \/ b= f+1;
        constraint d = 1 \/ d = e+1 \/ d = a+1 \/ d = g+1;
        constraint c = 1 \/ c = b+1 \/ c = f+1;
        constraint b = 1 \/ b = a+1 \/ b = e+1 \/ b = c;
        constraint a = 1 \/ a = b+1 \/ a = d+1;
        
        constraint (100*a + 10*b + c) + (100*d + 10*e + f)
                  == (100*g + 10*h + i);
        
        % show number grid ie abc + def = ghi
        output[show(a),show(b), show(c)," + ",show(d), show(e),
               show(f)," = ",show(g), show(h),show(i)];
        
        % Output: 129 + 438 = 567
        %
        
        

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: