Enigmatic Code

Programming Enigma Puzzles

Enigma 1748: Quo Vadis?

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

Enigma 1748

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]

Advertisements

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
    def add(d, k, v):
      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
      def add(d, k, v):
        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
        def add(d, k, v):
          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
    
    def add(u,v):
        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
          position = add(position,p[position[0] + position[1]*4])
          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
    

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: