Enigmatic Code

Programming Enigma Puzzles

Enigma 1085: Cut and run

From New Scientist #2241, 3rd June 2000 [link]

Place your finger in the starting box in the grid and follow each instruction. You will find that you visit each square before finishing in the appropriate box.

Now cut up the board into six rectangles each consisting of two adjacent squares. Then put them back together to form a new three-by-four grid with the starting square one place lower than it was before. Do all this in such a way that, once again, if you follow the instructions you visit each square.

In your new grid, what instruction is in the top left-hand corner, and what is the instruction in the bottom right-hand corner?

[enigma1085]

2 responses to “Enigma 1085: Cut and run

  1. Jim Randell 4 December 2017 at 8:17 am

    I tackled this puzzle in two parts. The first part is to arrange the squares in the grid so that you can start in row 2, column 2 and complete the gird. The second part is to look at the grid made from the first part and see if it can be made from the original grid by cutting it into dominoes.

    This Python 3 code runs in 124ms.

    Run: [ @repl.it ]

    from enigma import irange, update, ordered, chunk, printf
    
    # label the squares:
    #
    #   0  1  2  3
    #   4  5  6  7
    #   8  9 10 11
    
    squares = set(irange(0, 11))
    
    # then the corresponding move functions are
    def move(k, i):
      (r, c) = k
      moves = {
        # 0: "go down one"
        0: (r + 1, c),
        # 1: "start here, and go right one"
        1: (r, c + 1),
        # 2: "go diagonally one, down + right"
        2: (r + 1, c + 1),
        # 3: "go down two if possible: if not, go up one"
        3: (r + 2, c) if r < 2 else (r - 1, c),
        # 4: "go right two"
        4: (r, c + 2),
        # 5: "go diagonally one, down + left"
        5: (r + 1, c - 1),
        # 6: "go diagonally one, up + right"
        6: (r - 1, c + 1),
        # 7: "go left two"
        7: (r, c - 2),
        # 8: "go up two"
        8: (r - 2, c),
        # 9: "go right one"
        9: (r, c + 1),
        # 10: "finish here", so we don't need it
        # 11: "go left two"
        11: (r, c - 2)
      }
      (r1, c1) = moves.get(i, (0, 0))
      assert 0 < r1 < 4 and 0 < c1 < 5
      return (r1, c1)
    
    def solve(g, k, squares):
      # are we done?
      if not squares:
        yield (g, k)
      # choose a square to place at (r, c)
      for i in squares:
        try:
          k2 = move(k, i)
        except AssertionError:
          continue
        if k2 not in g:
          yield from solve(update(g, [(k, i)]), k2, squares.difference([i]))
    
    # choose a value from dict <d>
    def choose(d):
      for x in d.items():
        return x
    
    # find value <v> in dict <d>
    def find(d, v):
      for (k, v1) in d.items():
        if v == v1:
          return k
    
    # remove items from dict <d>
    def remove(d, ks):
      d = d.copy()
      for k in ks:
        del d[k]
      return d
    
    # can g1 and g2 be made from the same set of dominoes?
    def dominoes(g1, g2, ds=set()):
      # are we done?
      if not g1:
        if not g2:
          yield sorted(ds)
      else:
        # choose a square from g1
        ((r1, c1), s1) = choose(g1)
        # and consider adjacent squares
        for (r2, c2) in ((r1 - 1, c1), (r1 + 1, c1), (r1, c1 - 1), (r1, c1 + 1)):
          s2 = g1.get((r2, c2))
          if s2 is None: continue
          # are they adjacent squares in g2?
          ((r1x, c1x), (r2x, c2x)) = (find(g2, s1), find(g2, s2))
          (r, c) = (abs(r1x - r2x), abs(c1x - c2x))
          if (r == 0 and c == 1) or (c == 0 and r == 1):
            # remove the domino from each grid, and solve the remaining squares
            yield from dominoes(remove(g1, [(r1, c1), (r2, c2)]), remove(g2, [(r1x, c1x), (r2x, c2x)]), ds.union([ordered(s1, s2)]))
    
    # the diagram grid
    g0 = dict()
    for i in squares:
      (r, c) = (x + 1 for x in divmod(i, 4))
      g0[(r, c)] = i
    
    # set up the new grid
    (k, i) = ((2, 2), 1)
    grid = { k: i }
    
    # place all the squares (except the final square) in the grid
    for (g, k) in solve(grid, move(k, i), squares.difference([i, 10])):
      # place the final square
      g = update(g, [(k, 10)])
      # try to match the grids dominowise
      for ds in dominoes(g0, g):
        printf("top left = {tl}, bottom right = {br}", tl=g[(1, 1)], br=g[(3, 4)])
        printf("  grid = {g}", g=list(chunk((g[(r, c)] for r in irange(1, 3) for c in irange(1, 4)), 4)))
        printf("  dominoes = {ds}")
    

    Solution: In the new grid the instruction in the top left-hand corner is “GO RIGHT TWO”, and the instruction in the bottom right-hand corner is “GO LEFT TWO”.

    There is only one way to make up the grid so that you can start in row 2, column 2 and complete the grid, even if you cut the original grid into single squares, so we know what the solution is, if it is possible.

    There are two tiles that read “GO LEFT TWO”, so these tiles can be interchanged without changing the pattern. But by cutting the original grid into 2×1 “dominoes” only one of these tiles can appear in the bottom right-hand square, but there are multiple ways to make the cuts. We can cut the square into 2 2×1 rectangles and 2 2×2 rectangles which re-arrange to make the solution grid, as shown below:

    The 2×2 tiles can be cut either horizontally or vertically to make dominoes, which gives us 4 different sets of dominoes that can be arranged to make the grid.

  2. Brian Gladman 6 December 2017 at 5:26 pm
    # the (x, y) increments for the different moves
    A, B, C, D, E, F, G, H, I, J, K = (
       ( 0, -1), (1, 0), ( 1, -1), (0, -2), (2, 0),
       (-1, -1), (1, 1), (-2,  0), (0,  2), (0, 0), (0, 1) )
    
    # the twelve tile types (labelled 1 to 12)
    tiles = ( (1, A, J), ( 2, B, J), ( 3, C, J), ( 4, D, K),
              (5, E, J), ( 6, F, J), ( 7, G, J), ( 8, H, J),
              (9, I, J), (10, B, J), (11, J, J), (12, H, J) )
    
    # find a grid of tiles that can be fully traversed
    def solve(g, pos, tiles):
      x, y = pos
      # are all tiles except the finish tile placed?
      if not tiles:
        # place the 'finish' tile and return the tile positions
        g[4 * y + x] = 11
        yield g
        g[4 * y + x] = 0
      else:
        # consider unplaced tiles
        for i, t1, t2 in tiles:
          # try its possible moves
          for t in (t1, t2):
            xx, yy = pp = (x + t[0], y + t[1])
            # is the move valid?
            if pp != pos and (0 <= xx < 4 and 0 <= yy < 3) and not g[4 * yy + xx]:
              # place the tile and proceed to the next move
              g[4 * y + x] = i
              yield from solve(g, (xx, yy), [z for z in tiles if z[0] != i])
              g[4 * y + x] = 0
              break
    
    # adjacent positions for in the grid for the indexed position
    adj = [ (1, 4), (0, 2, 5), (1, 3, 6), (2, 7),
            (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9), (5, 8, 10), (6, 9, 11), (7, 10) ]
    
    # pair the same tiles in two grids
    def pair_tiles(g1, g2, pt=[]):
      if len(pt) == 6:
        yield tuple(sorted(pt))
      else:
        # pick a tile
        p1, t1 = g1.popitem()
        # ... and consider adjacent tiles
        for p2 in adj[p1]:
          t2 = g1.get(p2)
          if t2:
            # find the tiles in the second grid
            q1, q2 = (p for p, t in g2.items() if t in {t1, t2})
            # if this tile is also adjacent in the second grid 
            if q2 in adj[q1]:
              # remove the tiles and continue to the next pairing
              h1 = {p:t for p, t in g1.items() if p not in {p1, p2}}
              h2 = {p:t for p, t in g2.items() if p not in {q1, q2}}
              yield from pair_tiles(h1, h2, pt + [tuple(sorted((t1, t2)))])
            
    # position for the first tile
    x, y = pos = (1, 1)
    # form the grid and place the first tile
    g = [0] * 12
    g[4 * y + x] = 2
    # list tiles that remain to be placed (except the finish tile)
    sm = [x for x in tiles if x[0] not in {2, 11}]
    # find solutions
    for g in solve(g, (x + 1, y), sm):
      print(f'Grid: (r1 r2 r3): {g[8:]} {g[4:8]} {g[:4]}')  
      # the initial and re-arranged grids as dictionaries (position:tile)
      g0 = {i:i + 1 for i in range(12)}
      g1 = {i:v for i, v in enumerate(g)}
      for pl in pair_tiles(g0, g1):
        print(f'  Top Left = {g[8]}, bottom Right = {g[3]}')
        print(f'  Tile Pairings {pl}')
    

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: