# Sunday Times Teaser 2838 – King Lear IV

*by Nick MacKinnon*

#### Published: 12 February 2017 (link)

King Lear IV’s realm consisted of a regular hexagon divided into 24 counties that were equal-sized equilateral triangles. In his will he wanted to share the counties among his six daughters, each daughter’s portion having the property that, if you walked in a straight line between any two points in it, then you remained in her portion. If two daughters’ portions had the same area then they had to be of different shapes (and not the mirror image of each other). He wanted Cordelia to have a single county (his favourite county on the edge of the kingdom), he wanted Goneril to have a hexagonal-shaped portion, and he knew the number of counties he wanted to allocate to each of the other daughters, with Reagan’s portion being the largest of all. It turned out that his requirements uniquely determined Goneril’s and Reagan’s counties.

What, in increasing order, were the numbers of counties allocated to the six daughters?

This solution used Donald Knuth’s ‘Dancing Links’ algorithm for the exact cover problem.

I used the Polyform Puzzler framework [ http://puzzler.sourceforge.net/ ] to write a Python program to solve this one.

I copied the convex polyiamonds up to size 7 from the framework, and added the two convex polyiaminds of size 8. We then fit 6 of them with a total size of 24 into the hexagon (with additional constraints that T1 is already placed, O6 must be present, and the largest polyiamond has a size greater than 6).

We then accumulate solutions according to the sizes of the pieces used, and output sizes that lead to a unique packing.

The program runs in 458ms.

Note that the Polyform Puzzler framework works with Python 2, but not Python 3.

I’ve used a variant of the wrapper code I wrote for

Enigma 321[ https://enigmaticcode.wordpress.com/2015/11/27/enigma-321-going-to-pieces/ ] to find the number of solutions using the Polyform Puzzler framework, and also a couple of useful routines from theenigma.pylibrary [ http://www.magwag.plus.com/jim/enigma.html ].Note that really I should be recording the solutions by the numbers of counties (= size of the pieces) and the positions of Goneril’s and Regan’s pieces.

We can achieve this by modifying the solve() routine to return the positions of the pieces (instead of just the number of solutions), and then accumulate the positions of O6 and the largest piece against the size of the pieces.

This doesn’t affect the run time, and the overall answer is the same.