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.
#
#                      (  )---(  )---(  )
#                       |             |
# (  )---(  )---(  )---(  )          (  )
#         |             |             |
#        (  )          (  )---(  )---(  )---(  )
#         |             |
#        (  )---(  )---(  )
#
# This is take three. This version is four times faster than take two.
import itertools

__author__ = "David Blume"
__license__ = "MIT"

length = 16
total = 29


def test_outer_cols(a, b, c, d):
    """We've already assured the four rows add up, and that the middle column
    adds up. Now let's find the two values not yet used, and see if the two
    outer columns add up too. If they do, we found a solution."""
    used_numbers = set(itertools.chain(a, b, c, d))
    c1, c2 = set(range(1, 17)) - 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)
        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)
        print "      {:>5} {:>5} {:>5}".format(*d)
        print
        return True
    return False


def test_center_col(a, b, c, d):
    """ Rows a and d are swappable, and so are b and c.
    So test each possible ordering of the rows."""
    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_rows(r0, r1, r2, r3):
    """Try all permutations of all rows and see if center column adds up."""
    for a in itertools.permutations(r0):
        for b in itertools.permutations(r1):
            for c in itertools.permutations(r2):
                for d in itertools.permutations(r3):
                    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
    # a, b, c, d are the names of the rows from top to bottom.
    # a has three items.
    # b and c have four. (We'll deal with the solo item later.)
    # d has three.
    for b, c in itertools.combinations(t4, 2):
        if len(set(b + c)) == 8:
            for a, d in itertools.combinations(t3, 2):
                if len(set(a + b + c + d)) == 14:
                    test_rows(a, b, c, d)