A magic square is an n X n matrix in which each of the integers 1,2,3, ..., nZ appears exactly once and all column sums, row sums, and diagonal sums are equal. For example, the following is a 5 X 5 magic square in which all the rows, columns, and diagonals add up to 65:
The following is a procedure for constructing an n x n magic square for any odd integer n. Place 1 in the middle of the top row. Then, after integer k has been placed, move up one row and one column to the right to place the next integer k + 1, unless one of the following occurs:
- If a move takes you above the top row in the jth column, move to the bottom of the jth column and place k + 1 there.
- If a move takes you outside to the right of the square in the throw, place k + 1 in the ith row at the left side.
- If a move takes you to an already filled square or if you move out of the square at the upper right-hand corner, place k + 1 immediately below k.
- Write a program to construct an n X n magic square for any odd value of n.