A magic square is a square matrix (N rows by N columns) with the following properties:

1. It contains the numbers 1 through N², with each number appearing exactly once.

2. The sums of each row, each column, and both main diagonals are equal.

For example, here is a "3 by 3" magic square:

4 9 2

3 5 7

8 1 6

The assignment is to create a class to model a magic square and a test class for it.

I. The MagicSquare Class

• The only instance variable is a 2D array of ints

• The class constructor will create an "N by N" 2D array, where the size is passed as a parameter. It will then call a private utility methods to fill the array

• To get credit, your fill method must use the following algorithm:

1. Place a 1 in the "middle" column of the last row.

2. Place the integers from 2 to N² into the matrix in succession, according to these rules:

1. Attempt to place each number in a position that is one row below and one column to the right of the previous number.

2. If rule (a.) leads to a non-existent row and a non-existent column, then the number is placed instead in the position directly above the previous number (i.e., same column, previous row).

3. If rule (a.) leads to a non-existent row, then the number is placed instead in the first row, one column to the right.

4. If rule (a.) leads to a non-existent column, then the number is placed instead in the first column, one row down.

5. If rule (a.) leads to a position that is not empty (i.e., already contains a value), then the number is placed instead in the position directly above the previous number.

• Your MagicSquare class will also have a toString() method that returns the square in table form, as shown above

• Finally, a method that returns a value of true or false indicating whether the square created is truly magic. That is, whether all the sums those of every row and of every column and of both diagonals are equal. All. Every. Both.

II. The Test Class

Your main method will:

1. Get the size of the square, N, from the user. Use a loop so that only positive, odd values for N are accepted

2. Create a MagicSquare object

3. Call the method that tests whether the square is truly magic. If so, call toString and print the square returned. Else, print an error message

6. After each square (or error message) is printed, the user should be asked whether he/she wants to create another