Father's Day Puzzle #3, sort of like a magic square, but not a square.

fathers_day_puzzle3.py

#!/usr/bin/env python
#
# Father's Day card puzzle #3:
# In the figure below, fill in each of the sixteen numbers from 1 to 16 such
# that the four rows and three columns add up to 29.
#
#                      (  )---(  )---(  )
#                       |             |
# (  )---(  )---(  )---(  )          (  )
#         |             |             |
#        (  )          (  )---(  )---(  )---(  )
#         |             |
#        (  )---(  )---(  )
import itertools

__author__ = "David Blume"
__license__ = "MIT"

length = 16
total = 29


def test_outer_cols(a, b, c, d):
    used_numbers = set(itertools.chain(a, b, c, d))
    c1, c2 = [i for i in range(1, length+1) if i not in used_numbers]
    if b[1] + c1 + d[0] == total and a[2] + c2 + c[2] == total:
        print "                  {:>5} {:>5} {:>5}".format(*a)
        print "{:>5} {:>5} {:>5} {:>5}       {:>5}".format(b[0], b[1], b[2], b[3], c2)
        print "      {:>5}       {:>5} {:>5} {:>5} {:>5}".format(c1, c[0], c[1], c[2], c[3])
        print "      {:>5} {:>5} {:>5}".format(*d)
        print
        return True
    if b[1] + c2 + d[0] == total and a[2] + c1 + c[2] == total:
        print "                  {:>5} {:>5} {:>5}".format(*a)
        print "{:>5} {:>5} {:>5} {:>5}       {:>5}".format(b[0], b[1], b[2], b[3], c1)
        print "      {:>5}       {:>5} {:>5} {:>5} {:>5}".format(c2, c[0], c[1], c[2], c[3])
        print "      {:>5} {:>5} {:>5}".format(*d)
        print
        return True
    return False


def test_center_col(a, b, c, d):
    if a[0] + b[3] + c[0] + d[2] == total:
        return test_outer_cols(a, b, c, d)
    if a[2] + b[3] + c[0] + d[0] == total:
        return test_outer_cols(d, b, c, a)
    if a[0] + b[0] + c[3] + d[2] == total:
        return test_outer_cols(a, c, b, d)
    if a[2] + b[0] + c[3] + d[0] == total:
        return test_outer_cols(d, c, b, a)
    return False


def test(ll):
    for a in itertools.permutations(ll[0]):
        for b in itertools.permutations(ll[1]):
            for c in itertools.permutations(ll[2]):
                for d in itertools.permutations(ll[3]):
                    if test_center_col(a, b, c, d):
                        break


if __name__ == '__main__':
    l = range(1, length+1)

    # Break it down into smaller problems. Just work on the four rows first.
    # Make tuples of 3 and 4 items that add up to 29
    t3 = [i for i in itertools.combinations(l, 3) if sum(i) == total]
    t4 = [i for i in itertools.combinations(l, 4) if sum(i) == total]

    # Choose all sets of 2 from t3 and 2 from t4 that have no duplicate numbers
    t14 = []
    for a in t3:
        for b in t4:
            if any(n in b for n in a):
                continue
            for c in t4:
                if any(n in c for n in a):
                    continue
                if any(n in c for n in b):
                    continue
                for d in t3:
                    if any(n in d for n in a):
                        continue
                    if any(n in d for n in b):
                        continue
                    if any(n in d for n in c):
                        continue
                    t14.append((a,b,c,d))

    # See if the columns add up
    for i in t14:
        test(i)