In one of our office kitchen/break room areas sits a wooden math puzzle called the magic hexagon. The puzzle consists of nineteen hexagonal wooden blocks that fit inside a larger hexagonal frame. The goal is to arrange the wooden blocks such that every row of numbers adds up to thirty-eight from edge to edge.

One night after work we sat down to try and solve the puzzle. In what was likely a case of too many cooks spoiling the soup, we mostly argued about the best strategy to use, rather than actually arranging the pieces. After a few minutes, I decided it would be easier to just write a program to solve the puzzle for me.

``````# Spoiler: the output is as follows
#
# 3700 checked
#
#     3   19  16
#   17  7   2   12
# 18  1   5   4   10
#   11  6   8   13
#     9   14  15
``````

In order to solve the problem, I first found valid combinations to form the outer ring of the hexagon, then looked for pieces that could fill in the center. The full program follows.

``````import itertools
import sys

def triplesValid(edges):
"""Order edges so that each overlaps the next, or return None."""
flat = sum(edges, ()) # one tuple with all given edge tiles
counts = [flat.count(i) for i in set(flat)]

# We need six numbers used once (the middle of each edge) and six
# numbers used twice (the ends of each edge, which overlap with a
# neighboring edge)
if counts.count(1) != 6 or counts.count(2) != 6:
return None

# Sort edges so that each overlaps the next, if possible.
ls = list(edges)
y = set(edges[1:])
while len(y) > 0:
for el in y:
if len(set(ls[-3:]).intersection(el)) > 0:
ls.extend(el)
y.remove(el)
break
else:
return None
return [tuple(ls[i:i+3]) for i in range(0, len(ls), 3)]

def getTriples():
"""Generate triples that work as hexagon edges.
Returns all (i, j, k) such that 0 < i < j < k < 20, i + j + k = 38.
"""
for i in range(1,20):
for j in range(i+1,20):
k = 38 - i - j
if k > j and k <= 19:
yield (i,j,k)

def getOuterRings():
for combo in itertools.combinations(getTriples(), 6):
scombo = triplesValid(combo)
if scombo:
allsort = []
for i in range(0, len(scombo)):
right = tuple([x for x in scombo[i] if x in scombo[i-1]]
+ [x for x in scombo[i] if (x not in scombo[i-1] and x not in scombo[(i+1)%len(scombo)])]
+ [x for x in scombo[i] if (x not in scombo[i-1] and x in scombo[(i+1)%len(scombo)])])
allsort.append(right)
yield allsort

def checkCenter(ring, center):
return (ring + ring + center + center
== ring + ring + center + center + center
== ring + ring + center + center
== ring + ring + center + center
== ring + ring + center + center + center
== ring + ring + center + center
== ring + ring + center + center + center
== ring + ring + center + center
== ring + ring + center + center)

def getCenter(out):
ring = [e for l in [(x,y) for x,y,z in out] for e in l]
centerels = set(range(1,20)) - set(ring)
for perm in itertools.permutations(centerels):
if checkCenter(ring, perm):
return perm
return None

def printHex(tups, mid):
out = [e for l in [(x,y) for x,y,z in tups] for e in l]
print("  {: <2}  {: <2}  {: <2}".format(out, out, out))
print("  {: <2}  {: <2}  {: <2}  {: <2}".format(out, mid, mid, out))
print("{: <2}  {: <2}  {: <2}  {: <2}  {: <2}".format(out, mid, mid, mid, out))
print("  {: <2}  {: <2}  {: <2}  {: <2}".format(out, mid, mid, out))
print("  {: <2}  {: <2}  {: <2}".format(out, out, out))

i = 0
for out in getOuterRings():
if i % 100 == 0:
sys.stdout.write("\r{} checked".format(i))
sys.stdout.flush()
center = getCenter(out)
if center:
print("\n")
printHex(out, center)
break
i += 1
``````

This code is a bit ugly, but it got me the answer, while my friends all gave up and had a beer instead.