Sunday Times Teaser 2821 – Magic Cards

by Andrew Skidmore

Published: 16 October 2016 (link)

Joe placed nine cards on the table to form the magic square shown on the left below (where each row, column and diagonal has the same total). Then he turned over each card one at a time and the result is shown on the right below: it is not magic.

__________	4	11	9	__________	7	4	8
	13	8	3		3	6	9
	7	5	12		2	14	1

Penny then rearranged the cards to form a magic square which, after each card was turned over, was also magic.

What (in increasing order) were the four corner numbers in her magic square with the higher total?

2 Comments Leave one →

Brian Gladman permalink

There are far faster ways of checking whether a 3 by 3 grid of numbers forms a magic square than the approach I have used here but this gets the job done in less than a second.


from itertools import product, permutations

# the numbers on each side of the nine cards
cards = ( ( 4, 7), (11,  4), ( 9, 8), 
          (13, 3), ( 8,  6), ( 3, 9), 
          ( 7, 2), ( 5, 14), (12, 1) )

# try all combinations of cards both ways up
for t9 in product((False, True), repeat=9):
  cp = tuple(x if v else tuple(reversed(x)) for x, v in zip(cards, t9))
  
  # now list the nine 'top' and 'bottom' numbers and their sums
  c0, c1 = (tuple(x[i] for x in cp) for i in (0, 1))
  (e0, r0), (e1, r1) = divmod(sum(c0), 9), divmod(sum(c1), 9)

  # ensure that they have the right forms for magic squares  
  if (e0 >= e1 and r0 == r1 == 0 
        and c0[4] == e0 and c1[4] == e1 and len(set(c0)) == len(set(c1)) == 9):

    # now try and form the two magic squares by rearranging the nine cards
    for a, b, c, d, e, f, g, h, i in permutations(cp):
      
      # form the row, column and diagonal sums for the top and bottom 
      # of the cards and check that they are all the same for both sides
      if all(len(set((
              a[k] + b[k] + c[k], d[k] + e[k] + f[k], g[k] + h[k] + i[k],
              a[k] + d[k] + g[k], b[k] + e[k] + h[k], c[k] + f[k] + i[k],
              a[k] + e[k] + i[k], c[k] + e[k] + g[k]))) == 1 for k in (0, 1)):
        
        # print the corner square values for the magic square
        # with the higher sum
        fs = 'The corner squares are {}, example card layout:\n'
        print(fs.format(sorted((a[0], c[0], g[0], i[0]))))
        
        # print the numbers on the tops and bottoms of the cards
        # for an example card arrangement
        print('\n'.join([' '.join('{:2}'.format(x) for k in (0, 1) 
                      for x in ('   ', u[k], v[k], w[k]))
              for u, v, w in ((a, b, c), (d, e, f), (g, h, i))]))
        break

from itertools import product, permutations

# the numbers on each side of the nine cards

cards = ( ( 4, 7), (11, 4), ( 9, 8),

(13, 3), ( 8, 6), ( 3, 9),

( 7, 2), ( 5, 14), (12, 1) )

# try all combinations of cards both ways up

for t9 in product((False, True), repeat=9):

cp = tuple(x if v else tuple(reversed(x)) for x, v in zip(cards, t9))

# now list the nine 'top' and 'bottom' numbers and their sums

c0, c1 = (tuple(x[i] for x in cp) for i in (0, 1))

(e0, r0), (e1, r1) = divmod(sum(c0), 9), divmod(sum(c1), 9)

# ensure that they have the right forms for magic squares

if (e0 >= e1 and r0 == r1 == 0

and c0[4] == e0 and c1[4] == e1 and len(set(c0)) == len(set(c1)) == 9):

# now try and form the two magic squares by rearranging the nine cards

for a, b, c, d, e, f, g, h, i in permutations(cp):

# form the row, column and diagonal sums for the top and bottom

# of the cards and check that they are all the same for both sides

if all(len(set((

a[k] + b[k] + c[k], d[k] + e[k] + f[k], g[k] + h[k] + i[k],

a[k] + d[k] + g[k], b[k] + e[k] + h[k], c[k] + f[k] + i[k],

a[k] + e[k] + i[k], c[k] + e[k] + g[k]))) == 1 for k in (0, 1)):

# print the corner square values for the magic square

# with the higher sum

fs = 'The corner squares are {}, example card layout:\n'

print(fs.format(sorted((a[0], c[0], g[0], i[0]))))

# print the numbers on the tops and bottoms of the cards

# for an example card arrangement

print('\n'.join([' '.join('{:2}'.format(x) for k in (0, 1)

for x in (' ', u[k], v[k], w[k]))

for u, v, w in ((a, b, c), (d, e, f), (g, h, i))]))

break

Here is a much faster version:


from itertools import combinations, permutations, product
from collections import defaultdict

# the numbers on each side of the nine cards
cards = set((min(c), max(c)) for c in   
          ( ( 4, 7), (11,  4), ( 9, 8), 
            (13, 3), ( 8,  6), ( 3, 9), 
            ( 7, 2), ( 5, 14), (12, 1) ))

# list all the numbers present and list all duplicates 
nbrs = sum(([x, y] for x, y in cards), [])
dups = [x for x in nbrs if nbrs.count(x) > 1]

# If the row/column/diagonal sum is 3.e and x and y
# are integers such that 1 < x < y with y != 2 * x,
# then this 3 x 3 number grid forms a magic square:
#
#    e - x    e + x + y    e - y
#  e + x - y      e      e - x + y 
#    e + y    e - x - y    e + x

# generate a magic square from the centre value and 
# those at the start and the end of the first row
def magic(e, a, c):
  x, y = e - a, e - c
  return ( e - x, e + x + y, e - y,
           e + x - y, e, e - x + y,
           e + y, e - x - y, e + x )

# find the central card and its two values
q = sum(nbrs) // 9
el, eh = sorted([x for x in cards if sum(x) == q][0])

# create sets of valid magic squares for the two centre values
sml, smh = set(), set()
for e in (el, eh):
  # choose values for the first and last positions in the first row
  for a, c in combinations(nbrs, 2):
    # create the resulting magic square
    m = magic(e, a, c)
    # check that it contains all duplicated values and that all
    # its values are possible
    if all(x in m for x in dups) and all(x in nbrs for x in m):
      (sml if e == el else smh).add(m)

# consider pairs of magic squares for the top and bottom of the cards
for mh, ml in product(smh, sml):
  # and look for a pair of magic squares with the given card values
  if set(((min(x, y), max(x, y)) for x, y in zip(mh, ml))) == cards:

    # output the corner values for the magic square with the higher sum
    fs = 'The corner values are {}, {}, {} and {}, example card layout:\n'
    print(fs.format(*sorted(mh[i] for i in (0, 2, 6, 8))))
    
    # output top and bottom values on the cards for an example magic square
    print('\n'.join([' '.join('{:2}'.format(x) for m in (mh, ml) 
                for x in ('   ', m[i], m[j], m[k]))
                    for i, j, k in ((0, 1, 2), (3, 4, 5), (6, 7, 8))]))
    break

from itertools import combinations, permutations, product

from collections import defaultdict

# the numbers on each side of the nine cards

cards = set((min(c), max(c)) for c in

( ( 4, 7), (11, 4), ( 9, 8),

(13, 3), ( 8, 6), ( 3, 9),

( 7, 2), ( 5, 14), (12, 1) ))

# list all the numbers present and list all duplicates

nbrs = sum(([x, y] for x, y in cards), [])

dups = [x for x in nbrs if nbrs.count(x) > 1]

# If the row/column/diagonal sum is 3.e and x and y

# are integers such that 1 < x < y with y != 2 * x,

# then this 3 x 3 number grid forms a magic square:

# e - x e + x + y e - y

# e + x - y e e - x + y

# e + y e - x - y e + x

# generate a magic square from the centre value and

# those at the start and the end of the first row

def magic(e, a, c):

x, y = e - a, e - c

return ( e - x, e + x + y, e - y,

e + x - y, e, e - x + y,

e + y, e - x - y, e + x )

# find the central card and its two values

q = sum(nbrs) // 9

el, eh = sorted([x for x in cards if sum(x) == q][0])

# create sets of valid magic squares for the two centre values

sml, smh = set(), set()

for e in (el, eh):

# choose values for the first and last positions in the first row

for a, c in combinations(nbrs, 2):

# create the resulting magic square

m = magic(e, a, c)

# check that it contains all duplicated values and that all

# its values are possible

if all(x in m for x in dups) and all(x in nbrs for x in m):

(sml if e == el else smh).add(m)

# consider pairs of magic squares for the top and bottom of the cards

for mh, ml in product(smh, sml):

# and look for a pair of magic squares with the given card values

if set(((min(x, y), max(x, y)) for x, y in zip(mh, ml))) == cards:

# output the corner values for the magic square with the higher sum

fs = 'The corner values are {}, {}, {} and {}, example card layout:\n'

print(fs.format(*sorted(mh[i] for i in (0, 2, 6, 8))))

# output top and bottom values on the cards for an example magic square

print('\n'.join([' '.join('{:2}'.format(x) for m in (mh, ml)

for x in (' ', m[i], m[j], m[k]))

for i, j, k in ((0, 1, 2), (3, 4, 5), (6, 7, 8))]))

break

Jim Randell permalink

Here’s my programmed solution. It runs in 43ms.


from itertools import permutations, product
from enigma import diff, printf

