Enigmatic Code

Programming Enigma Puzzles

Enigma 1572: Just magic

From New Scientist #2735, 21st November 2009 [link]

Joe has been showing Penny how to calculate the numbers in a 3-by-3 magic square. Each row, column and main diagonal have the same totals. Above is Penny’s first effort. But she thought it would make a good puzzle if all but one number were in the wrong position.

Which number is in its correct position?

[enigma1572]

Advertisements

One response to “Enigma 1572: Just magic

  1. jimrandell 14 February 2012 at 1:59 pm

    The following Python program runs in 40ms.

    from itertools import combinations
    from collections import defaultdict
    from enigma import printf
    
    # the numbers mapped to how many sums they appear in (centre = 4, corner = 3, edge = 2)
    numbers = { 66: 3, 49: 2, 20: 3, 37: 2, 44: 4, 61: 2, 78: 3, 32: 2, 54: 3 }
    
    def solve(numbers):
      # group the combinations by their sum
      sums = defaultdict(list)
      for l in combinations(numbers.keys(), 3):
        sums[sum(l)].append(l)
    
      # find sums that have at least 8 ways to make it
      for s in sorted(sums.keys()):
        l = len(sums[s])
        if l < 8: continue
        # and consider groups of 8 combinations
        for ss in combinations(sums[s], 8):
          check(ss)
    
    # check the 8 sums form a magic square
    def check(s):
      # count the number of times each number is used
      count = defaultdict(int)
      for l in s:
        for n in l:
          count[n] += 1
    
      # each number needs to occur the right number of times
      if not(sorted(count.values()) == [2, 2, 2, 2, 3, 3, 3, 3, 4]): return
    
      # find which numbers are used the same number of times in the original square
      for n in count.keys():
        if numbers[n] == count[n]:
          printf("{n} is in the correct position")
    
    solve(numbers)
    

    Solution: The number 66 is in the correct position.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: