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) | |
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) | |
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