Enigmatic Code

Programming Enigma Puzzles

Enigma 1755: Sudoprime II

From New Scientist #2923, 29th June 2013 [link]

Enigma 1755

The grid shows a cross-figure with two digits given as a start. All 11 two- and three-digit answers are prime and none has a leading zero; no digit appears more than once in any row, column or either of the two long diagonals; no even digit appears more than once anywhere.

What are the numbers in the shaded regions?

This puzzle is similar to Enigma 1740 and Enigma 1730 (both also set by Peter Chamberlain).

[enigma1755]

Advertisements

28 responses to “Enigma 1755: Sudoprime II

  1. Jim Randell 26 June 2013 at 7:23 pm

    A slightly modified version of my recursive solver for Enigma 1750 solves this in 84ms.

    # 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("{G}{H}{J} {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 no even digit appears more than once
        if not any(g.count(d) > 1 for d in '02468'):
          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('7?????3????????'))
    

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

    Enigma 1755 - Solution

    • Des 26 July 2013 at 7:59 am

      Isn’t zero an even digit?

      • Jim Randell 26 July 2013 at 9:03 am

        Yes, zero is an even digit. But it only appears once in the solution grid, so that’s OK.

        I took the phrase “no even digit appears more than once anywhere” to mean “there cannot be more than one occurrence of any particular even digit in the solution grid; there may multiple even digits in the solution grid (but each of them will have to be a different digit)”, rather than “there cannot be more than one even digit in the solution grid”.

        There are no solutions if the latter interpretation is used.

    • Jim Randell 31 July 2013 at 9:46 pm

      I wrote a generic cross-figure solver (the code for which is given in my solution for Enigma 1760). Here’s a solution to this problem using that code. 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('7?????3????????')
      # 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: no even digit is repeated
      p.set_check(lambda grid: not any(grid.count(d) > 1 for d in '02468'))
      
      # 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("{G}{H}{J} {K}{P}\n")
      
  2. saracogluahmet 28 June 2013 at 1:19 pm
    #This is the same algorithm for the first version of this enigma
    
    grid=[[-2]*5 for i in range(5)]#This is the grid
    grid[0][0],grid[2][1]=7,3#given the constraints in the puzzle
    
    #start= [0][0]
    
    # I move along this path, this means, 0,0 to 1,0 and 1,0 to 1,1
    path=[[0,0,1,0],[1,0,1,1],[1,1,3,1],[3,1,3,0],[3,0,4,0],[4,0,2,2],[2,1,2,3],[2,3,0,4],
          [0,4,1,4],[1,4,1,3],[1,3,3,3],[3,3,3,4],[3,4,4,4],[4,4,-1,-1]]
    
    primes=[-1]*14
    counter=0
    
    def IsPrime(number):
        
        root=(int)(pow(number,0.5))+1
        for i in range(2,root):
            if number%i==0:
                return False
        return True
            
    #Digits are converted to a number in the corresponding cells
    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
    
        #This one is to be able to check the constaints saying that there must not be double of an item in the same row, and....
        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:
                    return False
            
    
            if (X1+Y1)==4:
               if X1!=i and grid[i][4-i]==Item:
                   return False
                
        if (X1==2 and Y1==2):
            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
    
    
        #The numbers must not start with "0"
        if grid[0][4]==0 or grid[1][3]==0 or grid[3][0]==0 or grid[3][3]==0:
            return False
    
        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)
    
        # whether the number being got is prime or not
        if IsPrime(Sum):
            #print("prime",Sum,"X=",X,"X1=",X1,"Y=",Y,"Y1=",Y1)
            primes[counter]=Sum
            return True
    
        return False
    
    
    #Only a certain digit may be used once given in the puzzle, it is a controversial point I guess
    def Distinct():
        count=[0]*10
        for i in range(5):
            for j in range(5):
                item=grid[i][j]
                if item>0:
                    if item%2==0:
                        count[item]+=1
                        if count[item]>1:
                            return False
        return True
    
    def Solve(x,y,x1,y1,nxt):
        global counter    
    
        if x1==-1 and y1==-1:
            if Distinct():
                print(grid)
                return
        for i in range(10):
            grid[x1][y1]=i
            #print(nxt)
            if valid(x,y,x1,y1,i,nxt):
                x,y,x1,y1=path[nxt][0],path[nxt][1],path[nxt][2],path[nxt][3]
                #print("next",nxt,i)
                Solve(x,y,x1,y1,nxt+1)
                #Backtracking occurs below...
                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
    Solve(0,0,1,0,1)
    
    • saracogluahmet 28 June 2013 at 1:26 pm

      The execution time of the algorithm above on my machine is about 15 miliseconds, I guess that is really fast..

      • Brian Gladman 29 June 2013 at 1:04 pm

        This one is rather long but it is quite fast:

        # digit positions are numbered 0 .. 14 from top left to bottom right
        
        from primes import Primes
        
        # two and three digit primes with no repeated digits
        prms = Primes().list(10, 1000)
        prms = [x for x in prms if len(str(x)) == len(set(str(x)))]
        
        # the digit positions for the eleven primes
        pr_ix = ((0, 2), (1, 5), (2, 3), (4, 5), (9, 10), (11, 12), (9, 13),
                 (12, 14), (6, 7, 8), (3, 6, 10), (4, 8, 11))
        
        # the positions in the same rows, columns and diagonals
        rows = ((0, 1), (2, 3, 4, 5), (6, 7, 8), (9, 10, 11, 12), (13, 14))
        cols = ((0, 2, 9, 13), (3, 6, 10), (4, 8, 11), (1, 5, 12, 14))
        diag = ((0, 3, 7, 11, 14), (1, 4, 7, 10, 13))
        
        # remove 'digit' from allowed values in a row, column or diagonal
        def rem(digit, position, friends_list, d):
          for friends in friends_list:
            if position in friends:
              for friend in friends:
                if friend != position:
                  d[friend] -= set((digit,))
        
        # remove 'digit' from the possible values for other positions
        # in rows, columns and diagonals that include it
        def remove(digit, position, d):
          e = d.copy()
          rem(digit, position, rows, e)
          rem(digit, position, cols, e)
          rem(digit, position, diag, e)
          return e
        
        # check if all completed numbers in the grid are prime
        def test_primes(g, p_ix):
          for t in p_ix:
            # compile digits for this prime
            ps = ''.join(str(g[i]) for i in t)
            # if it is complete but it is not prime
            if not ('None' in ps or int(ps) in prms):
              return False
          # all completed numbers are prime
          return True
        
        # compile a dictionary of the possible digit values for
        # each grid position
        dmap = dict()
        for position in range(15):
          # for each prime in the grid
          for digit_indexes in pr_ix:
            # if this position is the last digit of a prime, it
            # can only be 1, 3, 7 or 9
            if position == digit_indexes[-1]:
              dmap[position] = set((1, 3, 7, 9))
              break
          else:
            # otherwise allow any digit
            dmap[position] = set(range(10))
        
        # remove 7 and 3 from as possible values for positions
        # in the same rows, columns and diagonals
        dmap = remove(3, 6, remove(7, 0, dmap))
        
        # place a digit in grid 'g' with a map in 'dmap' giving
        # the possible values for each position
        def solve(g, dmap):
          # we have more values to set
          if None in g:
            # find a position with the fewest possible values
            min_len, min_pos = 1000, -1
            for position, val in enumerate(g):
              if val == None and len(dmap[position]) < min_len:
                min_len, min_pos = len(dmap[position]), position
            # try these values in this position
            for v in tuple(dmap[min_pos]):
              # add this value to a new copy of the grid
              new_g = g[:]
              new_g[min_pos] = v
              # and test if all the complted numbers are prime
              if test_primes(new_g, pr_ix):
                # continue to place digits with an updated map
                solve(new_g, remove(v, min_pos, dmap))
          else:
            # check that any even digits are not used more than once
            if all(g.count(x) < 2 for x in range(0,10, 2)):
              # output the answer and the corresponding grid
              print('{:d}{:d}{:d} and {:d}{:d}'.format(g[6], g[7], g[8], g[9], g[13]))
              print('{:2d} # # #{:2d}'.format(g[0], g[1]))
              print('{:2d}{:2d} #{:2d}{:2d}'.format(g[2], g[3], g[4], g[5]))
              print(' #{:2d}{:2d}{:2d} #'.format(g[6], g[7], g[8]))
              print('{:2d}{:2d} #{:2d}{:2d}'.format(g[9], g[10], g[11], g[12]))
              print('{:2d} # # #{:2d}'.format(g[13], g[14]))
        
        # set an empty grid
        g = [None] * 15
        # and add 7 and 3 to it
        g[0], g[6] = 7, 3
        # now solve for other digit positions
        solve(g, dmap)
        
        • Ahmet Saracoğlu 29 June 2013 at 6:02 pm

          Hi Brian, what is the execution time of it?

          • Brian Gladman 29 June 2013 at 7:07 pm

            If I replace lines 1 to 7 with

            # digit positions are numbered 0 .. 14 from top left to bottom right
            
            from enigma import Primes
            
            # two and three digit primes with no repeated digits
            prms = [x for x in Primes(1000) if len(str(x)) == len(set(str(x))) > 1]
            

            so that Jim’s enigma can be used, I then get PyPy 2.0.2 timings for Jim’s, your’s and mine of 1040, 980 and 30 milliseconds respectively (this is on a 1.8GHz i7 laptop). On CPython 3.3 I get 250, 240 and 31 milliseconds respectively.

            These are timings using Python’s CProfile module. My experience is that timings vary wildly between machines and Python versions so the different versions have to be run on the same machine using the saame timing approach to be meaningful. Even then I am not very convinced about the results.

            • Ahmet Saracoğlu 29 June 2013 at 7:13 pm

              I see, frankly when ı get the 15 ms on my machine which is 2.6 ghz laptop, I dont need to optimize more, however your codes execution time on my machine is 45 ms

              • Brian Gladman 29 June 2013 at 10:01 pm

                Hi Ahmet,

                Jim timed his own version, your version and mine and got yours and his similar and mine aboutr twice the speed. I have timed them and I have also asked two colleagues to do so and all the results are reasonably close to those that Jim has reported.

                But you are suggesting that my version takes three times as long on your machine as your version – 45 ms compared with 15 ms. So something that others find to be about twice as fast, you are measuring as three times slower – a factor of six different!

                Since this seems very unlikely, it suggests that there may be something wrong with the way you are measuring running times.

                • Ahmet Saracoğlu 29 June 2013 at 10:12 pm

                  Ok, then I am going to post the output, that is impossible that my code’s execution time is 90ms, it is working just 15 ms on my machine, and yours is about 45 ms, and one thing, if the execution time is not so important, then no need to talk about it, this is just python, and a child play for me, the point is to construct a good algortihm, and I believe that I am succesfull at construcing good one, in my opinion, then no need to talk about the execution times, because nobody can prove their execution time, and it is really dependent on the processors speed, I know that mine is working on my machine in 15 ms, I dont know and can not know the rest 🙂

                  • Brian Gladman 29 June 2013 at 10:49 pm

                    It is not the algorithm that I am seeking to explain. I am seeking to understand how a program that seems to be about twice as fast for a number of people is three times slower for you! I suspect that this is a problem with timing but it could be something else. Either way it would be useful to know why this is as it may tell us something.

                    I am timing in the following way. I have a batch file called ‘profile.bat’ in the same directory as my Python files. It contains the two lines:

                    @echo off
                    “c:\program files\python33\python” -mcProfile -scumulative %1

                    I then run a command prompt (a DOS window) in this directory and enter the command:

                    profile ns1755.py

                    where ns1755.py is the name of the program being timed.

                    How are you producing your timing results?

                    • Ahmet Saracoğlu 30 June 2013 at 7:53 am

                      What I am trying to understand is the same as you did tell me the differences of the execution times between two different machines, on my machine my code’s execution time is about 15 ms, how is it possible to be 90 ms on other machine, this is 6 times slower, that is unbelievable. I guess if I do not misunderstand that your code, you have a prime a list given on the top of the code, you have not coded a function of primarility test,

                      As to my timing issue, I run the code on the Python editor, as I showed you before, and although there is overhead because of the editor itself, when I use the time function on my code, it gives me a 15ms on my machine,now the point is this, how is it possible for it to be working on a diiferent machine with the 6 times slower execution time than mine

      • Jim Randell 29 June 2013 at 6:19 pm

        For comparison I ran the same timing tests that I run for my own code on this one and it comes out at 92ms. So the running times are very similar.

        As I noted in my solution for Enigma 1740 you can write a faster program for solving this kind of problem, but I find the more general algorithm to be more interesting to program.

        Personally I’m happy with any code that runs in under 100ms, as that’s pretty much instantaneous.

        • Ahmet Saracoğlu 29 June 2013 at 6:33 pm

          Hi Jim, which one do you mean, mine or Brian s?

          • Jim Randell 29 June 2013 at 6:37 pm

            @Ahmet: I’m referring to the code you posted above (28 June 2013 at 1:19 pm).

            • Ahmet Saracoğlu 29 June 2013 at 6:51 pm

              I do not know, my execution time is 15 ms on my machine, I can post the image of the output if you wish, and also I can speed up mine, if you have noted that, I did not use some constraints like the prime numbers end wirh the 1 3 7 9 and some other stuff, anyway, i dont know how yo do test the codes

              • Jim Randell 29 June 2013 at 7:15 pm

                I don’t doubt the times you report. I was just running your code under the same environment to give a comparable figure. The code Brian published (with a little tweak to use the Primes class from enigma.py) came in at 44ms.

                As noted on the Notes page I time all phases of the command execution, so it’s quite hard to get a runtime reported of less than around 30ms.

                But for me the challenge is not about coming up with the fastest executing program, or the shortest program, but a program that is easy to understand and that runs fast enough and doesn’t take too long to write. For this puzzle I just adapted a program I’d written for a previous puzzle, so it only took me a few minutes to come up with a viable program, and it ran in less than 100ms, so I was happy with it.

                • Ahmet Saracoğlu 29 June 2013 at 7:32 pm

                  I agree with you, the previous puzzle is so similar to this, I did code this first, after, İ did code the previous one in a few minutes, and I agree with you about the point is algorithm, and sure execution time, the code might be longer but the execution time does matter

  3. saracogluahmet 1 July 2013 at 10:02 am
    def Run():
        for i in range(100000):
            mul=i+10
            
    
    for j in range(10):
        Run()
    
    

    This one’s execution time on my machine is about 260ms,what about on yours?

    • Jim Randell 2 July 2013 at 1:23 pm

      That would come out as 97ms on my machine.

      % mtime python test.py                        
      python test.py  0.11s user 0.01s system 96% cpu 0.123 total
      python test.py  0.10s user 0.01s system 96% cpu 0.121 total
      python test.py  0.11s user 0.01s system 96% cpu 0.123 total
      python test.py  0.11s user 0.01s system 96% cpu 0.126 total
      python test.py  0.11s user 0.01s system 96% cpu 0.123 total
      python test.py  0.11s user 0.01s system 97% cpu 0.131 total
      python test.py  0.10s user 0.01s system 96% cpu 0.118 total
      python test.py  0.09s user 0.01s system 96% cpu 0.099 total
      python test.py  0.09s user 0.01s system 96% cpu 0.101 total
      python test.py  0.09s user 0.01s system 96% cpu 0.103 total
      python test.py  0.08s user 0.01s system 96% cpu 0.097 total
      python test.py  0.10s user 0.01s system 96% cpu 0.116 total
      python test.py  0.11s user 0.01s system 96% cpu 0.124 total
      python test.py  0.10s user 0.01s system 96% cpu 0.117 total
      python test.py  0.08s user 0.01s system 95% cpu 0.098 total
      python test.py  0.09s user 0.01s system 95% cpu 0.108 total
      16 runs: best 97.0ms, worst 131.0ms, avg=114.2ms
      

      I wouldn’t get too hung up on comparing runtimes though, as they will vary depending on the hardware, operating system, Python version and what else is running on the machine at the time. I only report them as a rough guide to the amount of computation involved in determining the solution.

      Python has its own timeit module for doing more detailed calculation of the runtimes of code fragments, but I like using the shell’s time command as it gives me a reasonable basis for comparison between programs written in different languages. (I used to do Enigma problems in Perl).

  4. Ahmet Saracoğlu 3 July 2013 at 6:35 pm
    #This is the second version of the same algorihm, just changed the path....
    import time
    print(time.time())
    grid=[[-2]*5 for i in range(5)]#This is the grid
    grid[0][0],grid[2][1]=7,3#given the constraints in the puzzle
    
    #start= [0][0]
    
    # I move along this path, this means, 0,0 to 1,0 and 1,0 to 1,1
    path=[[0,0,1,1],[1,1,3,3],[3,3,4,4],[4,4,4,0],[4,0,3,1],[3,1,2,3],[2,3,1,3],[1,3,1,0],
          [1,0,1,4],[1,4,0,4],[0,4,2,2],[2,2,3,0],[3,0,3,4],[3,4,-1,-1]]
    
    
    flag=False
    
    def IsPrime(number):
        
        root=(int)(pow(number,0.5))+1
        for i in range(2,root):
            if number%i==0:
                return False
        return True
            
    #Digits are converted to a number in the corresponding cells
    def CalculateNumber(X,X1,Y,Y1,coeff):
        Sum=0
        for i in range(X,X1):
            for j in range(Y,Y1):
                Sum=Sum+(grid[i][j]*coeff)
                coeff//=10
        return Sum
    
    
    def valid(X,Y,X1,Y1,Item,nxt):
        
        Sum=0
        
    
        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:
                    return False
            
    
            if (X1+Y1)==4:
               if X1!=i and grid[i][4-i]==Item:
                   return False
    
    
    
        if X1==2 and Y1==2:
            return (IsPrime(CalculateNumber(2,3,1,4,100)))
            
    
        if X1==1 and Y1==3 and Item!=0:
            return (IsPrime(CalculateNumber(1,4,3,4,100)))
            
        if X1==3 and Y1==0 and Item!=0:
            return(IsPrime(CalculateNumber(3,5,0,1,10)))
           
    
            
    
        if X1==0 and Y1==4 and Item!=0:
            return(IsPrime(CalculateNumber(0,2,4,5,10)))
           
    
        if Item not in [1,3,7,9]:
            return False
    
        #This one is to be able to check the constaints saying that there must not be double of an item in the same row, and....
        
        if X1==1 and Y1==0:
            return(IsPrime(CalculateNumber(0,2,0,1,10)))
            
        if X1==3 and Y1==1:
            return(IsPrime(CalculateNumber(1,4,1,2,100)))
            
        if X1==1 and Y1==4:
            return(IsPrime(CalculateNumber(1,2,3,5,10)))
            
        if X1==3 and Y1==4:
            return(IsPrime(CalculateNumber(3,5,4,5,10)))
        return True
    
    
    def Solve(x,y,x1,y1,nxt):
          
        global flag
    
        if x1==-1 and y1==-1:
            print(grid)
            return
            
        if flag==False:
            for i in range(10):
                grid[x1][y1]=i
            #print(nxt)
                if valid(x,y,x1,y1,i,nxt):
                    x,y,x1,y1=path[nxt][0],path[nxt][1],path[nxt][2],path[nxt][3]
                #print("next",nxt,i)
                    if nxt==13:
                        flag=True
                    Solve(x,y,x1,y1,nxt+1)
                #Backtracking occurs below...
                    x,y,x1,y1=path[nxt-1][0],path[nxt-1][1],path[nxt-1][2],path[nxt-1][3]
                
                grid[x1][y1]=-2
            
            
    Solve(0,0,1,1,1)
    print(time.time())
     

    I changed the path array, I have been moving on the diagonals first, and this one’s execution time on my machine is about 15ms…

  5. saracogluahmet 8 July 2013 at 2:00 pm

    This one is java version with the same algorithm and it is a simulation of the depth first search,

    import java.awt.*;
    import java.applet.Applet;
     
     /*
      @author asks
     */
    
    public class LineApplet extends Applet implements Runnable {
        Thread t=new Thread(this);  // This is the thread! 
        public TextField [] f=new TextField[25];
        
        int K=-1;
        int [][] grid=new int[5][];
        int cellnumber=0,value=7;
        
        int [][] path={{0,0,1,0},{1,0,1,1},{1,1,3,1},{3,1,3,0},{3,0,4,0},{4,0,2,2},{2,1,2,3},{2,3,0,4},
        {0,4,1,4},{1,4,1,3},{1,3,3,3},{3,3,3,4},{3,4,4,4},{4,4,-1,-1}};
        
        // Set the size of the applet...
        public void init() {
           int i,j;
              resize(300,300); 
              for (i=0;i<25;i++){
                  f[i]=new TextField();
                  add(f[i]);
              }
             for (i=0;i<5;i++){
                grid[i]=new int[5];
                for (j=0;j<5;j++){
                    grid[i][j]=-2;
                }
            }
                grid[0][0]=7;
                grid[2][1]=3;
                t.start();
                
             
                
        }
        
       public void run() {
             if (K==-1){
                 K=-2;
                 Solve(0,0,1,0,1);
                }
             }
       
       public void stop(){
           t=null;
       }
        
       public void paint(Graphics g){
             int X=40,Y=40,count=0;
             f[0].setText(Integer.toString(7));
             f[11].setText(Integer.toString(3));
             
             for (int i=0;i<5;i++){
                 for(int j=0;j<5;j++){
                    f[count].setSize(40, 40);
                    f[count].setBackground(Color.white);
                    f[count].setEditable(false);
                    /*f[count].setBackground(Color.red);*/
                    
                    f[count++].setLocation(X,Y);
                    X+=40;
                 }
                 Y+=40;
                 X=40;
             }
             
            f[1].setBackground(Color.black);
            f[2].setBackground(Color.black);
            f[3].setBackground(Color.black);
            f[7].setBackground(Color.black);
            f[10].setBackground(Color.black);
            f[14].setBackground(Color.black);
            f[17].setBackground(Color.black);
            f[21].setBackground(Color.black);
            f[22].setBackground(Color.black);
            f[23].setBackground(Color.black);
            
            if (K==-2){
                f[cellnumber].setText(Integer.toString(value));
                f[cellnumber].setBackground(Color.yellow);
            }
             
            
        }
        // Run the thread. Lines everywhere!
    
         
        public boolean IsPrime(double number){
        int root=(int)(Math.pow(number, 0.5)+1);
        
        if (number==0)
            return false;
        
        int i;
        for (i=2;i<=root;i++){
           if (number%i==0)
                   return false;
        }
       return true;
        }
        
        public int CalculateNumber(int X,int X1,int Y,int Y1,int way){
        int Sum=0,coeff=1,i,j;
        
        if (way>0)
        {
        for (i=X;i<X1+way;i+=way){
            for (j=Y;j<Y1+way;j+=way){
                Sum=Sum+(grid[i][j]*coeff);
                coeff*=10;
            }
        }
        }
        else {
         for (i=X;i>X1+way;i+=way){
             for(j=Y;j>Y1+way;j+=way){
                 Sum=Sum+(grid[i][j]*coeff);
                 coeff*=10;
             }
         }   
        }
        return Sum;
    }
        
        public boolean Valid(int X,int Y,int X1,int Y1,int Item,int nxt){
        int Sum=0,i,Xc,Yc;
        
        for (i=0;i<5;i++){
            if (Y1!=i)
                if (grid[X1][i]==Item)
                        return false;
            
            if (X1!=i)
                if (grid[i][Y1]==Item)
                    return false;
    
            if ((X1!=i) && (Y1!=i)&& (X1==Y1))
                if (grid[i][i]==Item)
                    return false;
            
    
            if ((X1+Y1)==4)
               if (X1!=i && grid[i][4-i]==Item)
                   return false;
          }
        
         if (X1==2 && Y1==2)
            return true;
         
         if (X1==0 && Y1==4)
             return true;
       
    
        if (X1==3 && Y1==1)
            X=1;
    
        if (X1==1 && Y1==4){
            X=0;
            X1=1;
        }
        
        Xc=X1-X;
        Yc=Y1-Y;
        
        if (grid[0][4]==0 || grid[1][3]==0 || grid[3][0]==0 || grid[3][3]==0)
            return false;
        
        if (Xc>0)
            Sum=CalculateNumber(X1,X,Y1,Y,-1);
         else if (Xc<0)
            Sum=CalculateNumber(X,X1,Y,Y1,1);
         else if  (Yc>0)
            Sum=CalculateNumber(X,X1,Y1,Y,-1);
         else if  (Yc<0)
            Sum=CalculateNumber(X,X1,Y,Y1,-1);
        
       
        if (IsPrime(Sum)){
          return true;
        }
       return false;
    
        
    }
        
        public boolean Distinct(){
        int [] count=new int[10];
        int i,j,item;
        
        for (i=0;i<5;i++){
            for (j=0;j<5;j++){
                item=grid[i][j];
                if (item>0)
                {
                    if (item%2==0)
                    {
                        count[item]+=1;
                    }
                    
                    if (count[item]>1)
                        return false;
                }
               
            }
        }
        return true;
    }
    
        public void Solve(int x,int y,int x1,int y1,int nxt){
        int i;
        
     
        if ((x1==-1) && (y1==-1)){
            
            return;
        }
        for (i=0;i<10;i++){ 
            grid[x1][y1]=i;
            cellnumber=(5*x1)+y1;
            value=i;
            repaint();
            
            
            try {
           Thread.sleep(100);
          }
          catch (InterruptedException e) { }
    
            if (Valid(x,y,x1,y1,i,nxt))
            {
               
               
            
                /*g.drawString(str,0,140);*/
                x=path[nxt][0];
                y=path[nxt][1];
                x1=path[nxt][2];
                y1=path[nxt][3];
               
                Solve(x,y,x1,y1,nxt+1);
                x=path[nxt-1][0];
                y=path[nxt-1][1];
                x1=path[nxt-1][2];
                y1=path[nxt-1][3];
                
              }
            
            grid[x1][y1]=-2;
            }
        }
     }
    
  6. geoffrounce 20 July 2017 at 7:27 pm

    This enigma is different to Enigma 1740, in that it does not state that all primes are to be different.
    In fact, prime number 31 appears twice and this time (!) I get the published single answer for this Enigma.

    I had to use a new ‘ at_most’ predicate in MiniZinc to allow for the condition that no even digit appears more than once anywhere:
    Usage:
    % predicate at_most (int: n, array [int] of var int: x, int: v)
    % Requires at most n variables in x to take the value v.

    Even digits 0, 4, and 6 appear once and digits 2 and 8 are absent from the grid in the answer.

    % A Solution in MiniZinc 
    % In the grid below, ghi and jn needed as shaded numbers 
    
    % a X X X b
    % c d X e f
    % X g h i X
    % j k X l m
    % n X X X p
    
    include "globals.mzn";
    
    % parameter variables
    int: a = 7;
    int: g = 3;
    
    % decision variables   
    var 1..9:b;  var 1..9:c;   var 0..9:d;   var 1..9:e;  var 0..9:f;  
    var 0..9:h;  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;
    
    array[1..13] of var 0..9: nbr = [b,c,d,e,f,h,i,j,k,l,m,n,p];
    
    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};
    
    % All eleven two and three digit answers are prime 
    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;
    
    % No digit appears more than once in any row, column or either of the two long diagonals
    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]);
    
    % No even digit (ie 0,2,4,6 or 8) appears more than once anywhere
    % nbr = [b,c,d,e,f,h,i,j,k,l,m,n,p], so this array includes all variables used (but not a and g)
    
    constraint at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 0)
    /\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 2) 
    /\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 4)
    /\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 6) 
    /\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 8);  
    
    solve satisfy;
    
    output[ "Shaded area values: " ++ show(jn) ++ " and " ++ show(ghi) ++ "\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) ];  
         
    % Shaded area values: 41 and 307
    
    % Grid Output:
    % 7XXX3
    % 31X67
    % X307X
    % 47X31
    % 1XXX9
    %----------
    % Finished in 58msec
    
    

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: