# Enigmatic Code

Programming Enigma Puzzles

From New Scientist #2916, 11th May 2013 [link]

In the 4×4 grid shown, you must place all the unused arrow cards on the unshaded squares of the grid, such that by moving from card to card the number of squares in the direction shown on each, you complete a circuit visiting all 12 unshaded squares.

What are the numbers on the cards, from left to right, in the bottom row?

[enigma1748]

### 11 responses to “Enigma 1748: Quo Vadis?”

1. Jim Randell 8 May 2013 at 8:18 pm

Here’s a recursive solution in Python. It runs in 43ms.

```from enigma import irange, printf

# we represent the cells by (<row>, <column>) pairs

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

# placed cards
g[(0, 0)] = (0, 3)
g[(0, 3)] = (0, -1)

# unplaced cards
cards = set(((1, 0), (2, 0), (3, 0), (0, 1), (0, 2),
(-1, 0), (-2, 0), (-3, 0), (0, -2), (0, -3)))

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

# output a solution
def output(g):
for r in irange(0, 3):
print(''.join('[' + card(g, (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[0] + c[0], p[1] + c[1])
# 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,)))

# (0, 0) -> (0, 3) -> (0, 2) so solve for (0, 2) -> ... -> (0, 0)
solve(g, (0, 2), (0, 0), cards)
```

Solution: The numbers on the cards on the bottom row are 1, 3, 2, 1.

2. Brian Gladman 8 May 2013 at 11:47 pm

Here is my version, which is also recursive:

```# 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):

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

# 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]
# 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 last row are {:s}.'.format(
(' and '.join(new_cells[24:32:2])).replace(' and', ',', 2)))
return
else:
# otherwise place the next arrow symbol
place(new_cells, new_arrows, crnt)

# the given starting point
cells = '3R    1LSH  SH    SHSH          '
# the arrow symbols to be placed
arrows = '1D2D3D1R2R1U2U3U2L3L'
place(cells, arrows, 0)
```
3. Jim Randell 9 May 2013 at 7:48 am

In my solution I was originally going to use integers 0 to 15 to represent the cells, and then just use differences to represent the arrows, but I was worried about wraparound at the edges of the grid. So, for instance, the program might try 1R in square 7 (2nd row down, 4th column) to get to square 8 (3rd row down, 1st column), which I don’t think should be allowed. In the end I used (row,column) pairs so this problem doesn’t arise, rather than explicitly code around it.

I rewrote my program to use integers and it gives the same unique solution, so it looks like there are no solutions where this problem arises.

• Jim Randell 9 May 2013 at 2:43 pm

Actually the code to eliminate the wraparounds is probably worth the simplification gained from not using pairs. Here’s my revised Python program.

```from enigma import irange, printf

# use integers to represent the cells

# empty grid
g = dict((d, None) for d in (0, 1, 2, 3, 5, 7, 8, 11, 12, 13, 14, 15))

# placed cards
g[0] = +3
g[3] = -1

# unplaced cards
cards = set((+4, +8, +12, +1, +2, -4, -8, -12, -2, -3))

# represent the card at position p
def card(g, p):
if p not in g: return 'XX'
(r, c) = divmod(abs(g[p]), 4)
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, r * 4 + 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
# eliminate wraparounds
if n % 4 != p % 4 and n // 4 != p // 4: continue
# 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,)))

# (0, 0) -> (0, 3) -> (0, 2) so solve for (0, 2) -> ... -> (0, 0)
solve(g, 2, 0, cards)
```
• Brian Gladman 9 May 2013 at 8:36 pm

As you suggest, I should have avoided wraparounds but I was lucky and found that there was only one solution anyway and hence no false ones caused by them. I agree that this is a bit sloppy.

• Brian Gladman 9 May 2013 at 9:03 pm

Here it is again with wraparound elimination:

```# 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):

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

# 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[1] 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 last row are {:s}.'.format(
(' and '.join(new_cells[24:32:2])).replace(' and', ',', 2)))
return
else:
# otherwise place the next arrow symbol
place(new_cells, new_arrows, crnt)

# the given starting point
cells = '3R    1LSH  SH    SHSH          '
# the arrow symbols to be placed
arrows = '1D2D3D1R2R1U2U3U2L3L'
place(cells, arrows, 0)
```
• Jim Randell 10 May 2013 at 8:35 pm

And you can eliminate having to check for any potential wrap arounds by representing the grid by the centre of a 10×4 grid, then the horizontal moves can’t make it out of their own row.

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

# empty grid
g = dict((d, None) for d in (3, 4, 5, 6, 14, 16, 23, 26, 33, 34, 35, 36))

# placed cards
g[3] = +3
g[6] = -1

# unplaced cards
cards = set((+10, +20, +30, +1, +2, -10, -20, -30, -2, -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, r * 10 + c) + ']' for c in irange(3, 6)))
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,)))

# (0, 0) -> (0, 3) -> (0, 2) so solve for (0, 2) -> ... -> (0, 0)
solve(g, 5, 3, cards)
```
4. arthurvause 10 May 2013 at 2:38 pm

The two middle cells in the top row can readily be deduced, so only 432 permutations are possible for the remaining cells, only 6 of which use all the arrow cards.

``` from itertools import product

return ( u[0]+v[0],u[1]+v[1])

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 = [ [R3],         [D1],      [D3],   [L1], \
[""],         [U1,D2,R2],[""],   [L2,D2], \
[U2],         [""],      [""],   [L3,U1], \
[R1,R2,U1],   [R2,U3],   [L2,R1],[L2,L3,U1] ]

for p in product(*candidates):
if len(set(p))==13:
position = (0,0)
for i in xrange(12): # chase the circuit
if position == (0,0):
if i<11: # we have found a short circuit
break
else:
for row in xrange(4):
print [p[4*row+col] for col in xrange(4)]

```
5. arthurvause 11 May 2013 at 9:43 pm

A simplified version, representing the cells as numbers 0 to 15

```from itertools import product

L,R,U,D = -1,+1,-4,+4

candidates = [ [R*3],         [D*1],     [D*3],     [L*1], \
[""],          [D*2,R*2], [""],      [L*2,D*2], \
[U*2],         [""],      [""],      [L*3,U*1], \
[R*1,R*2,U*1], [U*3],     [L*2,R*1], [L*2,L*3,U*1] ]

for p in product(*candidates):
if len(set(p))==13:
position = 0
for i in xrange(12): # chase the circuit
position+= p[ position ]
if position == 0:
if i<11: # we have found a short circuit
break
else:
print [x if x<4 else x/4
for x in [abs(p[c]) for c in xrange(12,16)]]
```
6. Ahmet Saracoğlu 19 May 2013 at 11:01 pm
```
path=[[False for i in range(5)]for i in range(5)]
rule=[[1,0],[-1,0],[2,0],[-2,0],[3,0],[-3,0],[0,1],[0,-2],[0,2],[0,-3]]
Rls=[False]*10
cells=[0]*10
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==1 and y==0:
return False

if x==2 and y==1:
return False

if x==2 and y==2:
return False

if x==1 and y==2:
return False

if x==0 and y==3:
return False

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

path[x][y]=True
Rls[i]=True

return True

path[0][2]=True # starts from (x,y) at (0,2)

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

for i in range(10):
a,b=rule[i]
cells[counter]=i#Rules applied in order

##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==9 :
print("Cells",cells)

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

traverse(cells,0,0,2)#it starts from (0,2), (0,0) is the left corner at top.

#Cells [4, 7, 6, 5, 0, 8, 2, 1, 9, 3] print out
```
• Ahmet Saracoğlu 19 May 2013 at 11:07 pm

it is a depth-first search used in my algorithm and it is a recursive approach.

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