Enigmatic Code

Programming Enigma Puzzles

Enigma 1730: Prime position

From New Scientist #2898, 5th January 2013 [link]

Enigma 1730The grid shown above is a cross-figure puzzle with one digit given as a starting point. All 11 answers are prime numbers, none of them starts with a zero, and adding the individual figures in each column gives the same sum.

What are the two numbers in the shaded regions of the grid?

[enigma1730]

Advertisements

6 responses to “Enigma 1730: Prime position

  1. Jim Randell 2 January 2013 at 6:21 pm

    This Python program is a direct implementation of the problem statement, and finds the solution in 41ms. I’m sure I can make a prettier version though.

    # 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, printf
    
    # record 1, 2, 3 digit primes
    ps = [ None, [], [], [] ]
    for n in Primes(999):
      p = str(n)
      ps[len(p)].append(p)
    
    # p1 is a 2-digit prime beginning with 2
    for p1 in ps[2]:
      if p1[0] != '2': continue
      # p3 is a 2-digit prime beginning with p1[1]
      for p3 in ps[2]:
        if p3[0] != p1[1]: continue
        # p4 is a 3 digit prime beginning with p3[1]
        for p4 in ps[3]:
          if p4[0] != p3[1]: continue
          # and its digits must sum to single digit number
          s = sum(int(x) for x in p4)
          if s > 9: continue
          # p8 is a 2-digit prime ending in p4[2]
          for p8 in ps[2]:
            if p8[1] != p4[2]: continue
            # p9 is a 2-digit prime beginning with p8[0]
            for p9 in ps[2]:
              if p9[0] != p8[0]: continue
              # and the sum of the digits in p1 and p9 should be s
              if sum(int(x) for x in p1 + p9) != s: continue
              # p7 is a 3-digit prime that starts with p4[1]
              # and has s as its second digit
              for p7 in ps[3]:
                if p7[0] != p4[1] or p7[1] != str(s): continue
                # p6 is a 3-digit prime with p7[2] in the middle
                for p6 in ps[3]:
                  if p6[1] != p7[2]: continue
                  # and its digits should sum s
                  if sum(int(x) for x in p6) != s: continue
                  # p5 is a 2-digit prime starting with p6[0]
                  for p5 in ps[2]:
                    if p5[0] != p6[0]: continue
                    # p2 is a 2-digit prime ending with p5[1]
                    for p2 in ps[2]:
                      if p2[1] != p5[1]: continue
                      # p10 is a 2-digit prime starting with p6[2]
                      for p10 in ps[2]:
                        if p10[0] != p6[2]: continue
                        # p11 is a 2-digit prime starting with p10[1]
                        for p11 in ps[2]:
                          if p11[0] != p10[1]: continue
                          # and the digits of p2 and p11 should sum to s
                          if sum(int(x) for x in p2 + p11) != s: continue
        
                          printf("p2={p2} p7={p7} [s={s} p1={p1} p3={p3} p4={p4} p5={p5} p6={p6} p8={p8} p9={p9} p10={p10} p11={p11}]")
    

    Solution: The two shaded numbers are 41 and 571.

    Here is the completed grid.

    Enigma 1730 - Solution

    • Jim Randell 2 January 2013 at 7:47 pm

      Here’s a slightly cleverer (and also slightly slower) Python program that gets the same solution. It runs in 69ms.

      from collections import defaultdict
      from itertools import product
      from enigma import Primes, printf
      
      # find 2, 3 digit primes
      ps2 = set(str(p) for p in Primes(99) if p > 9)
      ps3 = set(str(p) for p in Primes(999) if p > 99)
      
      # digit sum of a number (passed as a string)
      def dsum(s):
        return sum(int(x) for x in s)
      
      # find 3-digit primes where the digits sum to a 1-digit number
      p3s = defaultdict(list)
      for p in ps3:
        s = dsum(p)
        if s > 9: continue
        p3s[s].append(p)
      
      # now find pairs of these
      for (s, v) in p3s.items():
        for p4, p6 in product(v, repeat=2):
          # check p7
          p7 = p4[1] + str(s) + p6[1]
          if p7 not in ps3: continue
          # find pairs of 2-digit primes where the digits sum to s
          p2s = set((p, q) for p, q in product(ps2, repeat=2) if dsum(p + q) == s)
          # p1 and p9 are one of these pairs
          for (p1, p9) in p2s:
            # but we're given the first digit of p1
            if p1[0] != '2': continue
            # check p3 and p8
            (p3, p8) = (p1[1] + p4[0], p9[0] + p4[2])
            if p3 not in ps2 or p8 not in ps2: continue
            # similarly p2 and p11 are also one of these pairs
            for (p2, p11) in p2s:
              # check p5 and p10
              (p5, p10) = (p6[0] + p2[1], p6[2] + p11[0])
              if p5 not in ps2 or p10 not in ps2: continue
              
              printf("p2={p2} p7={p7} [s={s} p1={p1} p3={p3} p4={p4} p5={p5} p6={p6} p8={p8} p9={p9} p10={p10} p11={p11}]")
      
    • Jim Randell 31 July 2013 at 10:23 pm

      You can also use the generic cross figure solver given in my solution for Enigma 1760 to solve this problem. But it isn’t quick – it takes 3m26s under PyPy – because the condition that the columns sum to the same value is not checked until the the grid is filled out. But here’s the code if you want to see it.

      # consider the grid:
      #
      #  A # # # B
      #  C D # E F
      #  # G H J #
      #  K L # M N
      #  P # # # Q
      
      from enigma import CrossFigure, irange, Primes, 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 prime
      primes = Primes(1000)
      p2s = list(primes.range(10, 99))
      p3s = list(primes.range(100, 999))
      
      # final check - all columns have the same sum
      def check(grid):
        (A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = (int(x) for x in grid)
        return A + C + K + P == D + G + L == H == E + J + M == B + F + N + Q
      
      #                ABCDEFGHJKLMNPQ
      p = CrossFigure('2??????????????')
      # 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)
      # final check: all columns have the same sum
      p.set_check(check)
      
      # 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("{B}{F} {G}{H}{J}\n")
      
  2. arthurvause 3 January 2013 at 10:22 am

    Numbering the grid as for a crossword, as shown in this diagram.

    The digits of all columns add to the same sum, which must be less than 10 due to the middle digit of 6 across.

    So 1 down must be 23 (29 would make the common sum more than 1 digit).

    7 down must be 11, (if it were 13 or 31, the common digit sum would be 9, so the 3 digit numbers would not be prime)

    So the common column digit sum is 7, which is the middle digit of 6 across.

    3 across must be 31 (37 would be too large for 4 down)

    Some code for the rest:

    import primes
    primelist = primes.primeList(1000)
    twoDigitPrimes = [p for p in primelist if 9<p<100]
    
    def digitsum(n):
        return sum(map(int,str(n)))
    
    for D4 in [str(x) for x in primelist if 99<x<200 and digitsum(x)==7
               and x%10+10 in primelist]:
      for A6 in [x for x in primelist if x//10 == 10*int(D4[1])+7]:
        for D5 in [x for x in primelist if 99<x<1000
                   and digitsum(x)==7
                   and (x//10)%10==A6%10]:
          for (D2,D9) in [(x,y) for x in twoDigitPrimes for y in twoDigitPrimes
                          if 10*(D5//100)+x%10 in primelist
                          and 10*(D5%10)+y//10 in primelist
                          and digitsum(x+100*y)==7]:
            print "6-across =",A6, ", 2-down =",D2, "(others:", D4,D5,D9,")"
      
    
  3. Jim Randell 25 April 2017 at 3:55 pm

    Each square contains a single digit, so we can use the alphametic solver (SubstitutedExpression()) from the enigma.py library to solve this puzzle, by expressing the constraints as Python expressions.

    Here is a run-file that executes in 120ms.

    #!/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,2"
    --answer="(BF, GHJ)"
    
    # 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)"
    "is_prime(DGL)"
    "is_prime(EJM)"
    "is_prime(GHJ)"
    
    # column sums are the same (so they must sum to H)
    "A + C + K + P = H"
    "D + G + L = H"
    "E + J + M = H"
    "B + F + N + Q = H"
    

    With analysis we can provide additional constraints. For example: no prime can start or end with a zero, so none of the letters (except H) can be zero, but all the columns must sum to H, so it can’t be zero either, hence we could add the parameter --digits="1-9". Also none of the digits that end a prime (with more than 1 digit) can be 2, 4, 5, 6, 8, so we could also add the parameter --invalid="24568,CDFJLMNPQ", although these provide only a modest reduction in overall execution time.

  4. geoffrounce 20 July 2017 at 3:48 pm
    % A Solution in MiniZinc - Grid is shown below - shaded numbers are BF and GHJ
    %   A # # # B   -    
    %   C D # E F
    %   # G H J #
    %   K L # M N
    %   P # # # Q
    
    include "globals.mzn";
    
    var 1..9:A;   var 1..9:B;  var 1..9:C;  var 1..9:D;  var 1..9:E;  
    var 1..9:F;   var 1..9:G;  var 1..9:H;  var 1..9:J;  var 1..9:K;  
    var 1..9:L;   var 1..9:M;  var 1..9:N;  var 1..9:P;  var 1..9:Q;
    
    var 11..97 : AC = 10*A + C;
    var 11..97 : BF = 10*B + F;
    var 11..97 : CD = 10*C + D;
    var 11..97 : EF = 10*E + F;
    var 11..97 : KL = 10*K + L;
    var 11..97 : MN = 10*M + N;
    var 11..97 : KP = 10*K + P;
    var 11..97 : NQ = 10*N + Q;
    
    var 101..997 : DGL = 100*D + 10*G + L;
    var 101..997 : EJM = 100*E + 10*J + M;
    var 101..997 : GHJ = 100*G + 10*H + J;
    
    predicate is_prime(var int: x) = 
    x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
    ((i < x) -> (x mod i > 0));
    
    constraint A == 2;
    
    constraint sum ( [is_prime(AC), is_prime(BF), is_prime(CD), is_prime(EF),
       is_prime(KL), is_prime(MN), is_prime(KP), is_prime(NQ), is_prime(DGL), 
       is_prime(EJM), is_prime(GHJ) ] ) == 11;
     
    % adding the individual figures in each column gives the same sum ie H
    constraint sum ( [A + C + K + P == H, D + G + L == H, 
                      E + J + M == H, B + F + N + Q == H] ) == 4;
    solve satisfy;
    
    output [ "The two shaded numbers are "++ show(BF) ++ " and " ++ show(GHJ) ];
    
    % The two shaded numbers are 41 and 571
    % Finished in 55msec
    

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: