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.

2 Comments Leave one →

Brian Gladman permalink

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.


# Since there are 15 squares shared equally among the daughters,  there
# are either 3 or 5 daughters (ignoring 1 and 15). The daughter's areas
# are three or five small squares,  with the three squares in an I or L
# shape and the '5 square' areas being 4 squares in a 2 by 2 array with
# an adjacent  single square.   But identically shaped '5 square' areas
# cannot be arranged to cover the 15 squares left after the King claims
# a square. But if a mirror image (chiral) version of the '5 square' is
# allowed, then the remaining area can be covered. It seems likely that
# this was the  intent although it stetches the meaning of 'identically
# shaped' areas.

from collections import defaultdict
from itertools import product
# import an implementation of Donald Knuth's Danncing Links algorithm
# by David Goodger and Ali Assaf  (licensed under GPL v2)
from exact_cover_x2 import ExactCover

# return true if the x is a perfect square
def is_square(x):
  return int(x ** 0.5 + 0.5) ** 2 == x

# find possible layouts of the daughter's areas using
# the Exact Cover algorithm 
def solve_square(pieces, m, n):
  
  # a two dimensional matrix
  mat = []
  # row 0 holds strings of the names of the pieces followed
  # by names for each point in the space being covered
  lp, ln = list(pieces), len(pieces)
  for x, y in product(range(m), range(n)):
    lp.append(str(x + m * y + 1))
  mat.append(lp)

  # for each piece
  for p in pieces:
    # for each x and y position that the piece can occupy
    for y, x in product(range(-3, n + 3), range(-3, m + 3)):
      # for each orientation of the piece
      for sh in pieces[p]:
        # check it is within the square 
        if all(0 <= x + v < m and 0 <= y + w < n for v, w in sh):
          l = [0] * (ln + m * n)
          # set the piece
          l[lp.index(p)] = 1
          # and the cells it occupies in this position and orientation
          for v, w in sh:
            l[len(pieces) + (x + v) + m * (y + w)] = 1
          mat.append(l)
  # return solutions
  ec = ExactCover(mat)
  for s in ec.solve():
    yield s

# find solutions for a specific shape of the daughter's areas
def solve_pos(pieces):
  m, n = 4, 4 
  sol = set()
  for s in solve_square(pieces, m, n):
    # extract the numbers of each of the five daughter's squares
    d = tuple(sorted(tuple(sorted(int(y) for y in x[:-1])) 
                     for x in s if len(x) > 2))
    k = tuple(sorted(tuple(sorted(int(y) for y in x[:-1])) 
                     for x in s if len(x) == 2))[0][0]
    # sum the three numbers for each daughter
    u = tuple(sum(int(x) for x in y) for y in d)
    # add the solution to the set of solutions:
    # (King's square, daughter's sum list, list of daughter's square lists)
    sol.update([(k, u, d)])
  # return all the solutions
  return frozenset(sol)

# the coordinates covered by a single square
sh_s =  ( ((0, 0),), )
# the coordinates covered by 3 squares in a line in two orientations
sh_i =  ( ((0, 0), (0, 1), (0, 2)), ((0, 0), (1, 0), (2, 0)) )
# the coordinates covered by 3 squares in an L shape in four orientations
sh_l =  ( ((0, 0), (0, 1), (1, 0)), ((0, 0), (0, 1), (1, 1)),
          ((1, 0), (0, 1), (1, 1)), ((0, 0), (1, 0), (1, 1)) )
# the coordinates covered by an XXX shape in four orientations
#                               XX
sh_a =  ( ((0, 0), (0, 1), (0, 2), (1, 0), (1, 1)),
          ((0, 0), (0, 1), (1, 0), (1, 1), (2, 1)),
          ((0, 1), (0, 2), (1, 0), (1, 1), (1, 2)),
          ((0, 0), (1, 0), (1, 1), (2, 0), (2, 1)) )
# the coordinates covered by an XX  (chiral) shape in four orientations
#                               XXX
sh_c =  ( ((0, 0), (0, 1), (1, 0), (1, 1), (2, 1)),
          ((0, 0), (0, 1), (1, 0), (1, 1), (2, 0)),
          ((0, 0), (0, 1), (0, 2), (1, 1), (1, 2)),
          ((0, 1), (1, 0), (1, 1), (2, 0), (2, 1)) )

# 5 daughters with I shaped areas
cfg1 = {'A':sh_s, 'B':sh_i, 'C':sh_i, 'D':sh_i, 'E':sh_i, 'F':sh_i }
# 5 daughters with L shaped areas
cfg2 = {'A':sh_s, 'B':sh_l, 'C':sh_l, 'D':sh_l, 'E':sh_l, 'F':sh_l }
# 3 daughters with '5 square'  areas (2 normal + 1 chiral or vice versa)
cfg3 = {'A':sh_s, 'B':sh_a, 'C':sh_a, 'D':sh_c }
cfg4 = {'A':sh_s, 'B':sh_a, 'C':sh_c, 'D':sh_c }

# collect the solutions in three dictionaries for the King
# occupying corner, middle and edge positions repectively 
c_d = [defaultdict(list), defaultdict(list), defaultdict(list)]
for cfg in (cfg1, cfg2, cfg3, cfg4):
  # Kings square, daughter's sums, daughter's square lists
  for k, l_sum, l_sq in solve_pos(cfg):
    # find which dictionary from the King's square type
    ix = 0 if k in (1, 4, 13, 16) else (1 if k in (6, 7, 10, 11) else 2)
    # index on King's square type and then on the number of daughters 
    c_d[ix][len(l_sq)] += [(k, l_sum, l_sq)]

ps2kc = defaultdict(list)
# consider Kings square types for which the number of daughters is unique
for d in [x for x in c_d if len(x) == 1]:
  # extract (Kings square, daughter's sums, daughter's square lists)  
  for di in d.values():
    for k, l_sum, l_sq in di:
      # look for daughter's sums that are perfect squares
      for sm in l_sum:
        if is_square(sm):
          # and store the King's and Cordelia's square numbers 
          ps2kc[sm] += [(k, l_sq[l_sum.index(sm)])]

for l_sol in ps2kc.values():
  # look for perfect squares giving unique values for the King and Cordelia
  if len(l_sol) == 1:
    k = l_sol[0][0]
    s = (' and '.join(str(x) for x in l_sol[0][1])).replace(' and ', ', ', 1)
    print('King Lear keeps square {}, Cordelia's squares are {}'.format(k, s))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

# Since there are 15 squares shared equally among the daughters, there

# are either 3 or 5 daughters (ignoring 1 and 15). The daughter's areas

# are three or five small squares, with the three squares in an I or L

# shape and the '5 square' areas being 4 squares in a 2 by 2 array with

# an adjacent single square. But identically shaped '5 square' areas

# cannot be arranged to cover the 15 squares left after the King claims

# a square. But if a mirror image (chiral) version of the '5 square' is

# allowed, then the remaining area can be covered. It seems likely that

# this was the intent although it stetches the meaning of 'identically

# shaped' areas.

from collections import defaultdict

from itertools import product

# import an implementation of Donald Knuth's Danncing Links algorithm

# by David Goodger and Ali Assaf (licensed under GPL v2)

from exact_cover_x2 import ExactCover

# return true if the x is a perfect square

def is_square(x):

return int(x ** 0.5 + 0.5) ** 2 == x

# find possible layouts of the daughter's areas using

# the Exact Cover algorithm

def solve_square(pieces, m, n):

# a two dimensional matrix

mat = []

# row 0 holds strings of the names of the pieces followed

# by names for each point in the space being covered

lp, ln = list(pieces), len(pieces)

for x, y in product(range(m), range(n)):

lp.append(str(x + m * y + 1))

mat.append(lp)

# for each piece

for p in pieces:

# for each x and y position that the piece can occupy

for y, x in product(range(-3, n + 3), range(-3, m + 3)):

# for each orientation of the piece

for sh in pieces[p]:

# check it is within the square

if all(0 <= x + v < m and 0 <= y + w < n for v, w in sh):

l = [0] * (ln + m * n)

# set the piece

l[lp.index(p)] = 1

# and the cells it occupies in this position and orientation

for v, w in sh:

l[len(pieces) + (x + v) + m * (y + w)] = 1

mat.append(l)

# return solutions

ec = ExactCover(mat)

for s in ec.solve():

yield s

# find solutions for a specific shape of the daughter's areas

def solve_pos(pieces):

m, n = 4, 4

sol = set()

for s in solve_square(pieces, m, n):

# extract the numbers of each of the five daughter's squares

d = tuple(sorted(tuple(sorted(int(y) for y in x[:-1]))

for x in s if len(x) > 2))

k = tuple(sorted(tuple(sorted(int(y) for y in x[:-1]))

for x in s if len(x) == 2))[0][0]

# sum the three numbers for each daughter

u = tuple(sum(int(x) for x in y) for y in d)

# add the solution to the set of solutions:

# (King's square, daughter's sum list, list of daughter's square lists)

sol.update([(k, u, d)])

# return all the solutions

return frozenset(sol)

# the coordinates covered by a single square

sh_s = ( ((0, 0),), )

# the coordinates covered by 3 squares in a line in two orientations

sh_i = ( ((0, 0), (0, 1), (0, 2)), ((0, 0), (1, 0), (2, 0)) )

# the coordinates covered by 3 squares in an L shape in four orientations

sh_l = ( ((0, 0), (0, 1), (1, 0)), ((0, 0), (0, 1), (1, 1)),

((1, 0), (0, 1), (1, 1)), ((0, 0), (1, 0), (1, 1)) )

# the coordinates covered by an XXX shape in four orientations

# XX

sh_a = ( ((0, 0), (0, 1), (0, 2), (1, 0), (1, 1)),

((0, 0), (0, 1), (1, 0), (1, 1), (2, 1)),

((0, 1), (0, 2), (1, 0), (1, 1), (1, 2)),

((0, 0), (1, 0), (1, 1), (2, 0), (2, 1)) )

# the coordinates covered by an XX (chiral) shape in four orientations

# XXX

sh_c = ( ((0, 0), (0, 1), (1, 0), (1, 1), (2, 1)),

((0, 0), (0, 1), (1, 0), (1, 1), (2, 0)),

((0, 0), (0, 1), (0, 2), (1, 1), (1, 2)),

((0, 1), (1, 0), (1, 1), (2, 0), (2, 1)) )

# 5 daughters with I shaped areas

cfg1 = {'A':sh_s, 'B':sh_i, 'C':sh_i, 'D':sh_i, 'E':sh_i, 'F':sh_i }

# 5 daughters with L shaped areas

cfg2 = {'A':sh_s, 'B':sh_l, 'C':sh_l, 'D':sh_l, 'E':sh_l, 'F':sh_l }

# 3 daughters with '5 square' areas (2 normal + 1 chiral or vice versa)

cfg3 = {'A':sh_s, 'B':sh_a, 'C':sh_a, 'D':sh_c }

cfg4 = {'A':sh_s, 'B':sh_a, 'C':sh_c, 'D':sh_c }

# collect the solutions in three dictionaries for the King

# occupying corner, middle and edge positions repectively

c_d = [defaultdict(list), defaultdict(list), defaultdict(list)]

for cfg in (cfg1, cfg2, cfg3, cfg4):

# Kings square, daughter's sums, daughter's square lists

for k, l_sum, l_sq in solve_pos(cfg):

# find which dictionary from the King's square type

ix = 0 if k in (1, 4, 13, 16) else (1 if k in (6, 7, 10, 11) else 2)

# index on King's square type and then on the number of daughters

c_d[ix][len(l_sq)] += [(k, l_sum, l_sq)]

ps2kc = defaultdict(list)

# consider Kings square types for which the number of daughters is unique

for d in [x for x in c_d if len(x) == 1]:

# extract (Kings square, daughter's sums, daughter's square lists)

for di in d.values():

for k, l_sum, l_sq in di:

# look for daughter's sums that are perfect squares

for sm in l_sum:

if is_square(sm):

# and store the King's and Cordelia's square numbers

ps2kc[sm] += [(k, l_sq[l_sum.index(sm)])]

for l_sol in ps2kc.values():

# look for perfect squares giving unique values for the King and Cordelia

if len(l_sol) == 1:

k = l_sol[0][0]

s = (' and '.join(str(x) for x in l_sol[0][1])).replace(' and ', ', ', 1)

print('King Lear keeps square {}, Cordelia's squares are {}'.format(k, s))

It provides the solution:

01 02 03 04 King

05 06 07 08 Cordelia

09 10 11 12

13 14 15 16

Jim Randell permalink

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


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():
    d = 15 // n
    for s in ss:
      printf("[checking: king = {k}, area = {n}, daughters = {d}, shape = {s}]")
 
      # 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])

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

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():

d = 15 // n

for s in ss:

printf("[checking: king = {k}, area = {n}, daughters = {d}, shape = {s}]")

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

Sunday Times Teaser 2759 – King Lear II

by Nick MacKinnon

Published: 9 August 2015 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta