# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1762: Quo Vadis? II

From New Scientist #2930, 17th August 2013 [link] On the grid shown on the right, place the remaining 11 cards on the unshaded squares so that when you move from card to card the number of squares in the direction shown on each, you complete a circuit visiting all 12 unshaded squares once.

What are the numbers on the cards, from top to bottom, in the third column?

[enigma1762]

### 11 responses to “Enigma 1762: Quo Vadis? II”

1. Jim Randell 14 August 2013 at 6:33 pm

Basically the same puzzle as Enigma 1748. So it is unsurprising that the same technique can be used to solve it. This Python program – the same as my solution for Enigma 1748, but with some parameters altered – runs in 38ms.

```from enigma import irange, printf

# use integers to represent the cells in the centre of a 10x4 grid
# so: (r, c) -> 10 * r + c + 3
def rc2i(r, c, offset=3):
return 10 * r + c + offset

# empty grid
g = dict((rc2i(r, c), None) for (r, c) in (
(0, 0), (0, 1), (0, 2),
(1, 0), (1, 2), (1, 3),
(2, 0), (2, 2), (2, 3),
(3, 1), (3, 2), (3, 3),
))

# placed cards
g[rc2i(0, 0)] = rc2i(+2, 0, 0)

# unplaced cards
cards = set(rc2i(r, c, 0) for (r, c) in (
(+1, 0), (+3, 0),
(-1, 0), (-2, 0), (-3, 0),
(0, -1), (0, -2), (0, -3),
(0, +1), (0, +2), (0, +3),
))

# represent the card at position p
def card(g, p):
if p not in g: return 'XX'
(r, c) = divmod(abs(g[p]), 10)
if r == 0:
return str(c) + ('R' if g[p] > 0 else 'L')
else:
return str(r) + ('D' if g[p] > 0 else 'U')

# output a solution
def output(g):
for r in irange(0, 3):
print(''.join('[' + card(g, rc2i(r, c)) + ']' for c in irange(0, 3)))
print('')

# return an updated dictionary
d = d.copy()
d[k] = v
return d

# g - current grid
# p - current position in grid
# t - target position
# cards - remaining cards
def solve(g, p, t, cards):
# are there any cards left to place?
if len(cards) == 0:
# have we reached the target
if p == t: output(g)
return
# otherwise try placing a card
for c in cards:
# where does it point?
n = p + c
# if it's not the last card it should point to an empty square
if n in g and (len(cards) == 1 or g[n] is None):
# solve for the remaining cards
solve(add(g, p, c), n, t, cards.difference([c]))

# solve (2, 0) -> ... -> (0, 0)
solve(g, rc2i(2, 0), rc2i(0, 0), cards)
```

Solution: The numbers in the third column are: 3, 1, 2, 1.

Here’s the completed grid: 2. arthurvause 14 August 2013 at 7:27 pm

And here’s my modified version of 1748:

```from itertools import product

return ( u+v,u+v)

blank=(0,0)
R1,R2,R3 = (1,0),(2,0),(3,0)
L1,L2,L3 = (-1,0),(-2,0),(-3,0)
U1,U2,U3 = (0,-1),(0,-2),(0,-3)
D1,D2,D3 = (0,1),(0,2),(0,3)

candidates = [ [D2], [L1,R1,R3], [L1,L2,D1,D3], [blank], \
[U1,D1,R2,R3], [blank], [L2,R1,U1,D1], [L3,L1,D1], \
[U1,R2,R3], [blank], [L2,R1,U2,U1,D1], [L3,L1,U1,D1], \
[blank], [U3,R1,R2], [U1,U2,U3,L1,R1], [L2,L1,U1,U2] ]

for c in product(*candidates):
if len(set(c))==13:
pos = (0,0)
for i in xrange(12):
if pos == (0,0):
if i<11:
break
else:
for row in xrange(4):
print [c[4*row+col] for col in xrange(4)]

```
• saracogluahmet 15 August 2013 at 3:10 pm

Hi,
Execution time of your code on my machine is almost 7.5 seconds

• arthurvause 20 August 2013 at 8:21 am

Indeed. Here is a faster version:

```R1,R2,R3,L1,L2,L3 = 1,2,3,-1,-2,-3
U1,U2,U3,D1,D2,D3 = -4,-8,-12,4,8,12
labels={1:"R1",2:"R2",3:"R3", -1:"L1",-2:"L2",-3:"L3", \
-4:"U1",-8:"U2",-12:"U3", 4:"D1",8:"D2",12:"D3",  0:"  "}

candidates = [ set((D2,)), set((L1,R1,R3,D3)), set((L1,L2,D1,D3)), set(), \
set((U1,D1,R2,R3)), set(), set((L2,R1,U1,D1)), set((L3,L1,D1)), \
set((U1,R2,R3)), set(), set((L2,R1,U2,U1,D1)), set((L3,L1,U1,D1)), \
set(), set((U3,R1,R2)), set((U1,U2,U3,L1,R1)), set((L2,L1,U1,U2)) ]

available = set((R1,R2,R3,L1,L2,L3,U1,U2,U3,D1,D3))
occupied = [D2,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0]
counter=0
pos=0

def check(pos):
moves = candidates[pos] & available
for m in moves:
if occupied[pos+m] in (0,D2):
available.remove(m)
occupied[pos]=m
if len(available)==0:
for row in xrange(4):
for col in xrange(4):
print labels[occupied[col+4*row]],
print " "
else:
check(pos+m)
occupied[pos]=0

check(D2)
```
3. saracogluahmet 14 August 2013 at 9:59 pm

I used the same approach where I did use in Enigma 1748,
I start to walk from the first cell,

1376513633.509371
Cells [-1, 2, 5, 6, 1, 9, 7, 10, 0, 4, 8]
1376513633.540597
Timing in my machine is like above,

```
import time
print(time.time())
path=[[False for i in range(5)]for i in range(5)]
Rls=[False]*11
path=True
cells=[-1]*11
rule=[[0,1],[0,2],[0,3],[0,-1],[0,-2],[0,-3],[-1,0],[-2,0],[-3,0],[1,0],[3,0]]

flag=False

def valid(x,y,i):

if Rls[i]==True:
return False

if x<0 or x>3:
return False
if y<0 or y>3:
return False
if x==0 and y==3:
return False
if x==1 and y==1:
return False
if x==2 and y==1:
return False
if x==3 and y==0:
return False
if x==0 and y==0:
return False

if path[x][y]==True:
return False
path[x][y]=True
Rls[i]=True
return True

def traverse(cells,counter,x,y):
global flag

if flag==True:
return
for i in range(11):
a,b=rule[i]
cells[counter]=i
##print("x=",x+a,"y=",y+b)
if valid(x+a,y+b,i):
##print("x=",x+a,"y=",y+b)
#print(cells)
if counter==10:
print("Cells",cells)
flag=True
else:
##print ("IN",x,y,i,counter)
traverse(cells,counter+1,x+a,y+b)
#print("hi",i,"x:",x,"y:",y,"a",a,"b",b)
#print (i,x,y,a,b,path[x+a][y+b])
Rls[i]=False
path[x+a][y+b]=False
##print(path[x+a][y+b])

traverse(cells,1,2,0)
print(time.time())
```
• saracogluahmet 14 August 2013 at 10:24 pm

Cells [-1, 2, 6, 5, 1, 9, 7, 10, 0, 4, 8] must be replaced with the previous one, the first one in invalid and “path= True” must be replaced with path=True at the top of the code, and in the valid function  cell is not checked, instead,  cell will be checked, as the first cell has been given already, no need to check that.

• Brian Gladman 15 August 2013 at 8:32 am

Ahmet, why are you still using such an error prone method for timing your code when you know that this has caused you problems in the past?

If for some reason you don’t want to use a better method, you could at least put ‘start=time.time()’ at the beginning and ‘print(time.time() – start)’ at the end to avoid the need to do the manual subtraction.

• saracogluahmet 15 August 2013 at 11:18 am

Hi Brian,

You are right 🙂

Cells [-1, 2, 6, 5, 1, 9, 7, 10, 0, 4, 8]
0.015599966049194336
I did that what you said, I guess this means 15 ms almost 16 ms, and my machine’s cpu 2.60 Hz and 6GB Ram.

You would like to test the timing on your processors, if you wish.

• Brian Gladman 16 August 2013 at 11:23 pm

You are lucky to find the right path Ahmet as there is another bug in your code. When you reach the end of your path you need to check that the last move gets you back to the first cell but you don’t check this since you only use 10 of the eleven cards. As it happens the unused card on your path is (0,-1) so it does get back to (0, 0), which was lucky 🙂

Here is a a commented and (I hope) corrected version of your code that uses Jim’s new timer in his latest enigma version

```from enigma import Timer

timer = Timer()

# the 11 possible moves as [down, right] where x is down and y is right
rules = [ [ 0, 1], [ 0, 2], [ 0, 3],
[ 0,-1], [ 0,-2], [ 0,-3],
[-1, 0], [-2, 0], [-3, 0],
[ 1, 0], [ 3, 0] ]

# is a move to grid cell
def valid(x, y, i):

# if the new position is outside the 4 by 4 grid
if ( x < 0 or x > 3 or y < 0 or y > 3 or
# or it is on a shaded cell
y == 0 and x == 3 or
y == 1 and x in (1, 2) or
y == 3 and x == 0 ):
return False

# return True if the cell is not yet on the path
return not grid[x][y]

def traverse(path, counter, x, y):

# 'counter' is the position on the path and the contents of
# path[counter] is the rule used at this point on the path

# apply all (unused) rules at this point on the grid
for i, (a, b)  in enumerate(rules):
# if the rule has not been used yet
if not rule_used[i]:
xx, yy = x + a, y + b
# check if the prospective move is legal
if valid(xx, yy, i):
# if so, put this rule on the grid at the current position
path[counter] = i
# check if we have used all cards and are back at the first cell
if counter == 10 and xx == yy == 0:
# now find content of grid column three (yp == 2)
col3, xp, yp =  * 4, 2, 0
# move along the path
for r in path:
# the move for this point on the path
a, b = rules[r]
# if in column three, store the card value indexed on x
if yp == 2:
col3[xp] = str(abs(a + b)) + ' and '
# move to the next cell on the path
xp, yp = xp + a, yp + b
col3 = ''.join(col3).replace(' and ', ', ', 2)[:-5]
print('The values in the third column are {:s}.'.format(col3))
else:
# mark the grid position and the rule used
grid[xx][yy] = True
rule_used[i] = True
# otherwise continue to build the path
traverse(path, counter + 1, xx, yy)
# free the grid position and the rule for use
rule_used[i] = False
grid[xx][yy] = False

# the 4 by 4 grid of path
grid = [[False] * 4 for i in range(4)]
# for marking the move rules as used
rule_used = [False] * 12
# start AFTER the move from the first cell
grid = True
# initialises positions on the path
path = [-1] * 11
traverse(path, 0, 2, 0)
```

Do not despair – you are not the only one with bugs this week!

4. Brian Gladman 14 August 2013 at 10:22 pm

I am sad to say that in doing this one I found a bug in my two solutions to enigma 1748 😦 I don’t like leaving buggy code around so if you could correct my two programs for that enigma, Jim, I would be most grateful – the return on line 45 in the first and line 48 in the second should be indented by two more spaces (one more level).

Here is this one:

