Monday's Programming Question

Monday November 3, 2008

I'm not really sure who first came up with a magic square. There is a story about a huge flood in China a long time ago. The people were worried they would be washed away and tried to appease the river god by making sacrifices. Nothing seemed to work until a child noticed a turtle sporting a magic square on its back that kept circling the sacrifice. The square told the people how big their sacrifice needed to be in order to save themselves. Since then magic squares are the height of fashion for any discerning turtle.

In case you've never come across one before, a magic square is an arrangement of sequential numbers in a square so that the rows, columns and diagonals all add up to the same number. For instance, a 3x3 magic square is:

8 1 6
3 5 7
4 9 2

Each row, column and diagonal adds up to 15.

This week the program to write is concerned with creating odd sized magic squares (i.e., the size of the square can only be an odd number, 3x3, 5x5, 7x7, 9x9, and so on). The trick with making such a square is to place the number 1 in the first row and middle column. To find where to place the next number, move diagonally upwards to the right (i.e., one row up, one column across). If such a move means you fall off the square, wrap around to the row or column on the opposite side. Finally, if the move takes you to a square that is already filled, go back to the original square and move downwards by one. Repeat the process until all the squares are filled.

For example, a 3x3 magic square would start like so:

0 1 0
0 0 0
0 0 0

A move diagonally upwards means we wrap around to the bottom of the square:

0 1 0
0 0 0
0 0 2

Likewise the next diagonal move upwards means we wrap around to the first column:

0 1 0
3 0 0
0 0 2

Now the diagonal move upwards results in a square that is already filled, so we go back to where we came from and drop down a row:

0 1 0
3 0 0
4 0 2

and it continues on and on until all the squares are full.

Write a Java program that takes an input from the user for an odd number, create the magic square and display it to the screen along with the magic number that each row, column and diagonal adds up to. The requirements are to write two methods – one to create the magic square and one that displays it to the screen. These are then called from the main method. The question is can your program create a 5x5 magic square like the one below?