Enigmatic Code

Programming Enigma Puzzles

Enigma 1309: Fill, cut and fit

From New Scientist #2467, 2nd October 2004

Amber and Ben have a new game which they play on this board.

Enigma 1309

Starting with Amber and going alternately, they each write their initial in an empty square until the board is full. They each then make a paper copy of the board; Amber cuts hers into three vertical strips and Ben cuts his into two horizontal strips. The board is then wiped clean. Starting with Amber and going alternately, they each place one of their own strips onto the board; each strip must retain its orientation and be placed so as to fit neatly over the two or three squares of the board.

They must not overlap their own strips but when they overlap a strip already placed by the other child then the letters in the overlapping squares must agree. If both children place all their strips then the game is a draw; otherwise a child wins when the other child cannot place a strip.

If both children play as well as possible, who wins or is it a draw?

[enigma1309]

Advertisements

2 responses to “Enigma 1309: Fill, cut and fit

  1. Jim Randell 15 July 2014 at 7:08 am

    This Python program considers all possible moves. It runs in 277ms.

    # label the grid:
    #
    # 0 1 2
    # 3 4 5
    #
    # so columns are: (0, 3), (1, 4), (2, 5)
    # rows are: (0, 1, 2), (3, 4, 5)
    
    from itertools import product
    from enigma import printf
    
    # update a grid
    def update(grid, *args):
      grid = list(grid)
      for (i, p) in args:
        grid[i] = p
      return grid
    
    # remove an element from a list
    def remove(l, i):
      l = list(l)
      del l[i]
      return l
    
    # return the first element of <args> in <r> (or the last element of <args>)
    def best(r, *args):
      for x in args:
        if x in r: break
      return x
    
    # return values (the "other" player is player ^ 3)
    (draw, A, B) = (0, 1, 2)
    
    # fit the strips into the grid
    def fit(grid, player, As, Ap, Bs, Bp):
      # is the game drawn?
      if not(As or Bs):
        return draw
      elif player == A:
        # A to play, choose a strip and a position
        r = set(
          fit(update(grid, (p, s[0]), (p + 3, s[1])), B, remove(As, i), remove(Ap, j), Bs, Bp)
          for ((i, s), (j, p)) in product(enumerate(As), enumerate(Ap))
          if grid[p] in (0, s[0]) and grid[p + 3] in (0, s[1])
        )
        # play the best outcome
        return best(r, A, draw, B)
      else:
        # B to play, choose a strip and a position
        r = set(
          fit(update(grid, (p, s[0]), (p + 1, s[1]), (p + 2, s[2])), A, As, Ap, remove(Bs, i), remove(Bp, j))
          for ((i, s), (j, p)) in product(enumerate(Bs), enumerate(Bp))
          if grid[p] in (0, s[0]) and grid[p + 1] in (0, s[1]) and grid[p + 2] in (0, s[2])
        )
        # play the best outcome
        return best(r, B, draw, A)
    
    # fill out the grid
    def fill(grid, player):
      # is the grid filled out?
      if 0 not in grid:
        # generate the strips and positions
        (As, Ap) = ([(grid[0], grid[3]), (grid[1], grid[4]), (grid[2], grid[5])], [0, 1, 2])
        (Bs, Bp) = ([(grid[0], grid[1], grid[2]), (grid[3], grid[4], grid[5])], [0, 3])
        return fit([0, 0, 0, 0, 0, 0], A, As, Ap, Bs, Bp)
      else:
        other = player ^ 3
        # consider possible positions
        r = set(
          fill(update(grid, (i, player)), other)
          for (i, p) in enumerate(grid)
          if p == 0
        )
        # play the best outcome
        return best(r, player, draw, other)
        
    # A's initial play is a corner or an edge
    for grid in ([A, 0, 0, 0, 0, 0], [0, A, 0, 0, 0, 0]):
      r = fill(grid, B)
      printf("{grid} -> {r}", grid=' '.join('xAB'[x] for x in grid), r=['draw', 'A', 'B'][r])
    

    Solution: The result is always a draw.

    The program considers the two different opening moves for A: playing on a corner square or an edge square. Both opening positions result in a draw.

    We could start with a blank board and allow A to play in any position, which would take the program longer to consider, but produce the same result.

    • Jim Randell 15 July 2014 at 7:29 am

      Analytically we can consider cases after the grid has been filled and then cut into columns (for player A) and rows (for player B).

      Suppose there is a column consisting of two of the same symbols (say two A’s). There are two columns remaining and 4 symbols (ABBB), so there must also be a column consisting of two B’s (and the other column is an A and a B). Player A knows where the BB column was, and so each of the rows that player B has must have a B in that position, so they can simply play the AA column in that position, B cannot play either of his rows, so this is a win for player A.

      In order to stop this happening player B must ensure that there are never two of the same symbol in any column during the “fill” stage of the game. This can simply be achieved by playing a B in the same column as player A plays their A.

      If this happens the filled out grid will always consist of mixed columns. So there are either:

      (1) three columns the same (e.g. AB, AB, AB), which gives two rows with all the same symbol (AAA, BBB). In this situation the game will always be drawn.

      (2) two columns the same (AB, AB) and one the opposite (BA). If player A plays a column that matches the original layout, then player B can play either of this rows, and the remaining columns and row must fit with the original layout, so, again, the game is always drawn.

      (3) if there are two columns the same (AB, AB) and one opposite (BA), and player A plays a column that is the opposite of the original layout, then player B can play either of his rows, but on the next go player A only has the choice of one column and cannot block B, so B will be able to play both rows, but A will not be able to play the final column, giving a win for B. But A goes first, so can choose not to play a column that is the opposite of the original layout, so this situation would not occur.

      For two players playing as well as possible, the game is always drawn.

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: