In this post I would be discussing about generating a magic square of odd dimension. I had already discussed about magic square in my earlier post on Magic Square test in Java.
A method for constructing magic squares of odd order was published by the French diplomat de la Loubère in his book, A new historical relation of the kingdom of Siam (Du Royaume de Siam, 1693), in the chapter entitled The problem of the magical square according to the Indians. (Source: http://en.wikipedia.org/wiki/Magic_square#Method_for_constructing_a_magic_square_of_odd_order) The method operates as follows:
The method prescribes starting in the central column of the first row with the number 1. After that, the fundamental movement for filling the squares is diagonally up and right, one step at a time. If a filled square is encountered, one moves vertically down one square instead, then continues as before. When an “up and to the right” move would leave the square, it is wrapped around to the last row or first column, respectively.
Let us understand the above procedure of making a magic square with the help of an example. Following is the step-wise illustration of making a magic square of 5 x 5.
Step 1 _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Step 2 _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 2 _ Step 3 _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 3 _ _ _ 2 _ Step 4 _ _ 1 _ _ _ _ _ _ _ 4 _ _ _ _ _ _ _ _ 3 _ _ _ 2 _ Step 5 _ _ 1 _ _ _ 5 _ _ _ 4 _ _ _ _ _ _ _ _ 3 _ _ _ 2 _ Step 6 _ _ 1 _ _ _ 5 _ _ _ 4 6 _ _ _ _ _ _ _ 3 _ _ _ 2 _ Step 7 _ _ 1 _ _ _ 5 7 _ _ 4 6 _ _ _ _ _ _ _ 3 _ _ _ 2 _ Step 8 _ _ 1 8 _ _ 5 7 _ _ 4 6 _ _ _ _ _ _ _ 3 _ _ _ 2 _ Step 9 _ _ 1 8 _ _ 5 7 _ _ 4 6 _ _ _ _ _ _ _ 3 _ _ _ 2 9 Step 10 _ _ 1 8 _ _ 5 7 _ _ 4 6 _ _ _ 10 _ _ _ 3 _ _ _ 2 9 Step 11 _ _ 1 8 _ _ 5 7 _ _ 4 6 _ _ _ 10 _ _ _ 3 11 _ _ 2 9 Step 12 _ _ 1 8 _ _ 5 7 _ _ 4 6 _ _ _ 10 12 _ _ 3 11 _ _ 2 9 Step 13 _ _ 1 8 _ _ 5 7 _ _ 4 6 13 _ _ 10 12 _ _ 3 11 _ _ 2 9 Step 14 _ _ 1 8 _ _ 5 7 14 _ 4 6 13 _ _ 10 12 _ _ 3 11 _ _ 2 9 Step 15 _ _ 1 8 15 _ 5 7 14 _ 4 6 13 _ _ 10 12 _ _ 3 11 _ _ 2 9 Step 16 _ _ 1 8 15 _ 5 7 14 16 4 6 13 _ _ 10 12 _ _ 3 11 _ _ 2 9 Step 17 17 _ 1 8 15 _ 5 7 14 16 4 6 13 _ _ 10 12 _ _ 3 11 _ _ 2 9 Step 18 17 _ 1 8 15 _ 5 7 14 16 4 6 13 _ _ 10 12 _ _ 3 11 18 _ 2 9 Step 19 17 _ 1 8 15 _ 5 7 14 16 4 6 13 _ _ 10 12 19 _ 3 11 18 _ 2 9 Step 20 17 _ 1 8 15 _ 5 7 14 16 4 6 13 20 _ 10 12 19 _ 3 11 18 _ 2 9 Step 21 17 _ 1 8 15 _ 5 7 14 16 4 6 13 20 _ 10 12 19 21 3 11 18 _ 2 9 Step 22 17 _ 1 8 15 _ 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 _ 2 9 Step 23 17 _ 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 _ 2 9 Step 24 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 _ 2 9 Step 25 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9
The Java program for creating a magic square of n * n, where n is odd, is as follows:
class MagicSquare{
public static void generateMagicSquare( int n ){
int magic[][] = new int[ n ][ n ];
int row = 0, col = n / 2, i, j, square = n * n;
for( i=1; i <= square ; i++ ){
magic[ row ][ col ] = i;
if( i % n == 0 ) row++;
else{
if( row == 0 ) row = n - 1;
else row--;
if( col == ( n - 1 ) ) col = 0;
else col++;
}
}
for( i = 0; i < n ; i++ ){
for( j = 0; j < n; j++ ){
System.out.print( magic[ i ][ j ] + "\t" );
}
System.out.println();
}
}
public static void main(String args[]){
generateMagicSquare(7);
}
}
The loop at line number 5 would run n*n times and it’s purpose is to control the number to be filled in the array. Line number 6 assigns the current value stored in i to the element position row and col. The remaining portion of the loop is for computing the next position where the next number is to be placed. The if-statement on line number 7, is for moving one row below when the next element which diagonally up towards the right is already filled up (see the step 5 and step 6 in the example of 5 x 5 magic square above, the same applies for step 10-11 and so on). The if-statement on line number 11, is for wrapping the row variable to the bottom once it reaches the top row. The if-statement on line number 13, is for wrapping the column to the first column once it reaches the last column. The second for loop is for displaying the contents of the array magic which is storing the magic square we have created.
The output of the above program for generating a magic square of nxn, where n is odd (in this case 7) is as follows:
30 39 48 1 10 19 28 38 47 7 9 18 27 29 46 6 8 17 26 35 37 5 14 16 25 34 36 45 13 15 24 33 42 44 4 21 23 32 41 43 3 12 22 31 40 49 2 11 20