Sunday, September 20, 2009

Solving a 3x3 Magic Square

In my last post, From 1 Through 19, I challenged you to solve a 3x3 magic square. This is a small instance of the problem (the smallest solvable instance, a 1x1 magic square, is trivial), so it's possible to solve it using a brute force method, but the solution I'll give is a little more elegant than that.

As I wrote in my last post, a magic square is an arrangement of n2 distinct integers (from 1 to n2) in a square such that the n numbers in each row, each column, and in the two long diagonals all have the same sum.


The magic sum


The sum for each row, column, and diagonal is known as the magic sum for the magic square of that particular size. This sum is unique for each size magic square. Knowing the size of the square, there's an easy way to figure out the magic sum. For a 3x3 magic square, we know that each of the three rows add up to the magic sum, x. We also know that all the numbers from 1 through 9 must be used exactly once in all three rows. Combining these two facts we get

3x = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
3x = 45
x = 15

So for our 3x3 magic square, the magic sum is 15. You can generalize the approach above to come up with the magic sum of any size magic square you want to solve.

The center square

The value that goes in the center square can be found using the same process we used in the From 1 Through 19 puzzle. Can the number 6 be placed in the center? No, because that would leave no place for the 9 (6 and 9 already add to 15). The numbers 7, 8, and 9 can be eliminated from the center for the same reason. What about placing the number 4 in the center? That won't do either, since then there would be no place we could put the 1 and still come up with a sum of 15. All the numbers 1 through 4 can be shown to be too small for the same reason. That leaves only the number 5 in the center square.


The rest of the numbers don't just fall into place, though, as they did in the From 1 Through 19 puzzle. Magic squares have additional constraints that weren't present in the earlier puzzle. We'll look at those constraints in the next sections.

9 in the corner?

To illustrate why the rest of the numbers don't fall easily into place after finding the center value, let's place the 9 in a corner and see what happens.


It's plain to see that a number in a corner (in this case, the 9) must combine with six other numbers in three different ways (row, column, diagonal) to sum to 15. It's tempting to start plugging in numbers for the unknown values to see what works, but there's a problem with that approach.

Notice that in the image above there are only two blank squares that the 9 doesn't combine with to form a sum. We know that the 9 cannot be combined with any of 6, 7, or 8, since the sum would then be greater than our magic sum of 15. Since there's no way to force all three of 6, 7, and 8 into the two blank squares, we have no choice but to conclude that the 9 cannot go in a corner.

9 on the side

Once you eliminate the four corners, you have no choice but to place the 9 in one of the four side positions. It doesn't really matter which one you choose, since rotating the puzzle will give you the same solution. After placing the 9, the 1 also falls into place.


Once again, it's tempting to start plugging in numbers to see what values work for the rest of the unknown squares, but there's a little bit more logic that can be applied before the remaining numbers fall into place. We already know that the numbers 6, 7, and 8 cannot be in the same row with the 9. That leaves only the 2, 3, and 4 as candidates for the squares I've labeled x and y in the diagram above. If we were to place the 3 in one of them, we would also need to place the 3 in the other to arrive at the magic sum of 15. Since we can only use each number once, this eliminates the 3 from being placed in the same row with the 9. That leaves only the 2 and 4.


Now there is finally enough information to begin filling in the remaining squares, starting with the two diagonals. One diagonal already contains the 4 and the 5, so the third value must be the 6. The other diagonal containing the 2 and the 5 can be completed only with the 8.


The sum of 15 across the bottom row verifies that these values are correct. The only two values that we haven't used so far, 3 and 7, fall neatly into place for the final solution.


Further reading

If this article doesn't contain everything you ever wanted to know about magic squares (and I understand that some of you probably never even wanted to know this much), then check out the book Before Sudoku: The World of Magic Squares. It contains the history, several variations, and even a few practical applications for this fascinating puzzle.

17 comments:

Venki said...

How many such squares are possible, including the mirror reflections? I tried, but not much clue...

corner kitchen table said...

nice post:)

Fun With Puzzles said...

Thanks for this post

Anonymous said...

thanks alot u helped me heaps

Anonymous said...

Very nice! Thank you for your post, I finished my homework using your website! Lastly, THANKS!!!

Anonymous said...

good but should add some worksheets or tets to practise..

Joseph said...

By the way Venki, 8 are possible, 4 reflections 4 rotations. Thanks for the post, I was stuck on my homework now I finished it.

Anonymous said...

can you please solve the puzzle with the numbers 783 696 609 522 435 348 261 174 87

Bill the Lizard said...

Anonymous,

You can follow the same procedure outlined in the post using those values to find the magic square.

The "magic sum" in this case is 1305 and the center square is 435. You know 783 can't go in a corner for the same reasons 9 couldn't go in a corner for a 1-9 magic square. Placing it on a side leaves 87 on the opposite side. You can follow the rest of the procedure to come up with the magic square:

348, 783, 174
261, 435, 609
696, 87, 522

Anonymous said...

This is very useful information

Anonymous said...

Can you help me with a square in order:
8 7 ?
17 ? ?
5 ? ?

Bill the Lizard said...

Anonymous,

You can get the "magic sum" for that square from the sum of the left-hand column. Then you can use that sum to find the value in the top right corner. From there you can find the value in the center square, then the bottom right corner, then the rest of the values should fall into place.

Anonymous said...

What if the the sum of magic squares differ like it is to be solved though the center number and the total is not given?

Anonymous said...

What are the answers for a 3x3 magic square with a sum of 21
Then 25
Then 35

Anonymous said...

What is the answers for a 3x3 magic square with total of 26
and number range is 8 to 16

Anonymous said...

What is the answers for a 4x4 magic square with total of 40
and number range is 1 to 16

Anonymous said...

What is the answers for a 3x3 magic square with total of "36"
and number range is 8 to 16