Last active
July 5, 2018 16:49
-
-
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. | |
# | |
# ( )---( )---( ) | |
# | | | |
# ( )---( )---( )---( ) ( ) | |
# | | | | |
# ( ) ( )---( )---( )---( ) | |
# | | | |
# ( )---( )---( ) | |
# | |
# 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