```# Each cell in the 4 by 4 array is represented by two characters
# in a 32 character string,  starting at the top left and ending
# at the bottom right.   The first character in a cell gives the
# number of steps,  the second the direction (L, R, U, D), where
# empty cells contain '  ' and shaded cells contain 'SH'.

# the moves along the sequence as a function of a cell's contents
moves = {'1L':-2, '2L': -4, '3L': -6, '1R':2, '2R': 4, '3R': 6,
'1U':-8, '2U':-16, '3U':-24, '1D':8, '2D':16, '3D':24 }

# place the next arrow in the next empty, unshaded cell
def place(cells, arrows, crnt, l):

# find the next vacant cell after the current one
while True:
# the contents of the current cell
cell = cells[crnt:crnt+2]
# break if it is empty
if cell == '  ':
break
# otherwise move on to the next cell
crnt += moves[cell]
assert cells.count(' ') == len(arrows)
# try each remaining arrow in this empty cell
for p in range(0, len(arrows), 2):
# the arrow symbol
cell = arrows[p:p+2]
# the position of the next cell in the sequence
move = crnt + moves[cell]
# ensure that Left/Right moves stay in the current row
if cell in ('L', 'R') and move // 8 != crnt // 8:
continue
# skip positions outside the sequence or occupied cells
if not 0 <= move < len(cells) or move and cells[move] != ' ':
continue
# remove the chosen cell value from arrows
new_arrows = arrows.replace(cell, '', 1)
# and insert it into cells
new_cells = cells[:crnt] + cell + cells[crnt+2:]

# if we are about to move to the first (top left) cell
if move == 0:
# and we have placed all the arrow symbols
if not new_arrows:
# then output the ressult
print('The numbers in the third column are {:s}.'.format(
(' and '.join(new_cells[4:32:8])).replace(' and', ',', 2)))
return
else:
# otherwise place the next arrow symbol
place(new_cells, new_arrows, crnt, l + 1)

# the given starting point
cells = '2D    SH  SH      SH    SH      '
# the arrow symbols to be placed
arrows = '1R2R3R1L2L3L1U2U3U1D3D'
place(cells, arrows, 0, 0)
```
5. saracogluahmet 17 August 2013 at 10:56 am

As I have forgotton to uncomment two lines in my previous code, I have deleted those two lines, and I have changed so, yeah, my code had a small bug, but the algorithm is the same as the previous one, sorry for that. This is the last one and the timing is the same as in the previous one, I am sorry to have uncommented those two lines.

```import time
start=time.time()
path=[[False for i in range(5)]for i in range(5)]
Rls=[False]*11

path=True
cells=[-1]*11
rule=[[0,1],[0,2],[0,3],[0,-1],[0,-2],[0,-3],[-1,0],[-2,0],[-3,0],[1,0],[3,0]]

flag=False

def valid(x,y,i):

if Rls[i]==True:
return False

if x<0 or x>3:
return False
if y<0 or y>3:
return False
if x==0 and y==3:
return False
if x==1 and y==1:
return False
if x==2 and y==1:
return False
if x==3 and y==0:
return False

if path[x][y]==True:
return False
path[x][y]=True
Rls[i]=True
return True

def traverse(cells,counter,x,y):
global flag

for i in range(11):
a,b=rule[i]
cells[counter]=i
##print("x=",x+a,"y=",y+b)
if valid(x+a,y+b,i):
##print("x=",x+a,"y=",y+b)
#print(cells)
if counter==10:
print("Cells",cells)
#flag=True
else:
##print ("IN",x,y,i,counter)
traverse(cells,counter+1,x+a,y+b)
#print("hi",i,"x:",x,"y:",y,"a",a,"b",b)
#print (i,x,y,a,b,path[x+a][y+b])
Rls[i]=False
path[x+a][y+b]=False
##print(path[x+a][y+b])

traverse(cells,0,2,0)
print(time.time()-start)
```

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