#
# the general form of a magic square is:
#
#  x y       | x z z | x y y z
#  ----------+-------+--------
#  x y y z z | x y z | x
#  ----------+-------+--------
#  x z       | x y y | x y z z
#
# each row, column, diagonal combines to give (x x x y y y z z z) = the magic constant

# make an additive magic square (a b c d e f g h i) given (a e f)
def magic(a, e, f):
  (x, y, z) = (f, a - f, e - a)
  return (
    x + y, x + z + z, x + y + y + z,
    x + y + y + z + z, x + y + z, x,
    x + z, x + y + y, x + y + z + z,
  )

# arrange the cards as:
#
#   a1 b1 c1    a2 b2 c2
#   d1 e1 f1    d2 e2 f2
#   g1 h1 i1    g2 h2 i2

# the cards are all different, so can stand for themselves
# here we list them in canonical sorted order
cards = [
  (1, 12),
  (2, 7),
  (3, 9),
  (3, 13),
  (4, 7),
  (4, 11),
  (5, 14),
  (6, 8),
  (8, 9),
]

# total of all the numbers on the cards
t = sum(a + b for (a, b) in cards)

# so the centre card must have a sum of...
(x, r) = divmod(t, 9)
assert r == 0

# find a card with the right sum for the e's
for e in cards:
  if sum(e) != x: continue

  # the magic constants for each square (largest first)
  (e1, e2) = sorted(e, reverse=True)
  (t1, t2) = (3 * e1, 3 * e2)

  # choose cards for the a's and the f's
  for (a, f) in permutations(diff(cards, [e]), 2):
    for ((a1, a2), (f1, f2)) in product(permutations(a), permutations(f)):
      # and generate the squares
      s1 = magic(a1, e1, f1)
      # for uniqueness require (a < c, g, i) and (b < d) on square 1
      if not all(s1[x] < s1[y] for (x, y) in ((0, 2), (0, 6), (0, 8), (1, 3))):
        continue
      s2 = magic(a2, e2, f2)
      # and the corresponding cards
      cs = sorted((min(x, y), max(x, y)) for (x, y) in zip(s1, s2))
      if cs != cards: continue
      # collect the corners
      corners = sorted(s1[x] for x in (0, 2, 6, 8))
      printf("corners={corners}, s1={s1}, s2={s2}")

from itertools import permutations, product

from enigma import diff, printf

# the general form of a magic square is:

# x y | x z z | x y y z

# ----------+-------+--------

# x y y z z | x y z | x

# ----------+-------+--------

# x z | x y y | x y z z

# each row, column, diagonal combines to give (x x x y y y z z z) = the magic constant

# make an additive magic square (a b c d e f g h i) given (a e f)

def magic(a, e, f):

(x, y, z) = (f, a - f, e - a)

return (

x + y, x + z + z, x + y + y + z,

x + y + y + z + z, x + y + z, x,

x + z, x + y + y, x + y + z + z,

)

# arrange the cards as:

# a1 b1 c1 a2 b2 c2

# d1 e1 f1 d2 e2 f2

# g1 h1 i1 g2 h2 i2

# the cards are all different, so can stand for themselves

# here we list them in canonical sorted order

cards = [

(1, 12),

(2, 7),

(3, 9),

(3, 13),

(4, 7),

(4, 11),

(5, 14),

(6, 8),

(8, 9),

]

# total of all the numbers on the cards

t = sum(a + b for (a, b) in cards)

# so the centre card must have a sum of...

(x, r) = divmod(t, 9)

assert r == 0

# find a card with the right sum for the e's

for e in cards:

if sum(e) != x: continue

# the magic constants for each square (largest first)

(e1, e2) = sorted(e, reverse=True)

(t1, t2) = (3 * e1, 3 * e2)

# choose cards for the a's and the f's

for (a, f) in permutations(diff(cards, [e]), 2):

for ((a1, a2), (f1, f2)) in product(permutations(a), permutations(f)):

# and generate the squares

s1 = magic(a1, e1, f1)

# for uniqueness require (a < c, g, i) and (b < d) on square 1

if not all(s1[x] < s1[y] for (x, y) in ((0, 2), (0, 6), (0, 8), (1, 3))):

continue

s2 = magic(a2, e2, f2)

# and the corresponding cards

cs = sorted((min(x, y), max(x, y)) for (x, y) in zip(s1, s2))

if cs != cards: continue

# collect the corners

corners = sorted(s1[x] for x in (0, 2, 6, 8))

printf("corners={corners}, s1={s1}, s2={s2}")

It uses a couple of utility routines from the enigma.py library – available at [ https://www.magwag.plus.com/jim/enigma.html ].

Sunday Times Teaser 2821 – Magic Cards

by Andrew Skidmore

Published: 16 October 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta