The magic square

1	9	5
6	2	7
8	4	3

 

 

 

 

 

 

 

The first square is attached above. Surprisingly it did not take too long and I did not write it down as a formal problem. Rather, I simply noted that the numbers 1+2+3+...+9 = 45 exactly. The connection is that we are told (actually we don't need to be told) that each column and row has to sum to 15. This is 45/3, so that seems to be useful. I started by putting 1 in the upper left corner, and hence I need bigger numbers on the row to make 15. I chose 9 and then 5. Now working down at the first column from the left, since I have used 9 I want something big so I pick something like 8. This seems to work fine and I was able to complete them row and column wise. The problem arises when considering the diagonals, they are way off at 1 + 2 + 3. To try it more, I start by considering the diagonals, and complete an X in the middle first. The trial and error approach took quite long, so I ended up using some linear algebra approach to this problem, as they are nothing more than a set of linear equations. The matrix was just 1s and 0s, and it was big but sparse. While working through it would not be too difficult, I used Matlab to help solving it. 

 

8	1	6
3	5	7
4	9	2

 

 

 

 

 

 

I am glad some people find it interesting, so I will provide the rough sketch of setting it up as a linear algebra problem.

First, let's give the 9 numbers a name, such as a,b,c,d,e,f,g,h,i.

 

a	b	c
d	e	f
g	h	i

 

 

 

 

 

 

Now the magic square rule can be captured as 

1) a+b+c = 15

2) d+e+f = 15

3) g+h+i = 15

corresponding to the sum of the rows.

4)a+d+g = 15

5)b+e+h=15

6)c+f+i=15

Corresponding to the columns

7)a+e+i=15

8)c+e+g=15

Corresponding to the diagonal.

Now we have 8 equations and 9 variables, and without any integer constraints we know we won’t get a unique solution.

Let’s supply a guess, say e = 5 by placing 5 in the middle.

Now we can assemble this in a matrix equation Ax = b (you can use the following code in Matlab/octave)

A = [1 1 1 0 0 0 0 0 0; 0 0 0 1 1 1 0 0 0; 0 0 0 0 0 0 1 1 1; 1 0 0 1 0 0 1 0 0; 0 1 0 0 1 0 0 1 0; 0 0 1 0 0 1 0 0 1; 1 0 0 0 1 0 0 0 1; 0 0 1 0 1 0 1 0 0;0 0 0 0 1 0 0 0 0]

 

The right hand side is a vector

b = [ 15 15 15 15 15 15 15 15 5]'

We are now ready to solve! (with a catch, of course)

Try using

A\b

And we get an answer of all 5s. Clearly something is not quite right.

That’s because we don’t have a nice way to specify that the variables must take distinct values from 1 to 9.

We can then try to see what we can do.

Try

rref(A)

and we will get a matrix with 2 zero rows on the bottom. That means there are really only 7 independent equation, the very last 2 does not tell us something new.

Solution: We have to supply another 2 guesses, say a = 8, b = 1

Remark: this actually foes full circle back to the problem of trial and error with 3 values supplied. The rest can be computed by hand must faster anyways. (any 3 values will have a row, column, or diagonal of 2 entries filled, so we can figure out the last one)

 

Another method which comes to mind after trying linear algebra would be integer linear programming! Linear programming is maximizing a linear function given linear constraints. In this case we are not maximizing anything, but we could set up a problem to find a feasible set of values that help us fill in the square.

It could look something like this

Max 0

Subject to

1) a+b+c = 15

2) d+e+f = 15

3) g+h+i = 15

4)a+d+g = 15

5)b+e+h=15

6)c+f+i=15

7)a+e+i=15

8)c+e+g=15

And we can apply Simplex’s method to find a feasible solution! (Because any solution attains a maximum of 0 in the function we are trying to maximize).