Construct a Magic Square

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).
Magic square has following properties -

• No number is repeated.
• All rows, columns and diagonals give equal sum.

8	1	6
3	5	7
4	9	2

Strategy:

The best method to approach this problem is called Siamese method.

• 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.

Complexity of pushing n elements is O(n).