Enigmatic Code

Programming Enigma Puzzles

Teaser 2759: King Lear II

From The Sunday Times, 9th August 2015 [link]

King Lear II had a square kingdom divided into 16 equal smaller squares. He kept one square and divided the rest equally among his daughters, giving each one an identically-shaped connected piece. If you knew whether Lear kept a corner square, an edge square or a middle square, then you could work out how many daughters he had.

The squares were numbered 1 to 16 in the usual way. The numbers of Cordelia’s squares added up to a perfect square. If you now knew that total you could work out the number of Lear’s square.

What number square did Lear keep for himself and what were the numbers of Cordelia’s squares?

[teaser2759]

Advertisements

One response to “Teaser 2759: King Lear II

  1. Jim Randell 14 August 2015 at 8:28 am

    [I was having trouble posting my solution to the PuzzlingInPython site, so I’ve put it up here].

    This is quite a convoluted puzzle – like two standard puzzles plugged together. Here’s my solution:

    The King gives 15 squares to his daughters. The number of daughters is uniquely determined by the class of square (corner, edge, interior) that the King keeps for himself.

    First there are a couple of clarifications that need to be made for us to be able to find a solution.

    We reject the possibility that the King could have 1 or 15 daughters, as the King could clearly keep any of the squares for himself and still be able to tile the remaining 15 squares with either 15 1-ominoes or 1 15-omino, and we wouldn’t be able to tell which of these situations arose. So we will suppose the use of “daughters” and “the number of Cordelia’s squares” implies that the King has more than 1 daughter and to each of his daughter he gives a piece of land composed of more than 1 square.

    So, the King must have 3 or 5 daughters. And he gives each daughter a piece of land composed of either 5 or 3 squares (respectively).

    We are looking at tiling a 4×4 grid with either similar 3-ominoes (trominoes – https://en.wikipedia.org/wiki/Tromino – of which there are 2 types) or similar 5-ominoes (pentominoes – https://en.wikipedia.org/wiki/Pentomino – of which there are 12 types, although only 11 of them will fit into a 4×4 grid). (I considered writing code to generate the possible n-ominoes, but I think there’s already enough programming in this puzzle as it is).

    Next we have to suppose that we allow the shapes of the pieces of land to be rotations or mirror images of each other when we consider the “identically-shaped” pieces. Otherwise it is not possible to fit 3 pentominoes into a 4×4 grid, and so we would know that the King must have 5 daughters (each receiving a tronimo shaped piece of land) without needing to know the class of the square that the king kept for himself. [*]

    The following Python 3 program looks at possible ways to tile the 4×4 grid using tronimoes and pentominoes, and collects the results to find possible classes for the King’s square. Ambiguous classes are removed, giving the number of daughters and area of their pieces of land.

    It then examines grids with each of the squares of the identified classes removed and produces tilings of the appropriate shape where one of the shapes has a total value that is a square number. These are then examined to find a total value that implies a unique solution for the King’s square.

    It runs in 352ms.

    (Note that the numbers used in (and output by) the program to label the squares are 0-based, not 1-based as in the puzzle text).

    from collections import defaultdict
    from enigma import irange, diff, is_square, printf
    
    # label the small squares
    # (you need to add 1 to get the numbering referred to in the question)
    squares = set(irange(0, 15))
    
    # rotation
    r90 = [3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12] # 90 degrees
    
    # reflection
    rv = [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12] # reflection about a vertical axis
    
    # translations (<empty squares>, <transformation>)
    tl = (set([0, 4, 8, 12]), [None, 0, 1, 2, None, 4, 5, 6, None, 8, 9, 10, None, 12, 13, 14]) # left
    tr = (set([3, 7, 11, 15]), [1, 2, 3, None, 5, 6, 7, None, 9, 10, 11, None, 13, 14, 15, None]) # right
    tu = (set([0, 1, 2, 3]), [None, None, None, None, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]) # up
    td = (set([12, 13, 14, 15]), [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, None, None, None, None]) # down
    
    # apply a transformation <t> to a shape <s>
    def transform(s, t):
      return tuple(sorted(t[i] for i in s))
    
    # move the shape to the TL corner (using tl and tu translations)
    def top_left(shape):
      for (empty, t) in (tl, tu):
        while not empty.intersection(shape):
          shape = transform(shape, t)
      return shape
    
    # generate translations of the shape (using tr and td)
    def translations(shape):
      while True:
        s = shape
        (empty, t) = tr
        while True:
          yield s
          if empty.intersection(s): break
          s = transform(s, t)
        (empty, t) = td
        if empty.intersection(shape): break
        shape = transform(shape, t)
    
    # generate possible placements of a shape (removing duplicates as we go)
    def placements(shape):
      seen = dict()
      # shape and reflection
      for s in (shape, transform(shape, rv)):
        if s in seen: continue
        # rotations
        for _ in (0, 1, 2, 3):
          # translations
          for x in translations(top_left(s)):
            if x in seen: continue
            yield x
            seen[x] = 1
          # then rotate the shape
          s = transform(s, r90)
    
    # fit the shapes into the required squares
    # sqs - available squares (as a set)
    # ss - shapes used
    # ps - possible placements
    def tile(sqs, ss, ps):
      # are we done?
      if not sqs:
        yield ss
      else:
        for p in ps:
          if sqs.issuperset(p):
            yield from tile(sqs.difference(p), ss + [p], ps)
    
    # possible shapes (by area)
    shapes = {
      # "tronimos" (2)
      3: [(0, 1, 2), (0, 1, 4)],
      # "pentominos" (11)  
      5: [(0, 1, 2, 3, 4), (0, 1, 2, 4, 5), (0, 1, 5, 6, 9), (0, 1, 2, 6, 7), (0, 1, 2, 5, 9), (0, 1, 2, 4, 6), (0, 1, 2, 4, 8), (1, 2, 4, 5, 8), (1, 4, 5, 6, 9), (0, 1, 2, 3, 5), (0, 1, 5, 9, 10)],
    }
    
    # partition the squares into (c)orner, (e)dge, (i)nterior
    square_types = {
      'c': (0, 3, 12, 15),
      'e': (1, 2, 4, 7, 8, 11, 13, 14),
      'i': (5, 6, 9, 10),
    }
    
    # record: <king's square type> -> <area> -> <shape>
    r1 = defaultdict(lambda: defaultdict(list))
    
    # consider each possible area n and the corresponding n-ominoes
    for (n, ss) in shapes.items():
    
      # for each n-omino
      for shape in ss:
    
        # possible positions
        ps = list(placements(shape))
    
        # try to tile the large square without a corner, an edge or an interior square
        for (k, v) in square_types.items():
    
          # we only need to find one possible tiling for one of the squares
          for t in tile(squares.difference([v[0]]), [], ps):
            r1[k][n].append(shape)
            printf("[king = {k}, n = {n}, shape = {shape}, tiling = {t}]")
            break
    
    # record <cordelia's total> -> <king's square> -> <tiling>
    r2 = defaultdict(lambda: defaultdict(list))
    
    # examine the possibilities
    for (k, vs) in r1.items():
      # there must be a unique area
      if len(vs) != 1: continue
      # consider the possible shapes
      for (n, ss) in vs.items():
        for s in ss:
          printf("[checking: king = {k}, area = {n}, daughters = {d}, shape = {s}]", d = 15 // n)
    
          # possible positions
          ps = list(placements(s))
    
          # look for positions that sum to a square
          for p in ps:
            v = sum(p) + len(p) # shift from 0-based to 1-based
            if not is_square(v): continue
    
            # attempt to tile the remaining squares
            # (we only need to find a single tiling)
            for kv in square_types[k]:
              for t in tile(squares.difference(p + (kv,)), [], ps):
                r2[v][kv].append([p] + t)
                printf("[cordelia's value = {v}, position = {p}, king's square = {kv}, tiling = {t}]")
                break
    
    # examine the possibilities
    for (v, vs) in r2.items():
      # there must be a unique possibility for the king's choice
      if len(vs) != 1: continue
      for (k, ts) in vs.items():
        printf("cordelia's value = {v}, king's square = {k}, tiling = {t}", t=ts[0])
    

    Solution: The King kept square 5 for himself. Cordelia’s squares were numbers 1, 2, and 6.

    Teaser 2759 - Solution

    [*] Also, if we don’t allow reflections then we can’t eliminate the possibility that the King keeps a corner square for himself. In this scenario the remaining squares can be tiled using I tronimoes. So Cordelia’s value of 9 could be made up of squares (2, 3, 4), and the King can take square 1, 13 or 16. So there is no unique solution unless reflections are allowed.

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: