Shouldn't this code generate a satisfiable value to all 9 variables of a magic square of 3*3?

Question

It took 22 minutes on a Core 2 Duo with no result.

for a in range(10):
    for b in range(10):
        while b!=a:

            for c in range(10):
                while c!= a or b:
                    for d in range(10):
                        while d!=a or b or c:

                                for e in range(10):
                                    while e!=a or b or c or d:

                                        for f in range(10):
                                            while f!=a or b or c or d or e:
                                                for g in range(10):
                                                    while g!=a or b or c or d or e or f:

                                                        for h in range(10):
                                                            while h!= a or b or c or d or e or f or g:
                                                                for i in range(10):
                                                                    while i!= a or b or c or d or e or f or g or h:
                                                                        if (a+b+c==15 and a+d+g==15 and d+e+f==15 and g+h+i==15 and b+e+h==15 and c+f+i==15 and a+e+i==15 and c+e+g==15):
                                                                            print(a,b,c,d,e,f,g,h,i)

Please see http://stackoverflow.com/q/9504638/3001761. Also **wow** that's ugly. — jonrsharpe, Mar 15 '15 at 16:10
All those `while` loops will run infinitely if the condition is true. Also, you're misusing `or`. — interjay, Mar 15 '15 at 16:23

score 2 · Accepted Answer · answered Mar 15 '15 at 16:23

2

This is ugly, but the error is that you cannot have a comparison like

while e!=a or b or c or d:

instead, you should write

while e!=a and e!=b and e!=c and e!=d:

Please learn how to use arrays/lists and re-think the problem.

answered Mar 15 '15 at 16:23

Selcuk

57,004
12
102
110

2

This shouldn't even be a `while` loop, it would just loop infinitely. – interjay Mar 15 '15 at 16:32

Hugh Bothwell · Answer 2 · 2015-03-15T17:12:58.327

@Selcuk has identified your problem; here is an improved approach:

# !!! Comments are good !!!
# Generate a magic square like
#
#   a b c
#   d e f
#   g h i
#
# where each row, col, and diag adds to 15

values = list(range(10))   # problem domain
unused = set(values)       # compare against a set
                           #  instead of chained "a != b and a != c"
SUM = 15

for a in values:
    unused.remove(a)

    for b in values:
        if b in unused:
            unused.remove(b)

                # value for c is forced by values of a and b
                c = SUM - a - b
                if c in unused:
                    unused.remove(c)

                    #
                    # etc 
                    #

                    unused.add(c)
            unused.add(b)
    unused.add(a)

This will work, but will still be ugly.

In the long run you would be better off using a constraint solver like python-constraint:

from constraint import Problem, AllDifferentConstraint

values = list(range(10))
SUM = 15

prob = Problem()

# set up variables
prob.addVariables("abcdefghi", values)

# only use each value once
prob.addConstraint(AllDifferentConstraint())

# row sums
prob.addConstraint(lambda a,b,c: a+b+c==SUM, "abc")
prob.addConstraint(lambda d,e,f: d+e+f==SUM, "def")
prob.addConstraint(lambda g,h,i: g+h+i==SUM, "ghi")

# col sums
prob.addConstraint(lambda a,d,g: a+d+g==SUM, "adg")
prob.addConstraint(lambda b,e,h: b+e+h==SUM, "beh")
prob.addConstraint(lambda c,f,i: c+f+i==SUM, "cfi")

# diag sums
prob.addConstraint(lambda a,e,i: a+e+i==SUM, "aei")
prob.addConstraint(lambda c,e,g: c+e+g==SUM, "ceg")

for sol in prob.getSolutionIter():
    print("{a} {b} {c}\n{d} {e} {f}\n{g} {h} {i}\n\n".format(**sol))

Note that this returns 8 solutions which are all rotated and mirrored versions of each other. If you only want unique solutions, you can add a constraint like

prob.addConstraint(lambda a,c,g: a<c<g, "acg")

which forces a unique ordering.

Also note that fixing the values of any three corners, or the center and any two non-opposed corners, forces all the remaining values. This leads to a simplified solution:

values = set(range(1, 10))
SUM = 15

for a in values:
    for c in values:
        if a < c:                    # for unique ordering
            for g in values:
                if c < g:            # for unique ordering
                    b = SUM - a - c
                    d = SUM - a - g
                    e = SUM - c - g
                    f = SUM - d - e
                    h = SUM - b - e
                    i = SUM - a - e
                    if {a,b,c,d,e,f,g,h,i} == values:
                        print(
                            "{} {} {}\n{} {} {}\n{} {} {}\n\n"
                            .format(a,b,c,d,e,f,g,h,i)
                        )

On my machine this runs in 168 µs (approximately 1/6000th of a second).

Shouldn't this code generate a satisfiable value to all 9 variables of a magic square of 3*3?

2 Answers2