### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,149)
- misc (2)
- project euler (2)
- puzzle (38)
- site news (44)
- tantalizer (40)
- teaser (3)

### Site Stats

- 175,242 hits

Advertisements

Programming Enigma Puzzles

14 August 2015

Posted by on **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

%d bloggers like this:

[I was having trouble posting my solution to the

PuzzlingInPythonsite, 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).

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.