# Sunday Times Teaser 2759 – King Lear II

*by Nick MacKinnon*

#### Published: 9 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 [1]. 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?

[1] “identically-shaped” here means identical or identical to a mirror image.

As a physicist, I originally took the word ‘identically shaped’ at face value and quickly realised that there was no way for three identically shaped ‘5 square’ pieces to cover the fifteen squares left after the King takes his. So, ignoring one and fifteen, it was easy to decide that the King had five daughters each getting areas of three squares. But this made the second paragraph above redundant as written. Nevertheless, I solved it on this basis, although I realised that if a mirror image of a ‘5 square’ area was allowed then solutions with three daughters would be possible. But I think Jim (below) is right that the easiest way of rescuing this teaser is to allow mirror image areas so I have modified the teaser text above to allow this. I have also updated my solution to solve the teaser on this basis.

Developing a programmed solution for this one is quite a challenge but it is possible using a brilliant algorithm first described by Donald Knuth (known as Dancing Links or Algorithm X) to solve the Exact Cover problem.

The following program uses a Python implementation of the Dancing Links algorithm developed by David Goodger and Ali Assaf, which I make available here. The program could be made a lot faster as it solves for all possible positions of the King’s square when it only needs to consider one corner, one edge and one middle position (remapping the sixteen cell values for four rotations and one reflection would be very fast). But since it runs in less than a second, I decided to be lazy on this occasion.

It provides the solution:

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 work 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).

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.