# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1750: Navigating the grid

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

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]

### 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

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))
}

# generate sequences starting with <s>
def generate(s):
# are we done?
if len(s) == 9:
yield s
else:
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
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…

This site uses Akismet to reduce spam. Learn how your comment data is processed.