# Solution to the star problem by leonardo maffi, V1.1, Feb 24 2007

import csp # http://www.fantascienza.net/leonardo/so/csp.zip

print """
Problem: place the numbers 1 to 16 in the squares such that
the total of the four numbers along each line is the same:

         e
   a b    c d
   f          p
g                o
   h          n
   i j    l m
         k

http://heath.hrsoftworks.net/archives/000073.html
Note that this problems takes 50-90+ minutes to run
"""

p = csp.Problem()
p.addvars("abcdefghijklmnop", range(1, 17))
p.alldifferent()

sides = ["+".join(s) for s in "abcd ecpo dpnm onlk mlji kjhg ihfa gfbe".split()]

for s in sides[1:]:
    p.addrule(sides[0] + " == " + s)
sol = p.solution()
sum_side = sum(sol[c] for c in "abcd")
print "Found sum:", sum_side

p.delrules()
p.alldifferent()
for s in sides:
    p.addrule(s + " == %d" % sum_side)

for sol in p.xsolutions():
    print "         %2d" % sol['e']
    print "   %2d %2d    %2d %2d" % (sol['a'], sol['b'], sol['c'], sol['d'])
    print "   %2d          %2d" % (sol['f'], sol['p'])
    print "%2d                %2d" % (sol['g'], sol['o'])
    print "   %2d          %2d" % (sol['h'], sol['n'])
    print "   %2d %2d    %2d %2d" % (sol['i'], sol['j'], sol['l'], sol['m'])
    print "         %2d\n" % sol['k']