# 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]

### 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))

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: 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.

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