Instantly share code, notes, and snippets.

# dblume/fathers_day_puzzle3.py Last active Jul 5, 2018

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 + c1 + d == total and a + c2 + c == total: print " {:>5} {:>5} {:>5}".format(*a) print "{:>5} {:>5} {:>5} {:>5} {:>5}".format(b, b, b, b, c2) print " {:>5} {:>5} {:>5} {:>5} {:>5}".format(c1, *c) print " {:>5} {:>5} {:>5}".format(*d) print return True if b + c2 + d == total and a + c1 + c == total: print " {:>5} {:>5} {:>5}".format(*a) print "{:>5} {:>5} {:>5} {:>5} {:>5}".format(b, b, b, b, 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 + b + c + d == total: return test_outer_cols(a, b, c, d) if a + b + c + d == total: return test_outer_cols(d, b, c, a) if a + b + c + d == total: return test_outer_cols(a, c, b, d) if a + b + c + d == 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)
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.