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

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

[*] 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.

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