Magic Quadrant

Magic Square is a square matrix n * n contains the numbers 1 to sqr (n) (each number only once), so that the total numbers of each line separately equals the sum of the numbers of each column; Ende and equal also the total number of each country separately.

First:

Find one of them the following simple way to generate the magic box when the matrix after the individual:

1 - Put 1 in the middle of the line up.

2 - After filling in the box (p, q) test number in the box at the line up and the left column (see arrow in the drawing) any cell (p-1, q-1).

3 - If the box is already busy place the following number of x +1 in the empty box, which lies directly under the box (p, q).

Required:

1 - Type of CheckMagic that tests the fact that the box (ie, matrix) magic or not.

2 - What is the complexity of the CheckMagic.

3 - Write a recursive procedure that you love the magic box of dimension n and in accordance with the algorithm described above.

Procedure RecMagic (x: 1 .. nmax; p, q: 1 .. nmax);

(X represents the number to be filled in and represent each of the p and q are the site that will put the number in it)

Second:

We want to put a general algorithm to solve this issue, regardless of whether it is the matrix after the individual or not, and drawing on the general outline of the algorithms regressive (BackTracking Algorithms).

Required:

4 - Writing a regressive procedure that calculates the magic box of dimension n>

Procedure BackTMagic (x: 1 .. nmax; var b: Boolean);

5 - - type program that you choose the programming language (Java, C #, VB.Net, C + +, Pascal) for the implementation of the algorithm.

That assumes that the Matrix is the matrix required for the convertible in procedural and median x indicates the number that should be put in the matrix and the mediator b indicates the success of the procedure or not.

Note: You must first clarify the call to this procedure