Instantly share code, notes, and snippets.

Embed
What would you like to do?
Father's Day Puzzle #3, sort of like a magic square, but not a square.
#!/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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment