Skip to content

Instantly share code, notes, and snippets.

@dblume
Last active July 5, 2018 16:49
Show Gist options
  • Save dblume/be136326f5846f5bfa39b6ddbfa08e5d to your computer and use it in GitHub Desktop.
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.
#!/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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment