Magic Square Solver Using Constraint-Programming

Question

I'm trying to do a custom magic square solver using constraint-programming in Python. For this I use python-constraint (http://labix.org/python-constraint).

For this problem the definition of a magic square will be: "A magic square is an arrangement of integers (positives or negatives) in an nxn matrix, and such that the sum of the entries of any row, any column, or any main diagonal is the same."

I have a pre-filled magic square like this:

+----+----+----+----+
| 7  |    |    |  4 |
+----+----+----+----+
|    |    |    |    |
+----+----+----+----+
| 0  | -3 | -2 |  3 |
+----+----+----+----+
| -5 |  6 |    |    |
+----+----+----+----+

Here is the code I use:

from constraint import *

problem = Problem()
problem.addVariables(range(0, 16), range(-20, 20))

problem.addConstraint(lambda a: a==7, [0])
problem.addConstraint(lambda a: a==4, [3])
problem.addConstraint(lambda a: a==0, [8])
problem.addConstraint(lambda a: a==-3, [9])
problem.addConstraint(lambda a: a==-2, [10])
problem.addConstraint(lambda a: a==3, [11])
problem.addConstraint(lambda a: a==-5, [12])
problem.addConstraint(lambda a: a==6, [13])

problem.addConstraint(ExactSumConstraint(-2), [0,5,10,15])
problem.addConstraint(ExactSumConstraint(-2), [3,6,9,12])
for row in range(4):
    problem.addConstraint(ExactSumConstraint(-2),
                          [row*4+i for i in range(4)])
for col in range(4):
    problem.addConstraint(ExactSumConstraint(-2),
                          [col+4*i for i in range(4)])
solutions = problem.getSolution()
print solutions

I can't find any solutions, while i think my constraints are corrects. The sum of each row and each column and both diagonals must be equal to -2 (based on the row we have on the magic square).

Do you have any ideas ? Thanks.

Answer 1

Ok, let's do some math (and python) to solve your mystery.

The row constraint on the first row tells you, that the value at pos. 4 is -4. The constraint for the off diagonal tells you, that the value at pos. 6 is 2.

Hence we already used the values [-5, -4, -3, -2, 0, 2, 3, 4, 6, 7]. The sum of these values is 8.

Therefor we have to choose six values out of range(-20, 20) without the already choosen values.

In a magic square with 4 times 4 entries the row/column/diagonal sum has to be

1 / 4 * sum(all_entries)

With that, we can prepare a brute force solution.

from itertools import combinations
choosen = [-5, -4, -3, -2, 0, 2, 3, 4, 6, 7]  # len(choosen) == 10
s_choosen = sum(choosen)
free_values = [x for x in range(-20, 20) if x not in choosen]
to_test = []
# we have to choose 6 values out of free_values
for comb in combinations(free_values, 6):
  if (1 / 4. * (sum(comb) + s_choosen)) == -2:  # could form correct row/col/diag sum
    to_test.append(comb)

This code gives us 7254 possible 6-tuples to fill in the free places in the square. And none of them results in a magic square.

If you explicitly don't want to apply the AllDifferentConstraint() then you have to do the following to validate the solution of python-constraint via bruteforcing it.

You still have to pick 6 values; but this time out of the whole range(-20, 20) with replacement.

from itertools import combinations_with_replacement
to_test2 = []
for comb in combinations_with_replacement(range(-20, 20), 6):
     if (1 / 4. * (sum(comb) + s_choosen)) == -2:  # could form correct row/col/diag sum
            to_test2.append(comb)
len (to_test2)


97063

The function combinations_with_replacements returns only the sorted combinations. Now we have to add all the permutations that satisfiy the constraint for the row sums.

The already set values (7 and 4) have a sum of 11. Therefor the first two entries in the 6-tuples have to have sum == -13. For the second row, the deduced entries (-4 and 2) have sum -2. So the remaining to entry for this line have to add up to 0. In the last row the sum of the already set entries is 1. Hence the sum of the last two entries has to be -3:

from itertools import permutations
sum_rows = []
for comb in to_test2:
    for entry in permutations(comb):
        if entry[0] + entry[1] == -13 and entry[2] + entry[3] == 0 and entry[4] + entry[5] == -3:
            sum_rows.append(entry)
len(sum_rows)




56672

Now we have to check the column sums. The second column has (-3 and 6) sum 3. So the sum of entry 0 and 2 has to be -5. The third column has (2 and -2) sum 0. Therefor the sum of entry 1 and 4 has to be -2. The fourth column has (4 and 3) sum 7. Hence the sum of entry 3 and 5 has to be -9.

col_sums = []
for entry in sum_rows:
    if entry[0] + entry[2] == -5 and entry[1] + entry[4] == -2 and entry[3] + entry[5] == -9:
        col_sums.append(entry)
len(col_sums)




32

Finally we have to check the sum of the diagonal. The sum of the diagonal (7 and -2) is 5. Therefor the sum of entry 2 and 5 has to be -7.

diag_sums = []
for entry in col_sums:
    if entry[2]+ entry[5] == -7:
        diag_sums.append(entry)
len(diag_sums)




1




print diag_sums

[(-6, -7, 1, -1, 5, -8)]