Enigmatic Code

Programming Enigma Puzzles

Enigma 1750: Navigating the grid

From New Scientist #2918, 25th May 2013 [link]

Enigma 1750

Using the number grid shown (A) it is possible to generate nine-digit numbers in the following way: Start on any square and then move horizontally, vertically or diagonally to an adjacent square that hasn’t already been visited. Repeat until all nine squares have been visited. For example, the path shown in diagram B generates the number 235968741.

I have listed all the numbers that can be generated in this way, and that end in a certain digit. Some of these are divisible by four (and only four) of the numbers 1 to 9. The rest are divisible by five (and only five) of the numbers 1 to 9.

How many numbers are there in my list?

[enigma1750]

Advertisements

7 responses to “Enigma 1750: Navigating the grid

  1. Jim Randell 22 May 2013 at 6:04 pm

    This Python program runs in 58ms. It uses the yield from construct so without modification it needs to be run under Python 3.

    from enigma import nconcat, printf
    
    # adjacency matrix
    adj = {
      1: set((2, 4, 5)),
      2: set((1, 3, 4, 5, 6)),
      3: set((2, 5, 6)),
      4: set((1, 2, 5, 7, 8)),
      5: set((1, 2, 3, 4, 6, 7, 8, 9)),
      6: set((2, 3, 5, 8, 9)),
      7: set((4, 5, 8)),
      8: set((4, 5, 6, 7, 9)),
      9: set((5, 6, 8))
    }
    
    digits = adj.keys()
    
    # generate sequences starting with <s>
    def generate(s):
      # are we done?
      if len(s) == 9:
        yield s
      else:
        for d in adj[s[-1]].difference(s):
          yield from generate(s + [d])
    
    # check sequences ending in <d>
    def check(d):
      i = 0
      for s in generate([d]):
        # turn the sequence into a number ending in <d>
        n = nconcat(s[::-1])
        # count how many of the digits divide n
        c = sum(1 for x in digits if n % x == 0)
        # if the count isn't 4 or 5 we're not interested
        if c not in (4, 5): return
        i += 1
      printf("num sequences = {i} [final digit = {d}]")
    
    # check each ending digit
    for d in digits:
      check(d)
    

    Solution: There are 32 numbers in the list.

  2. arthurvause 22 May 2013 at 7:12 pm

    A rather fiddly solution:

    graph = { 1:[2,4,5],2:[1,4,5,6,3],3:[2,5,6],4:[1,2,5,7,8], \
              5:[1,2,3,4,6,7,8,9],6:[2,3,5,8,9],7:[4,5,8], \
              8:[7,4,5,6,9], 9:[5,6,8]}
    
    candidates = set()
    
    def move(number,pos):
      number.append(pos)
      if len(number)==9:
        candidates.add( int(''.join([str(number[i]) for i in xrange(9)])))
        
      for x in graph[pos]:
        if x not in number:
          move(number,x)
      del number[-1]
      
    for start in xrange(1,10):
      number = []
      move([],start)
        
    #print len(candidates), sorted(candidates)[0:6], min(candidates), max(candidates)
    
    def num_divis(x):
      return len( [i for i in xrange(1,10) if x%i==0])
    
    for n in xrange(1,10):
      candidates_n = [x for x in candidates if x%10==n]
      #print len (candidates_n)
      OK = True
      for x in candidates_n:
        if num_divis(x) not in  (4,5):
          OK=False
          break
      if OK:
        print len(candidates_n),"numbers ending in", n
        
    
  3. Brian Gladman 22 May 2013 at 9:29 pm

    Pretty similar to Jim’s version:

    # dictionary listing adjacent cells
    adj = { 1:(2,4,5), 2:(1,3,4,5,6), 3:(2,5,6),
            4:(1,2,5,7,8), 5:(1,2,3,4,6,7,8,9), 6:(2,3,5,8,9),
            7:(4,5,8), 8:(4,5,6,7,9), 9:(5,6,8) }
    
    # add to list 'seq' from cells in 'left' if possible
    def solve(seq, left):
      # if all cells have been visited
      if not left:
        # create the number back to front
        yield int(''.join(str(x) for x in seq[::-1]))
      else:
        # move on to the next cell
        for n in adj[seq[-1]]:
          if n in left:
            yield from solve(seq + [n], left - set((n,)))
    
    def find(n):
      cnt = 0
      # process all numbers with the last digit 'n'
      for nbr in solve([n], set(range(1, 10)) - set((n,))):
        # count its divisors in 1..9, exiting if any are
        # neither 4 nor 5
        if 4 <= sum(1 for d in range(1, 10) if not nbr % d) <= 5:
          cnt += 1
        else:
          return
      print('There are {:d} numbers in the list.'.format(cnt))
    
    # for each possible last digit
    for n in range(1, 10):
      find(n)
    
  4. arthurvause 23 May 2013 at 6:00 pm

    All nine-digit numbers formed from digits 1 to 9 are divisible by 1,3,9.

    If the ending digit of the answer is even, then all the candidate numbers are divisble by 1,2,3,6,9, so no candidates are divisible by exactly four of the numbers 1 to 9.

    If the ending digit is one of 1,3,7,9, then the candidate numbers can only be divisible by 1,3,7,9, so no candidates are divisible by exactly five of the numbers 1 to 9.

    The ending digit therefore has to be 5.

    From there, it is not hard to enumerate by hand the patterns of sequences that end at 5.

  5. ahmet çetinbudaklar 26 May 2013 at 7:59 am

    The ending digit can only be 5 as it is only then searched number can only be divisible by 4 and 5 odd digits exactly as no even number can be a divisor which easily takes us to the solution by a very few number of sets.

  6. saracogluahmet 27 May 2013 at 12:41 pm
    import time
    print(time.time())
    
    rule=[[1,1],[0,1],[0,-1],[-1,0],[1,0],[-1,-1],[1,-1],[-1,1]]
    
    path=[[False for i in range(3)]for i in range(3)]
    
    cells=[0]*8
    
    
    M=[[1,2,3],[4,5,6],[7,8,9]]
    
    
    def valid(x,y):
    
        
        if x<0 or x>2:
            return False
        if y<0 or y>2:
            return False
        if path[x][y]==True:#if the cell already have been visited, mark it
            return False
        
        path[x][y]=True # Mark the cell
        return True
    
    def PrintCells(x,y,cells):
        p=[5]*9
        divisibleby7=[1,3,2,6,4,5] #this is for checking number if it is divisible by 7 or not
        productandsum,k=0,0
        valid=''
        
        for i in range(8):
            a,b=rule[cells[i]]
            x,y=x+a,y+b
            p[7-i]=M[x][y]
    
        for i in range(8,0,-1):
            productandsum=productandsum+p[i]*divisibleby7[k]
            k=(k+1)%6
    
        if productandsum%7==0:
            valid="VALID"
        else:
            valid="NOT VALID"
    
        print(p,productandsum,valid)
       
            
        
    def traverse(cells,counter,x,y):
    
        for i in range(8):
            a,b=rule[i]
            cells[counter]=i
            
            
           
            if valid(x+a,y+b):# if the applied rule is valid,
               
                if counter==7:#stop criteria
                    path[x+a][y+b]=False #backtraking to unmark the last cell
                    PrintCells(1,1,cells)
                else:
                    traverse(cells,counter+1,x+a,y+b)#call the function recursivly
                    path[x+a][y+b]=False
                  
    #it starts from the middle cell, that is 5.		
    path[1][1]=True
    p=traverse(cells,0,1,1)
    print (time.time())
    
    • saracogluahmet 27 May 2013 at 9:31 pm
              if valid(x+a,y+b):# if the applied rule is valid,
                  
                  if counter==7:#stop criteria
               #       path[x+a][y+b]=False #backtraking to unmark the last cell
                      PrintCells(1,1,cells)
                  else:
                      traverse(cells,counter+1,x+a,y+b)#call the function recursivly
                  path[x+a][y+b]=False
      

      I changed that part with the above code, only one is enough, missed that…

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: