Program to generate Magic square

A Magic square is a two dimensional arrangement of numbers ( from 1 to n² ) in an n x n matrix such that adding all the numbers from any row, column or principal diagonal gives the same result.

for example the following matrix is a magic square of size 3 X 3

8 1 6
3 5 7
4 9 2

Here the by summing up any row,column, or diagonal, result is 15.

There is a simple algorithm for generating square of odd order ( 3 X 3, 5 X 5,… )

We start by filling 1 in middle element in the first row. Then we move one step right and one step above. We will check if there is a number already placed in that slot. If not we put 2 there and follow the same algorithm for subsequent numbers.
If a number is already there, we move down one step and place the next number there.

In moving right,if we reach the last column, we wrap to the first column. Similarly while moving up, if we reach first row, we wrap to the last row. This essentially a cyclic iteration.

The following snapshots shows the step by step filling up of the grid.

0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 6 0 1 6 8 1 6 8 1 6
0 0 0->0 0 0-> 3 0 0-> 3 0 0-> 3 5 0-> 3 5 0 ->3 5 7-> 3 5 7-> 3 5 7
0 0 0 0 0 2 0 0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 9 2

In the first step, when we move right, we reach the last column in the first row. We can not go up, so we move to last row and place 2 there.
In the next step, we can not move from last column, so we move to first column, move up by one position and place 3 there. In the next step, if we move right, move up, we find that cell is already filled with 1. Hence we move down one step and place 4. You can analyze the remaining moves in a similar way.

The following Java program implements the above algorithm. Remember to pass only odd number as parameter.

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 7/26/13
 * Time: 4:53 PM
 */
public class MagicSquare {
    public static void main(String[] args)
    {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int[][] board = new int[n][n]; //automatically initialized with '0'

        int row = 0; // start with first row
        int col = n/2; //middle element
        int num = 1;  // number to be filled
  // n X n grid contains n^2 numbers
        while ( num <= n*n )
        {
            board[row][col] = num;
            num++;

   //increment column, when reaches last, start from the beginning
            int tempCol = (col + 1)%n;
   //decrement row, when last row is reached, move to the first
            int tempRow = (row - 1) >= 0 ? row-1 : n-1;
   
   //If the target cell is not empty, move to next row
            if( board[tempRow][tempCol] != 0 )
            {
                row = (row+1)%n;
            }
            else
            {
                row = tempRow;
                col = tempCol;
            }
        }
  //print the magix square
        for( int i = 0 ; i < n ; i++)
        {
            for( int j = 0 ; j < n ; j++)
            {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Leave a Reply Cancel reply