Enigmatic Code

Programming Enigma Puzzles

Enigma 1158: Anti-Magic

From New Scientist #2314, 27th October 2001 [link]

George quickly solved the popular magic square puzzle which asks you to arrange the numbers 1 to 16 in a 4 × 4 grid so that the four rows. the four columns and the two diagonals all have the same sum — so he tried to be different. He has now found an “Anti-Magic Square”, using the numbers 1 to 16, but the ten totals are all different. They are in fact ten consecutive numbers, but in no particular sequence in relation to the square grid.

One of the diagonals in George’s square contains four consecutive numbers and the other contains four prime numbers, each in ascending numerical order from top to bottom.

One row contains four numbers in ascending numerical order from left to right.

What are those four numbers?

Enigma 8 was also about anti-magic squares.

[enigma1158]

Advertisements

2 responses to “Enigma 1158: Anti-Magic

  1. Jim Randell 18 July 2016 at 8:42 am

    We can suppose that the leading diagonal (NW to SE) is the ascending sequence of primes, and the reverse diagonal (NE to SW) is the ascending consecutive sequence. If we have these the wrong way round then the row we are looking for will be a descending sequence instead of an ascending sequence, so we can just look for either.

    This Python 3 program runs in 577ms.

    from itertools import combinations
    from enigma import irange, Primes, find, chunk, tuples, compare, printf
    
    # consider the grid:
    #
    # 00 01 02 03
    # 04 05 06 07
    # 08 09 10 11
    # 12 13 14 15
    #
    
    # groups in the anti-magic square
    groups = (
      # rows
      (0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15),
      # columns
      (0, 4, 8, 12), (1, 5, 9, 13), (2, 6, 10, 14), (3, 7, 11, 15),
      # diagonals
      (0, 5, 10, 15), (3, 6, 9, 12),
    )
    
    # same as list <s>, except value <v> at index <i>
    def update(s, i, v):
      s = list(s)
      s[i] = v
      return s
    
    # fit numbers <ns> into grid <g> to make an anti-magic square
    # with sums in range <r>
    def solve(g, ns, r):
      # check sums all completed groups are different
      ss = list()
      for group in groups:
        try:
          s = sum(g[i] for i in group)
        except TypeError:
          continue
        ss.append(s)
      # all sums must be different
      if len(set(ss)) != len(ss): return
      # and they need to in the specified range
      s = max(ss) - min(ss)
      if s > r: return
      
      # find the next empty square
      i = find(g, None)
      # are we done?
      if i == -1:
        yield (g, ss)
      else:
        # fill it out
        for n in ns:
          yield from solve(update(g, i, n), ns.difference([n]), r)
    
    # are all the items in <s> the same?
    def same(s):
      i = iter(s)
      # find the first value
      try:
        v0 = next(i)
      except StopIteration:
        return True
      # all remaining values should be the same
      return all(v == v0 for v in i)
    
    # numbers in the square
    ns = set(irange(1, 16))
    
    # suppose the leading diagonal is four ascending primes
    for p in combinations(Primes(16), 4):
      # and the reverse diagonal is four consecutive numbers
      for i in irange(1, 13):
        c = tuple(irange(i, i + 3))
        # the remaining numbers are...
        rs = ns.difference(p, c)
        if len(rs) != 8: continue
    
        # fill out the grid
        grid = (
          p[0], None, None, c[0],
          None, p[1], c[1], None,
          None, c[2], p[2], None,
          c[3], None, None, p[3],
        )
    
        # solve it
        for (g, ss) in solve(grid, rs, 9):
          # one row must be ascending or descending
          rows = list(chunk(g, 4))
          if not any(same(compare(a, b) for (a, b) in tuples(r, 2)) for r in rows): continue
    
          printf("grid = {rows}, sums = {ss}", ss=sorted(ss))
    

    Solution: The ascending row is: 5, 9, 11, 12.

    There are two ways to construct the square:

    Enigma 1158 - Solution

    The positions of 6 and 14 are interchanged in the two solutions.

    In each case the third row is the ascending one, and the sums of the groups are consecutive numbers from 29 to 38.

  2. geoffrounce 18 July 2016 at 6:32 pm

    Yes, I also got two solutions with the four numbers being 5,9,11 and 12 in the third row.
    The ascending numbers are 7,8,9 and 10, and the primes are 2,3,11 and 13.

    % A solution in MiniZinc
    % the grid
    % --------
    % a b c d
    % e f g h
    % i j k l
    % m n o p
    
    include "globals.mzn";
    
    var 1..16: a;  
    var 1..16: b; 
    var 1..16: c; 
    var 1..16: d; 
    var 1..16: e;
    var 1..16: f;  
    var 1..16: g; 
    var 1..16: h; 
    var 1..16: i; 
    var 1..16: j;
    var 1..16: k;  
    var 1..16: l; 
    var 1..16: m; 
    var 1..16: n; 
    var 1..16: o;
    var 1..16: p;
    
    % is_prime
    predicate is_prime(var int: x) = x > 1 /\
       forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ( 
            (i < x) -> (x mod i > 0));
    
    % the anti-magic square grid
    array[1..16] of var int : cwd = [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p];
    constraint all_different(cwd);
    
    % array of row, column and diagonal totals ie 10 totals
    array[1..10] of var int : totals = [a+b+c+d,e+f+g+h, i+j+k+l,m+n+o+p,
    a+e+i+m, b+f+j+n,c+g+k+o, d+h+l+p, a+f+k+p, d+g+j+m];
    
    % sorted totals
    array[1..10] of var int: totals2 = sort(totals); 
    
    % 10 totals must also be 10 consecutive numbers
    constraint (totals2[1] < totals2[2] /\ totals2[2]-totals2[1]==1)
    /\ (totals2[2] < totals2[3] /\ totals2[3]-totals2[2]==1)
    /\ (totals2[3] < totals2[4] /\ totals2[4]-totals2[3]==1)
    /\ (totals2[4] < totals2[5] /\ totals2[5]-totals2[4]==1)
    /\ (totals2[5] < totals2[6] /\ totals2[6]-totals2[5]==1)
    /\ (totals2[6] < totals2[7] /\ totals2[7]-totals2[6]==1)
    /\ (totals2[7] < totals2[8] /\ totals2[8]-totals2[7]==1)
    /\ (totals2[8] < totals2[9] /\ totals2[9]-totals2[8]==1)
    /\ (totals2[9] < totals2[10] /\ totals2[10]-totals2[9]==1);
    
    % sums of rows cols and diagonals are all different
    constraint all_different( [(a+b+c+d), (e+f+g+h), (i+j+k+l), (m+n+o+p),  
    (a+e+i+m), (b+f+j+n), (c+g+k+o), (d+h+l+p), (a+f+k+p), (d+g+j+m)] ); 
    
    % one diagonal has four ascending consecutive numbers from top to bottom
    % and one diagonal has four ascending prime numbers from top to bottom
    constraint ((f-a==1 /\ k-f==1 /\ p-k==1) 
    /\ (is_prime(d) /\ is_prime(g) /\ is_prime(j) /\ is_prime(m))
    /\ ( g>d /\ j>g /\ m>j))
    
    % alternative order for two diagonals
    \/ 
    (( g-d==1 /\ j-g==1 /\ m-j==1) /\ ( is_prime(a) 
    /\ is_prime(f) /\ is_prime(k) /\ is_prime(p))
    /\ (f>a /\ k>f /\ p>k));
    
    % one row is in ascending order from left to right
    constraint (d>c /\ c>b /\ b>a) \/ (h>g /\g>f /\ f>e)
    \/ (l>k /\ k>j /\ j>i) \/ (p>o /\ o>n /\ n>p);
     
    solve satisfy;
    
    output[ "10 totals: ",show(totals2),"\n",
            show(a)," ",show(b)," ",show(c)," ",show(d),"\n",
            show(e)," ",show(f)," ",show(g)," ",show(h),"\n",
            show(i)," ",show(j)," ",show(k)," ",show(l),"\n",
            show(m)," ",show(n)," ",show(o)," ",show(p),"\n"
            ++ "row totals: ", show(a+b+c+d)," ",show(e+f+g+h)," ",
            show(i+j+k+l)," ", show(m+n+o+p) ,"\n"
            ++ "col totals: " , show(a+e+i+m)," ",show(b+f+j+n), " ",
            show(c+g+k+o)," ", show(d+h+l+p),"\n"
            ++ "diagonal totals: ",show(a+f+k+p)," ", show(d+g+j+m),"\n"
          ];
    
    % Output
    %-------soln 1-----------------
    % 10 totals: [29, 30, 31, 32, 33, 34, 35, 36, 37, 38]
    % 2 6 15 7
    % 16 3 8 4
    % 5 9 11 12
    % 10 14 1 13
    % row totals: 30 31 37 38
    % col totals: 33 32 35 36
    % diagonal totals: 29 34
    % ----------soln 2------
    % 10 totals: [29, 30, 31, 32, 33, 34, 35, 36, 37, 38]
    % 2 14 15 7
    % 16 3 8 4
    % 5 9 11 12
    % 10 6 1 13
    % row totals: 38 31 37 30
    % col totals: 33 32 35 36
    % diagonal totals: 29 34
    % ----------------------
    % Finished in 96msec
    
    

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: