# Magic Solution

Objective

The objective of this problem is to test the students’ understanding on 2-dimensional array.

Problem Description

In mathematics, a magic square of order N is an arrangement N2 numbers, usually distinct integers in a square, such that the N numbers in all rows, all columns, and both diagonals sum to the same constant.

John is interested in the process of creating a magic square. He knew about De La Loubère’s Algorithm and would like to ask for your help to make a program which is able to create a magic square of order N. Here is the algorithm:

1. Place the first number in the middle cell of the top row.

2. Successive numbers are inserted into the square in a diagonal line sloping upwards and to the right.

3. When the top row is reached, the next number goes in the bottom row as if it were directly below the top row.

4. When the right hand column is reached, the next number goes in the extreme left column as if it were directly to the right of the right hand column.

5. When a cell is reached that is already filled, or when the top right hand cell is reached, the next number drops to the cell directly below.

Given an odd number N, create the magic square using the given algorithm.

Input

The input contains one integer, N (1 <= N <= 20).

Output

Output the magic square with the same format as sample output. (There are N lines in

the output, each line has N numbers. There is a space character between 2 numbers.

There is no space after the last number in a line.)

Sample Input

3

Sample Output

8 1 6

3 5 7

4 9 2

Algorithm Template

1. How to store the grid information?

2. How to determine whether a cell is empty or not empty?

3. How are you going to keep track on the current position?

4. What should you do when you are at the first row and you want to move up?

The objective of this problem is to test the students’ understanding on 2-dimensional array.

Problem Description

In mathematics, a magic square of order N is an arrangement N2 numbers, usually distinct integers in a square, such that the N numbers in all rows, all columns, and both diagonals sum to the same constant.

John is interested in the process of creating a magic square. He knew about De La Loubère’s Algorithm and would like to ask for your help to make a program which is able to create a magic square of order N. Here is the algorithm:

1. Place the first number in the middle cell of the top row.

2. Successive numbers are inserted into the square in a diagonal line sloping upwards and to the right.

3. When the top row is reached, the next number goes in the bottom row as if it were directly below the top row.

4. When the right hand column is reached, the next number goes in the extreme left column as if it were directly to the right of the right hand column.

5. When a cell is reached that is already filled, or when the top right hand cell is reached, the next number drops to the cell directly below.

Given an odd number N, create the magic square using the given algorithm.

Input

The input contains one integer, N (1 <= N <= 20).

Output

Output the magic square with the same format as sample output. (There are N lines in

the output, each line has N numbers. There is a space character between 2 numbers.

There is no space after the last number in a line.)

Sample Input

3

Sample Output

8 1 6

3 5 7

4 9 2

Algorithm Template

1. How to store the grid information?

2. How to determine whether a cell is empty or not empty?

3. How are you going to keep track on the current position?

4. What should you do when you are at the first row and you want to move up?

You'll get 1 file (161.1KB)