[ad_1]
Recall that a magic square is a 2-dimensional square array with n rows and n columns where each row,
col, and diagonal add up to the same value. The value that every row, column, and diagonal adds up to is
called the magic sum. For example, here is a magic square for the case n = 4 with a magic sum of 34:
6 10 7 11 3 8 9 14 12 1 16 5 13 15 2 4
If a size n magic square contains all of the number from 1 to n2 exactly once (as in the example above) we
call this a standard magic square and it is not hard to show that the magic sum of a standard size n magic
square is n×(n2 +1)
2 .
You are to write a program that will find standard magic squares in three different ways, by
implementing the following 3 algorithms.
Purely random. Randomly put the numbers from 1 to n2 into an n × n array and then check to see if it is
a magic square. Fill the array from top to bottom, left to right order. In other words, first fill the first row
from left to right, then the second row, etc. Do this repeated until either a magic square is found or some
limit for the number of tries is reached. The limit will be a parameter to your magic square method.
The hardest part of implementing this is finding an efficient way to it. For example, in the 4 × 4 case,
how do we get the numbers from 1 to 16 randomly into the array? The way I did it was to create a 16
element array (in general you will create a n × n array) and put the numbers from 1 to 16 into that array. I
then randomly found one of the 16 elements, put it into the magic square array, and switched that element to
the end of the array so that I would never use it again. For the next step I randomly selected an element from
the first 15 spots in the array, put that in the magic sum array, and then swapped it so that it is 1 from the end
of the array.
Here’s how the example above got started. Let’s call my 16-element array num. It starts looking like this:
num: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
The algorithm found a random location in the 16-element array, in this case it’s location 5 with value 6, put
the 6 in the first position of the magic square and then swapped that 6 with 16 at the end of the num array,
giving us:
num: 1 2 3 4 5 16 7 8 9 10 11 12 13 14 15 6
Next the algorithm found a random location in the first 15 spots of num, in this case it was 10 which was
then put into the magic square and moved to the right of num giving us:
num: 1 2 3 4 5 16 7 8 9 15 11 12 13 14 10 6
Continue this until the entire magic square array is filled.
If you have an alternative way for doing this bring it up in a Discussion.
For finding random numbers you can either use Math.random or the Random class. Look these up in the
Java docs here and here. I think the Random class is easier to use but just be sure not to instantiate too many
Random objects. You only need 1.
[ad_2]
