Instantly share code, notes, and snippets.

# dblume/fathers_day_puzzle3.py

Last active July 5, 2018 16:49
Show Gist options
• Save dblume/be136326f5846f5bfa39b6ddbfa08e5d to your computer and use it in GitHub Desktop.
Father's Day Puzzle #3, sort of like a magic square, but not a square.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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)