Enigmatic Code

Programming Enigma Puzzles

Teaser 2773: King Lear III

From The Sunday Times, 15th November 2015 [link]

King Lear III had a square kingdom divided into sixteen equal-sized smaller square plots, numbered in the usual way. He decided to keep a realm for himself and share the rest into equal realms (larger than his) for his daughters, a “realm” being a collection of one or more connected plots. He chose a suitable realm for himself and one for his eldest daughter and he noticed that, in each case, multiplying together [the] plot numbers within the realm gave a perfect square. Then he found that there was only one way to divide the remainder of the kingdom into suitable realms.

What are the plot numbers of the eldest daughter’s realm and of the king’s realm.

The puzzle text on The Sunday Times website, uses “any” where I have placed “[the]”.

[teaser2773]

Advertisements

One response to “Teaser 2773: King Lear III

  1. Jim Randell 15 November 2015 at 11:19 am

    I thought this was quite a good puzzle, involving several steps to arrive at the solution.

    This Python program uses several useful routines from the enigma.py library. It runs in 135ms.

    from itertools import combinations, product
    from collections import defaultdict
    from enigma import irange, multiply, is_square, filter2, diff, first, printf
    
    # consider the grid:
    #
    #  1  2  3  4
    #  5  6  7  8
    #  9 10 11 12
    # 13 14 15 16
    
    # the plot numbers in the grid
    plots = set(irange(1, 16))
    
    # the adjacency matrix
    adj = dict()
    for i in plots:
      (y, x) = divmod(i - 1, 4)
      adj[i] = tuple(j for (g, j) in ((y > 0, i - 4), (x > 0, i - 1), (x < 3, i + 1), (y < 3, i + 4)) if g)
    
    # are the pieces in ps connected to the pieces in cs?
    def is_connected(ps, cs=set()):
      if not ps:
        return True
      elif not cs:
        # move one piece from ps to cs
        ps = set(ps)
        x = ps.pop()
        return is_connected(ps, set([x]))
      else:
        # partition ps into those connected to cs and those that aren't
        (pcs, pns) = filter2((lambda p: cs.intersection(adj[p])), ps)
        return bool(pcs) and is_connected(pns, cs.union(pcs))
    
    # construct t connected pieces of n squares from ps
    def construct(t, n, ps):
      # is there only one piece to construct?
      if t == 1:
        if is_connected(ps):
          yield [ps]
      else:
        # choose n connected pieces from ps
        ps = set(ps)
        x = ps.pop()
        for xs in combinations(ps, n - 1):
          xs = (x,) + xs
          if is_connected(xs):
            for cs in construct(t - 1, n, diff(ps, xs)):
              yield [xs] + cs
    
    # find square numbers that are the product of n connected plots
    # record the connected plots by the square number
    squares = defaultdict(list)
    for n in irange(1, 7):
      for s in combinations(plots, n):
        m = multiply(s)
        r = is_square(m)
        if r is None: continue
        if not is_connected(s): continue
        printf("[n={n}, plots={s}, product={m}, sqrt={r}]")
        squares[n].append(s)
    
    # choose the number of daughters
    for d in irange(2, 7):
      # number of plots per daughter
      for n in irange(2, 16 // d):
        # the remaining plots
        r = 16 - n * d
        if not(0 < r < n): continue
    
        # find regions for the king and the eldest daughter
        printf("[considering daughters={d}, plots={n}, remaining={r} ...]")
        for (K, E) in product(squares[r], squares[n]):
          # they must be disjoint
          if set(K).intersection(E): continue
          # construct connected plots for the rest of the daughters
          # and look for two different ways
          ds = first(construct(d - 1, n, plots.difference(K, E)), 2)
          printf("K={K} E={E} ds={ds}")
    
          # the solution has only one way to construct the remaining regions
          if len(ds) == 1: printf("*** SOLUTION FOUND ***")
    

    Solution: The Eldest daughter gets plots 1, 2, 5, 9 and 10. The King keeps plot 16.

    The division of the kingdom is shown below:

    Teaser 2773

    There are three daughters, who each receive a realm of 5 plots. The King keeps a realm of 1 plot for himself.

    The Eldest daughter’s realm is shaded red, the other two daughter’s realms are shaded blue. The King keeps the plot shaded black.

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: