Programming Exercise: Magic Square
| [](http://supermekanismo.files.wordpress.com/2011/12/magicsquareexample-svg.png) |
| A 3x3 Magic Square. [Source](http://en.wikipedia.org/wiki/Magic_square) |
How is it magical?
As you may have guessed from the above diagram, a magic square is an n by n matrix. It contains number 1-n^2 (n square) and the rows, columns and diagonal sums are equal. The above diagram is a 3x3 magic square.
For the full history about magic squares, you can check out the wikipage here. We won't be diving into the history much. Let's get on with the problem. We'll only be tackling the magic squares on odd numbers.
What makes it easy?
What's makes this question relatively easy is that the algorithm is already presented. You don't need to think about how to solve it. The main task is translating the algorithm to code.
Creating an Odd N x N Magic Square
Before diving into code, let's get a look on how a magic square is created. Let's use a 5 x 5 magic square as an example. Note: This is for creating odd based magic squares.
| Order 5 | ||||
|---|---|---|---|---|
| 17 | 24 | 1 | 8 | 15 |
| 23 | 5 | 7 | 14 | 16 |
| 4 | 6 | 13 | 20 | 22 |
| 10 | 12 | 19 | 21 | 3 |
| 11 | 18 | 25 | 2 | 9 |
Place the next value **unless**
- if moving up you are out of range, go to the bottom row (see 1>2 in above diagram)
- if moving right you are out of range, go to the first column on the left (see 3>4 in above diagram)
- if the location in which you're placing the value already has a value in place or if you are at the top right corner, place the new value below (see 5>6 in diagram)
Here is an example of building the above Magic Square.
| Order 5 | ||||
|---|---|---|---|---|
| 1 | ||||
| Order 5 | ||||
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| Order 5 | ||||
|---|---|---|---|---|
| 1 | ||||
| 3 | ||||
| 2 | ||||
| Order 5 | ||||
|---|---|---|---|---|
| 1 | ||||
| 4 | ||||
| 3 | ||||
| 2 | ||||
| Order 5 | ||||
|---|---|---|---|---|
| 17 | 24 | 1 | 8 | 15 |
| 23 | 5 | 7 | 14 | 16 |
| 4 | 6 | 13 | 20 | 22 |
| 10 | 12 | 19 | 21 | 3 |
| 11 | 18 | 25 | 2 | 9 |
**Solving the Problem**
Since we already have the rules in place, it's a matter of how you want to code or implement it. The code I'll be showing is just what first came to my mind in solving it. You can improve upon it further. Also, you may have a different way of implementing the above rules.
I'll be using Java as my language of choice for this problem. Let's begin!
Just remember the x and y coordinate positions (first value is at 0,0) as I'll be using it in solving the problem in moving up, right, left, down.
| Order 5 | ||||
|---|---|---|---|---|
| 17 | 24 | 1 | 8 | 15 |
| 23 | 5 | 7 | 14 | 16 |
| 4 | 6 | 13 | 20 | 22 |
| 10 | 12 | 19 | 21 | 3 |
| 11 | 18 | 25 | 2 | 9 |
| [](http://supermekanismo.files.wordpress.com/2011/12/magic17.png?w=209) |
**Create a separate class for Magic Square**
Yes, you could create this inside the "main" but I prefer to set it up in another class so I could reuse the class if ever the need arises.
**Variables**
We'll need two variables, one for the 2 dimensional array and one for the size. We create a variable for size because we want to be able to create a new magic square with the "n" determined by the user. We mark both values as private because other classes wouldn't need to use these values.
[](http://supermekanismo.files.wordpress.com/2011/12/magic2.png?w=300)
**Constructor**
We create a constructor for class Magic Square. We have size as an input so that we can build different magic squares objects with different values with ease. We declare the class public because we'll be calling the constructor in the main class.
I used this.size because I better understand parameters that way. Since the parameter will have the value for the variable size, I also called the parameter as size. If it confuses you, by all means change it.
We create an if-else to catch a user error. Remember, we are only creating magic squares with odd based "n" values. If successful then the 2d array is created. As an alternate, you could create an exception instead of the if-else scenario but for this example I used if-else.
Update: I added 2 new lines (in the downloadable code). Check note after the methods to better understand it.
**Methods**
[](http://supermekanismo.files.wordpress.com/2011/12/magic3.png?w=300)
**
**
**testFillUpArray()**
This method is used to fill the array with placeholder. I used zero. This method is optional but I used it while testing out the other parts of the code. See note section on why I had this as public.
[](http://supermekanismo.files.wordpress.com/2011/12/magic4.png?w=300)
**printArray()**
We create this method so that it'll be easier to test and see the output. You could mark it private or public depending if you want to see the output through the main class.
[](http://supermekanismo.files.wordpress.com/2011/12/magic6.png?w=300)
**isMagicSquare()**
This method is used to check whether the values inside the 2d array have equal sums. We'll have the individual checking code below. The comments were used while testing out the code.
[](http://supermekanismo.files.wordpress.com/2011/12/magic7.png?w=300)
**checkRowSum()**
The string that was cut short is not essential. Replace the string with what you want to display. The comments were used while testing out the code. We create two variables named rowSum and temp. We use rowSum to hold the initial sum and temp to check the next row's sum. We use temp to compare the previous and next row sum.
We use the first condition (temp not equal to zero) to fix the issue that arises when we're trying to check the previous and current sum. The issue will present itself during the first iteration since you'll compare the first rowSum versus temp which still has a value of zero thus failing the row sum check.
We put rowSum's value to temp then we return rowSum to zero. This is used as previous to new value thought. We have a condition to retain rowSum's value when we're at the last row.
We return rowSum based on how we built the checking in isMagicSquare method.
[](http://supermekanismo.files.wordpress.com/2011/12/magic8.png?w=300)
**checkColumnSum()**
See explanation above.
[](http://supermekanismo.files.wordpress.com/2011/12/magic9.png?w=300)
**checkDiagonalSum()**
You can have a variety of different ways on how to do this. I have two arrays that gets the diagonal values then compares each sum.
**fillUp()**
This is the most important part. This is where we apply the rules. First, let me discuss the general structure and pseudocode.
Loop: 1 - N^2
Is it at first iteration?
True
-
Compute for middle of the array
-
Place first value
-
Save current location
False
If: Is last location is on the first row (1>2 in diagram above)
Else if :Is last location on the far right (3>4 in diagram)
**Else if: **It's normal
**If: **The next location has a value or you are at the top right corner
Last Location = Next Location
Explanation:
We create 4 variables for positions. For the loop condition, we start from 1 to n square by definition of the magic square. We have a special case for the first iteration as mentioned in the problem. We get the middle value by dividing the size by 2. We use int since the decimal value would be truncated. We use that value since it would not need an adjustment. Finally, the first value is saved as "last position" to aid us in getting the next values.
[](http://supermekanismo.files.wordpress.com/2011/12/magic11.png?w=300)
**If**: **Is last location is on the first row (1>2 in diagram above)**
Again, disregard comments. If you read through it, you'll notice I used Magic Square with n = 5 as the test array.
We have the condition to check if the location is in the first row. We need to set the next location in the bottom. We move next location x to the bottom (size-1) then y is moved one to the right as the problem states.
[](http://supermekanismo.files.wordpress.com/2011/12/magic12.png?w=300)
**Else if :Is last location on the far right (3>4 in diagram) **
If we have the last location in the last column, we set the next location y as 0 essentially putting it on the "left". We have next location x -1 because we're moving the value "up" the table.
[](http://supermekanismo.files.wordpress.com/2011/12/magic13.png?w=300)
**
**
**Else if: It's normal**
Normal meaning there is no special situation (except for the last rule. see below). We're saving the location (not the value yet) to "up and right" of the previous value.
[](http://supermekanismo.files.wordpress.com/2011/12/magic14.png?w=300)
**If: The next location has a value or you are at the top right corner**
This is the last special rule. If the next location already has a value, we place it below. We use greater than zero as a test because we filled up the array with zero initially. The next condition check is simply whether its in the top right.
If the condition is true, then we place the value below (x location = x+1 and y value remains the same). If the condition is false, we simply place the value on the next location.
[](http://supermekanismo.files.wordpress.com/2011/12/magic15.png?w=265)
**Last Location = Next Location**
Lastly, we put replace the "last location" with the current one then iterate.
**Complete Code and Running the program**
If the screenshots have you confused, the source code is found [here](http://dl.dropbox.com/u/13982581/ProgrammingExercises/MagicSquare.java) and the sample main class [here](http://dl.dropbox.com/u/13982581/ProgrammingExercises/Main.java). Note the note(?) below. To run the program, create a main class and initialize the MagicSquare with an odd number in the parameter. You can print the array and check to see if it's magical(?).
[](http://supermekanismo.files.wordpress.com/2011/12/magic162.png?w=300)
**Notes**: I tested most of the methods through the main class. In hindsight, I should have placed the methods testFillArray, isMagicSquare and fillUp in the constructor of MagicSquare. I fixed this in the uploaded code. I also changed some of the methods to private (all except isMagicSquare and printArray).
Whew! This post took longer than I expected. Enjoy testing it out.