Problem
Write an algorithm to fill a magic square of size 3. You are given a position to start with (location of 1 on any edge).Background
Magic square has following properties -- No number is repeated.
- All rows, columns and diagonals give equal sum
- The magic constant of a normal magic square depends only on n and has the following value:
M = n(n^2+1)/2. eg. for 3, M = 3 * (9+1)/2 = 15.
For normal magic squares of order n = 3, 4, 5, …, the magic constants are: 15, 34, 65, 111, 175, 260, …
8 1 6 3 5 7 4 9 2
Solution
Method 1 - Use Siamese methodThe best method to approach this problem is called Siamese method. This approach will work for any n provided n is odd.
- Iterate from 1 to 9. We are already given the location of 1.
- Keep circular shifting in consideration. Means if you are at the top row and want to go up, you are moving to last row by circular shift.
- Post the next element up and right of current location
- If that location is already occupied, post it on a location just below the current pointer.
- Move to next element until the square is complete.
Three conditions hold:
1. The position of next number is calculated by decrementing row number of previous number by 1, and incrementing the column number of previous number by 1. At any time, if the calculated row position becomes -1, it will wrap around to n-1. Similarly, if the calculated column position becomes n, it will wrap around to 0.
2. If the magic square already contains a number at the calculated position, calculated column position will be decremented by 2, and calculated row position will be incremented by 1.
3. If the calculated row position is -1 & calculated column position is n, the new position would be: (0, n-2).
Example: Magic Square of size 3 ---------------------- 2 7 6 9 5 1 4 3 8 Steps: 1. position of number 1 = (3/2, 3-1) = (1, 2) 2. position of number 2 = (1-1, 2+1) = (0, 0) 3. position of number 3 = (0-1, 0+1) = (3-1, 1) = (2, 1) 4. position of number 4 = (2-1, 1+1) = (1, 2) Since, at this position, 1 is there. So, apply condition 2. new position=(1+1,2-2)=(2,0) 5. position of number 5=(2-1,0+1)=(1,1) 6. position of number 6=(1-1,1+1)=(0,2) 7. position of number 7 = (0-1, 2+1) = (-1,3) // this is tricky, see condition 3 new position = (0, 3-2) = (0,1) 8. position of number 8=(0-1,1+1)=(-1,2)=(2,2) //wrap around 9. position of number 9=(2-1,2+1)=(1,3)=(1,0) //wrap around
Here is the code
public static void generateSquare(int n)
{
int[][] magicSquare=new int[n][n];
// set all slots as 0
Arrays.fill(magicSquare,0)
// Initialize position for 1
int i = n/2;
int j = n-1;
// One by one put all values in magic square
for (int num=1; num <= n*n; )
{
if (i==-1 && j==n) //3rd condition
{
j = n-2;
i = 0;
}
else
{
//1st condition helper if next number goes to out of square's right side
if (j == n)
j = 0;
//1st condition helper if next number is goes to out of square's upper side
if (i < 0)
i=n-1;
}
if (magicSquare[i][j]) //2nd condition
{
j -= 2;
i++;
continue;
}
else
magicSquare[i][j] = num++; //set number
j++; i--; //1st condition
}
// print magic square
out.println("The Magic Square for n="+ n + "Sum of each row or column"+n*(n*n+1)/2);
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
out.print(magicSquare[i][j]);
out.println();
}
}
Complexity of pushing n elements is O(n).
References
0 comments:
Post a Comment