Enigmatic Code

Programming Enigma Puzzles

Enigma 1740: Sudoprime

From New Scientist #2908, 16th March 2013 [link]

Enigma 1740The grid above shows a cross-figure with two digits given as a start. The 11 answers are distinct primes and none has a leading zero. No digit appears more than once in any row, column or either of the two long diagonals.

What are the numbers in the shaded regions?

[enigma1740]

Advertisements

11 responses to “Enigma 1740: Sudoprime

  1. Jim Randell 13 March 2013 at 8:31 pm

    This (not very pretty) Python program runs in 60ms. It’s somewhat similar to my original solution of Enigma 1730.

    # in the grid:
    #
    #  A # # # B
    #  C D # E F
    #  # G H J #
    #  K L # M N
    #  P # # # Q
    #
    # the primes are:
    # p1 = AC, p2 = BF, p3 = CD, p4 = DGL, p5 = EF, p6 = EJM
    # p7 = GHJ, p8 = KL, p9 = KP, p10 = MN, p11 = NQ
    
    from enigma import Primes, is_duplicate, printf
    
    # record 1, 2, 3 digit primes
    ps = [ None, [], [], [] ]
    for n in Primes(999):
      p = str(n)
      if not is_duplicate(p):
        ps[len(p)].append(p)
    
    # p7 is a 3-digit prime with 9 in the middle
    for p7 in ps[3]:
      if p7[1] != '9': continue
      # p4 is a 3-digit prime with p7[0] in the middle
      for p4 in ps[3]:
        if p4[1] != p7[0]: continue
        # p6 is a 3-digit prime with p7[2] in the middle
        for p6 in ps[3]:
          if p6[1] != p7[2]: continue
          # p3 is a 2-digit prime ending in p4[0]
          for p3 in ps[2]:
            if p3[1] != p4[0]: continue
            # p1 is now defined, so check it's a 2-digit prime
            p1 = '5' + p3[0]
            if p1 not in ps[2]: continue
            # p5 is a 2-digit prime starting with p6[0]
            for p5 in ps[2]:
              if p5[0] != p6[0]: continue
              # check all the digits in row 2 are different
              if is_duplicate(p3 + p5): continue
              # p8 is a 2-digit prime ending with p4[2]
              for p8 in ps[2]:
                if p8[1] != p4[2]: continue
                # p9 is a 2-digit prime starting with p8[0]
                for p9 in ps[2]:
                  if p9[0] != p8[0]: continue
                  # check all the digits in column 1 are different
                  if is_duplicate(p1 + p9): continue
                  # p2 is a 2-digit prime ending with p5[1]
                  for p2 in ps[2]:
                    if p2[1] != p5[1]: continue
                    # check all the digits in row 1 are different
                    if p1[0] == p2[0]: continue
                    # check all the digits in the NE/SW diagonal are different
                    if is_duplicate(p2[0] + p5[0] + p7[1] + p4[2] + p9[1]): continue
                    # p10 is a 2-digit prime starting with p6[2]
                    for p10 in ps[2]:
                      if p10[0] != p6[2]: continue
                      # check all the digits in row 4 are different
                      if is_duplicate(p8 + p10): continue
                      # p11 is a 2-digit prime starting with p10[1]
                      for p11 in ps[2]:
                        if p11[0] != p10[1]: continue
                        # check all the digits in row 4 are different
                        if p9[1] == p11[1]: continue
                        # check all digits in column 4 are different
                        if is_duplicate(p2 + p11): continue
                        # check all digits on the NW/SE diagonal are different
                        if is_duplicate(p1[0] + p3[1] + p7[1] + p6[2] + p11[1]): continue
                        if len(set((p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11))) != 11: continue
    
                        printf("p6={p6} p9={p9} [p1={p1} p2={p2} p3={p3} p4={p4} p5={p5} p7={p7} p8={p8} p10={p10} p11={p11}]")
    

    Solution: The numbers in the shaded regions are 617 and 41.

    • Jim Randell 14 March 2013 at 11:44 am

      Here’s a recursive approach that runs in 79ms. So it’s a little bit slower, but it was more interesting to program.

      # in the grid:
      #
      #  A # # # B
      #  C D # E F
      #  # G H J #
      #  K L # M N
      #  P # # # Q
      
      from enigma import irange, Primes, is_duplicate, printf
      
      # label the indices to make things easier
      (A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = irange(0, 14)
      
      # digits that form primes
      primes = (
        (A, C), (K, P), (B, F), (N, Q),
        (C, D), (E, F), (K, L), (M, N),
        (D, G, L), (G, H, J), (E, J, M)
      )
      
      # groups of distinct digits
      groups = (
        (A, B), (C, D, E, F), (G, H, J), (K, L, M, N), (P, Q),
        (A, C, K, P), (D, G, L), (E, J, M), (B, F, N, Q),
        (A, D, H, M, Q), (B, E, H, L, P)
      )
      
      # 2- and 3-digit primes without repeated digits
      ps = [None, set(), set(), set()]
      for p in Primes(999):
        s = str(p)
        if is_duplicate(s): continue
        ps[len(s)].add(s)
      
      # output a solution
      def output(g):
        (A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = g
        printf("{A} # # # {B}\n{C} {D} # {E} {F}\n# {G} {H} {J} #\n{K} {L} # {M} {N}\n{P} # # # {Q}")
        printf("{E}{J}{M} {K}{P}\n")
      
      # match numbers in ns to the template t
      def match(t, ns):
        for n in ns:
          if all(a in ('?', b) for (a, b) in zip(t, n)):
            yield n
      
      # return an updated grid with digits in template t set to n
      def update(g, t, n):
        g = list(g)
        for (i, d) in zip(t, n):
          g[i] = d
        return g
      
      # check that groups don't have repeating digits
      def check(g):
        for d in groups:
          s = tuple(g[i] for i in d if g[i] != '?')
          if len(s) > 0 and len(set(s)) < len(s): return False
        return True
      
      # solve a grid
      def solve(g):
        # are we done?
        if '?' not in g:
          # check the numbers are distinct primes
          ns = set(''.join(g[i] for i in p) for p in primes)
          if len(ns.intersection(ps[2].union(ps[3]))) == len(primes):
            output(g)
          return
        # find a partially filled out prime
        for p in primes:
          t = tuple(g[i] for i in p)
          if 0 < t.count('?') < len(t): break
        # and fill it out
        for n in match(t, ps[len(p)]):
          g2 = update(g, p, n)
          if check(g2): solve(g2)
      
      #           ABCDEFGHJKLMNPQ
      solve(list('5??????9???????'))
      

      If you relax the condition that all 11 primes are distinct there is a second solution.

    • Jim Randell 31 July 2013 at 9:59 pm

      Here’s a version written using the generic cross figure solver the code for which I put up in my solution for Enigma 1760. It runs in 70ms.

      # consider the grid:
      #
      #  A # # # B
      #  C D # E F
      #  # G H J #
      #  K L # M N
      #  P # # # Q
      
      from enigma import CrossFigure, irange, Primes, is_duplicate, printf
      
      # label the indices to make things easier
      (A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = irange(0, 14)
      
      # 2- and 3-digit primes without repeated digits
      primes = Primes(1000)
      p2s = list(p for p in primes.range(10, 99) if not is_duplicate(p))
      p3s = list(p for p in primes.range(100, 999) if not is_duplicate(p))
      
      #                ABCDEFGHJKLMNPQ
      p = CrossFigure('5??????9???????')
      # solutions that are 2-digit primes
      p.set_answer([(A, C), (K, P), (B, F), (N, Q), (C, D), (E, F), (K, L), (M, N)], p2s)
      # solutions that are 3-digit primes
      p.set_answer([(D, G, L), (G, H, J), (E, J, M)], p3s)
      # no digit is repeated in a row, column or diagonal
      p.set_distinct([
        (A, B), (C, D, E, F), (G, H, J), (K, L, M, N), (P, Q),
        (A, C, K, P), (D, G, L), (E, J, M), (B, F, N, Q),
        (A, D, H, M, Q), (B, E, H, L, P)
      ])
      
      # final check: all answers in the grid are distinct
      def check(p, grid):
        answers = list(p.get_answers(grid))
        return len(set(answers)) == len(answers)
      p.set_check(lambda grid: check(p, grid))
      
      # solve it
      for (A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) in p.solve():
        printf("[{A} # # # {B}]\n[{C} {D} # {E} {F}]\n[# {G} {H} {J} #]\n[{K} {L} # {M} {N}]\n[{P} # # # {Q}]")
        printf("{E}{J}{M} {K}{P}\n")
      
  2. Brian Gladman 13 March 2013 at 10:36 pm

    Mine is similar except that I did more work up front to save time later (hopefully!)

    # grid layout 
    # 5  X  X  X  a
    # b  c  X  d  e
    # X  f  9  g  X
    # h  i  X  j  k
    # l  X  X  X  m
    
    from collections import defaultdict as dfd
    from enigma import Primes
    
    p2_tens, p2_unit = dfd(list), dfd(list)
    p3_hnrd, p3_tens, p3_unit = dfd(list), dfd(list), dfd(list)
    
    for p in Primes(1000):
      if p < 10:
        continue
      elif p < 100:
        # compute two digit primes xy and store (xy, (x, y), set(x, y))
        # when x != y in dictionaries indexed on x and y
        digits = (p // 10, p % 10)
        t = (p, digits, frozenset(digits))
        if len(t[2]) == 2:
          p2_unit[p % 10] += [t]
          p2_tens[p // 10] += [t]
      else:
        # compute three digit primes xyz and store (xy, (x, y, z), set(x, y, z))
        # when x <> y <> z in dictionaries indexed on x, y and z
        digits = (p // 100, (p // 10) % 10, p % 10)
        t = (p, digits, frozenset(digits))
        if len(t[2]) == 3:
          p3_unit[p % 10] += [t]
          p3_tens[(p // 10) % 10] += [t]
          p3_hnrd[p // 100] += [t]
      
    # now set values progressively, checking for distinct primes
    # and for different digits in rows as they are completed
    for _5b, (_, b), dgt_5b in p2_tens[5]:
      # select bc from 2 digit primes with tens digit b
      for bc, (b, c), dgt_bc in p2_tens[b]:
        if bc == _5b:
          continue
        # select cfi from 3 digit primes with hundreds digit c
        for cfi, (_, f, i), dgt_cfi in p3_hnrd[c]:
          # select hi from 2 digit primes with units digit i
          for hi, (h, _), s_hi in p2_unit[i]:
            if hi in (_5b, bc):
              continue
            # select hl from 2 digit primes with tens digit h
            for hl, (_, l), dgt_hl in p2_tens[h]:
              if hl in (_5b, bc, hi) or dgt_5b & dgt_hl:
                continue
              # select f9g from 3 digit primes with hundreds digit f          
              for f9g, (f, _, g), dgt_f9g in p3_hnrd[f]:
                if f9g == cfi or _ != 9:
                  continue
                for dgj, (d, _, j), dgt_dgj in p3_tens[g]:
                  if dgj in (cfi, f9g):
                    continue
                  # select de from 2 digit primes with tens digit d              
                  for de, (_, e), dgt_de in p2_tens[d]:
                    if de in (_5b, bc, hi, hl) or dgt_bc & dgt_de:
                      continue
                    # select de from 2 digit primes with units digit e              
                    for ae, (a, _), dgt_ae in p2_unit[e]:
                      if ae in (_5b, bc, hi, hl, de) or a == 5:
                        continue
                      # select jk from 2 digit primes with tens digit j              
                      for jk, (_, k), dgt_jk in p2_tens[j]:
                        if jk in (_5b, bc, hi, hl, de, ae) or s_hi & dgt_jk:
                          continue
                        # select km from 2 digit primes with tens digit k                                  
                        for km, (_, m), dgt_km in p2_tens[k]:
                          if km in (_5b, bc, hi, hl, de, ae, jk) or dgt_ae & dgt_km:
                            continue
                          
                          # now check the last row and the two diagonals
                          if (l == m or len(set((5, c, 9, j, m))) != 5 or 
                                      len(set((a, d, 9, i, l))) != 5):
                            continue
                          # print the grid and the answer
                          print(' {:2d}  X  X  X {:2d}'.format(5, a))
                          print(' {:2d} {:2d}  X {:2d} {:2d}'.format(b, c, d, e))
                          print('  X {:2d} {:2d} {:2d}  X '.format(f, 9, g))
                          print(' {:2d} {:2d}  X {:2d} {:2d}'.format(h, i, j, k))
                          print(' {:2d}  X  X  X {:2d}'.format(l, m))
                          print('Answer: ', dgj, hl)
    
  3. ahmet çetinbudaklar 14 March 2013 at 6:03 am

    Starting from 5 and moving vertically then horizontally one gets 3 possibilities.
    Then taking care of the diagonal from bottom left to top right amd moving from 3-digit lowest primes one can reach the answer quite easily

  4. saracogluahmet 28 June 2013 at 12:49 pm
    
    #In Fact, I did code this for the second version of the puzzle... The same algorithm does work for twos.
    #My algorithm is based upon traversing the grid one cell by one, and the tour starts at (0,0) denoting the top left corner of the grid.
    #It moves (0,0), (1,0),(1,1),(2,1),(3,1),(3,0),(4,0),(0,4),(1,4)....................
    #The search is a depth-search and the algorithm is a recursive backtracking algorithm
    grid=[[-2]*5 for i in range(5)]#This is the grid
    grid[0][0],grid[2][2]=5,9#given the constraints in the puzzle
    
    #start= [0][0]
    path=[[0,0,1,0],[1,0,1,1],[1,1,2,1],[2,1,3,1],[3,1,3,0],[3,0,4,0],[4,0,0,4],
          [0,4,1,4],[1,4,1,3],[1,3,2,3],[1,3,3,3],[3,3,3,4],[3,4,4,4],[4,4,-1,-1]]
    
    primes=[-1]*14
    counter=0
    
    
    #if The number is prime
    def IsPrime(number):
        
        root=(int)(pow(number,0.5))+1
        for i in range(2,root):
            if number%i==0:
                return False
        return True
            
    
    #Convert digits to number at base 10
    def CalculateNumber(X,X1,Y,Y1,way):
        Sum,coeff=0,1
    
        
        for i in range(X,X1+way,way):
            for j in range(Y,Y1+way,way):
                Sum=Sum+(grid[i][j]*coeff)
                coeff*=10
        
        return Sum 
        
    def valid(X,Y,X1,Y1,Item,nxt):
        global counter
        Sum,count=0,0
    
        counter+=1
        
    
        #print(X,Y,X1,Y1,Item)
    
        #This is for checking the row, column and diagonals constraint given in the puzzle
        for i in range(5):
            if (Y1!=i):
                if grid[X1][i]==Item:
                    return False
    
            if (X1!=i):
                if grid[i][Y1]==Item:
                    return False
    
            if (X1!=i) and (Y1!=i)and (X1==Y1):
                if grid[i][i]==Item:
                    count+=1
                if count>0:
                    return False
            count=0
    
            if (X1+Y1)==4:
               if X1!=i and grid[i][4-i]==Item:
                   count+=1
                   if count>0:
                       return False
                
        if (X1==2 and Y1==1): #If the move is at the center of the grid, it certainly must have 9 at that cell, in order not to change that cell's value.
            return True
    
        if X1==3 and Y1==1:
            X=1
    
        if X1==1 and Y1==4:
            X,X1=0,1
    
        
        Xc=X1-X #How many digits have
        Yc=Y1-Y
    
        if Xc>0: 
            Sum=CalculateNumber(X1,X,Y1,Y,-1)
        elif Xc<0:
            Sum=CalculateNumber(X,X1,Y,Y1,1)
        elif Yc>0:
            Sum=CalculateNumber(X,X1,Y1,Y,-1)
        elif Yc<0:
            Sum=CalculateNumber(X,X1,Y,Y1,-1)
    
        if grid[0][4]==0 or grid[1][1]==0 or grid[1][3]==0 or grid[3][0]==0 or grid[3][3]==0 or grid[2][1]==0:
           return False #No leading ones int the grid
        
        
        if IsPrime(Sum): # The digits converted into base here for being checked if the converted number is  prime or not.
            primes[counter]=Sum
            
            return True
    
        return False
    
    
    def Distinct():
        count=[0]*1000
        for i in range(13):
            prime=primes[i]
            if prime>i:
                count[prime]+=1
            if count[prime]>1:
                return False
        return True
    
    def Solve(x,y,x1,y1,nxt):
        global counter    
    
        if x1==-1 and y1==-1:
            if Distinct():#Primes are distinct given in the puzzle.
                print(grid)
            return
        for i in range(10):
            grid[x1][y1]=i
            
            if valid(x,y,x1,y1,i,nxt):
                x,y,x1,y1=path[nxt][0],path[nxt][1],path[nxt][2],path[nxt][3]
                Solve(x,y,x1,y1,nxt+1)
                #Backtracking occurs in the following
                x,y,x1,y1=path[nxt-1][0],path[nxt-1][1],path[nxt-1][2],path[nxt-1][3]
            counter-=1
            grid[x1][y1]=-2 
            
    #Stars from the top corner of the grid.
    Solve(0,0,1,0,1)
      
  5. geoffrounce 20 July 2017 at 4:16 pm

    I got the published answer and another possible answer in MiniZinc.
    Answers were (41 and 617) and (47 and 617)

    % A Solution in MiniZinc
    
    % grid references used - shaded regions jn and eil
    % 5 X X X b
    % c d X e f
    % X g 9 i X
    % j k X l m
    % n X X X p
    
    include "globals.mzn";
    
    % parameter variables
    int: a = 5;
    int: h = 9;
    
    % decision variables   
    var 1..9:b;  var 1..9:c;   var 0..9:d;   var 1..9:e;  var 0..9:f;  
    var 1..9:g;  var 0..9:i;   var 1..9:j;   var 0..9:k;  var 1..9:l;  
    var 1..9:m;  var 0..9:n;   var 0..9:p;
    
    var 100..999 : dgk = 100*d + 10*g + k;
    var 100..999 : ghi = 100*g + 10*h + i;
    var 100..999 : eil = 100*e + 10*i + l;
    
    var 10..99 : ac = 10*a + c;
    var 10..99 : jn = 10*j + n;
    var 10..99 : bf = 10*b + f;
    var 10..99 : mp = 10*m + p;
    var 10..99 : jk = 10*j + k;
    var 10..99 : cd = 10*c + d;
    var 10..99 : ef = 10*e + f;
    var 10..99 : lm = 10*l + m;
    
    % predicate 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));
    
    % 2-digit Primes
    set of int: primes = {11, 13, 17, 19, 23, 29, 31,
    37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    
    constraint cd in primes /\ ef in primes /\ is_prime(ghi) /\ jk in primes
    /\ lm in primes /\ ac in primes /\ jn in primes 
    /\ is_prime(dgk) /\ is_prime(eil) /\ bf in primes /\ mp in primes;
    
    constraint alldifferent ([a,b]) /\ alldifferent([c,d,e,f]) 
    /\ alldifferent ([g,h,i]) /\ alldifferent([j,k,l,m]) 
    /\ alldifferent([n,p]) /\ alldifferent([a,c,j,n])
    /\ alldifferent ([d,g,k]) /\ alldifferent([e,i,l]) 
    /\ alldifferent([b,f,m,p]) /\ alldifferent([a,d,h,l,p]) 
    /\ alldifferent([b,e,h,k,n]);
    
    solve satisfy;
    
    output[ "Shaded area values: " ++ show(jn) ++ " and " ++ show(eil) ++ "\n" 
         ++ show(a) ++ "XXX" ++ show(b) ++ "\n"
         ++ show(cd) ++ "X" ++ show(ef) ++ "\n"
         ++ "X" ++ show(ghi) ++ "X" ++ "\n" 
         ++ show(jk) ++ "X" ++ show(lm) ++ "\n"
         ++ show(n) ++ "XXX" ++ show(p)] ;   
         
    % 1st answer
    % Shaded area values: 41 and 617
    % 5XXX4
    % 31X67
    % X691X
    % 43X71
    % 1XXX3
    
    % 2nd answer                                        
    % Shaded area values: 47 and 617
    % 5XXX4
    % 31X67
    % X691X
    % 43X71
    % 7XXX3
    % Finished in 57msec
    
    
    • Jim Randell 20 July 2017 at 4:24 pm

      @geoff: Your second solution has 47 in it twice, so is disallowed as all 11 answers have to be different primes. (I think this check is missing from your MiniZinc model).

      Here’s a run-file that solves the problem using the SubstitutedExpression() solver from the enigma.py library. The conditions that the primes are all different are checked in line 27 and line 31.

      #!/usr/bin/env python -m enigma -r
      
      #
      #  A # # # B
      #  C D # E F
      #  # G H J #
      #  K L # M N
      #  P # # # Q
      #
      
      SubstitutedExpression
      
      --distinct=""
      --assign="A,5"
      --assign="H,9"
      --answer="(EJM, KP)"
      
      # the 11 answers are distinct primes
      "is_prime(AC)"
      "is_prime(BF)"
      "is_prime(CD)"
      "is_prime(EF)"
      "is_prime(KL)"
      "is_prime(MN)"
      "is_prime(KP)"
      "is_prime(NQ)"
      "all_different(AC, BF, CD, EF, KL, MN, KP, NQ)"
      "is_prime(DGL)"
      "is_prime(EJM)"
      "is_prime(GHJ)"
      "all_different(DGL, EJM, GHJ)"
      
      # no digit appears more than once in any row column or diagonal
      "all_different(A, B)"
      "all_different(C, D, E, F)"
      "all_different(G, H, J)"
      "all_different(K, L, M, N)"
      "all_different(P, Q)"
      "all_different(A, C, K, P)"
      "all_different(D, G, L)"
      "all_different(E, J, M)"
      "all_different(B, F, N, Q)"
      "all_different(A, D, H, M, Q)"
      "all_different(B, E, H, L, P)"
      
  6. saracogluahmet 20 July 2017 at 4:36 pm

    Oh it was 2013, how are you all? I hope you all great, best wishes

    • Jim Randell 20 July 2017 at 10:36 pm

      @ahmet: Enigmatic Code is still here. Although New Scientist stopped publishing new Enigma puzzles at the end of 2013, I am putting up two puzzles a week (sometimes three) from New Scientist back issues, and there are now over 1000 puzzles on the site. There are about 700 Enigma puzzles left for me to post, so it’ll keep me busy for a while longer.

  7. saracogluahmet 21 July 2017 at 11:51 am

    @Jim You are doing good job, as soon as I find an occasion, I will be here, I have been following you, have a nice day

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: