CIS 250 Magic square assignment
The objective of this assignment is to write a program to find all
4 by 4 arrays which contain the numbers from 1 through 16 which also
have the property that all rows, all columns, and both diagonals
add up to the same value. This involves the use of a two-dimensional
array.
It turns out that we can tell what that sum is ahead of time. Since all
the numbers from 1 through 16 are represented once, we know that all
four rows (or columns) will have to add up to the total of the digits 1
through 16, which is 136. Since all the rows have to have the same sum,
we know that each row must be one-quarter of 136, which is 34. So, all
rows must sum to 34. Likewise, all columns must sum to 34. The two
diagonals must also sum to 34.
Here is an example:
1 4 13 16
14 15 2 3
8 5 12 9
11 10 7 6
In the example above, the second row is 14+15+2+3 = 34. The third column is
13+2+12+7 = 34. The diagonals are 1+15+12+6 = 16+2+5+11 = 34. Hopefully,
that gives you a pretty good idea of the rules for this assignment.
So, what do you have to do? You have to create a program that will find, count, and
optionally display all 7040 solutions. Here are some suggestions and requirements:
- You are required to use a two dimensional (4 by 4) array to hold the
numbers for processing.
- Create a function named findSquares. It should take a Boolean value that is true
if you want the solutions displayed and false if you don't want the solutions
displayed. It should return an int which is the number of solutions found.
- All the main funtion has to do is call findSquares and display the number
that it returns.
- A straight-forward brute-force approach would require trying every
possible combination of digits in the cells.
for cell_1 = 1 to 16
for cell_2 = 1 to 16
for cell_3 = 1 to 16
etc.
This is problematic since this would require 16 nested loops iterating 16
times each. This would create 18,446,744,073,709,551,616 combinations
to check. Even if you were able to check 3 billion of those combinations
per second, which would be checking one position per CPU cycle on a 3GHz
single core processor, that would still take almost 195 years. Of course,
if you needed 11 CPU cycles to check each solution, then you would have had
to have started your program before Christ was born to have an answer now.
Clearly, you need to employ some kind of shortcut.
- One shortcut to the brute-force approach is to recognize that some cells
have only one possible value once other cells have been chosen. For example,
if we are choosing values for row 1, and the first three values are 1, 4,
and 13, then we know that the last cell in that row must be 34-1-4-13 = 16.
Therefore the last cell in each row does not have to be generated by a loop,
but by simple subtraction. Likewise, the last cell in each column is determined
by the three cells above it. This reduces the number of loops needed for a
brute-force approach to 9. This gives 169 iterations, which is only
68,719,476,736 combinations to check. That may seem like a lot, but if you
divide that by modern processor speeds (3GHz), you end up with around 23
seconds. That's a ballpark estimate. You won't be able to check a combination
in one processor cycle. With a couple more optimizations, though,
you should be able to end up in the 2 minute range. With really clever optimization,
you could complete all the checking in under one second, but displaying all the
results on the screen will probably cost you a few more seconds.
- OK. So you have nine loops that set the first three cells in the first three
rows to the numbers 1 through 16. For each of these combinations, you can
calculate what all the other cells must be. What other optimizations are possible?
The most obvious is that every time you choose a number, you could check to see if
it is already used in another cell. If the number was already used, then have the
current loop continue on to the next value.
for cell_1 = 1 to 16
for cell_2 = 1 to 16
if cell_2 == cell_1 then continue
for cell_3 = 1 to 16
if cell_3 == cell_2 or cell_3 == cell_1 then continue
etc.
- Another obvious thing to check is to make sure the cells you calculate the values for
are in the range 1 through 16. In other words, if you set cell_4 = 34 - cell_1 - cell_2 - cell_3,
then you want to check to make sure cell_4 is between 1 and 16, and that the value in cell_4
has not been used in cell_1, cell_2, or cell_3. If cell_4 is out of range, or a duplicate
value, then you can skip to the next number for cell_3.
- After you generate each possible combination, check to see if all the rows, all
the columns, and the two diagonals all sum to 34. If they do and the findSquares function
was passed true, then count and display the solution and the solution number. If the
findSquares function was passed false, then just count the solution.
- DO NOT WAIT UNTIL THE LAST MINUTE TO START THIS ASSIGNMENT.
- I look forward to answering your questions in class and via the discussion forum.
Sample output
Solution: 1
1 2 15 16
12 14 3 5
13 7 10 4
8 11 6 9
Solution: 2
1 2 15 16
13 14 3 4
12 7 10 5
8 11 6 9
Solution: 3
1 2 16 15
13 14 4 3
12 7 9 6
8 11 5 10
[numerous solutions omitted here to save space]
Solution: 7038
16 15 1 2
4 3 13 14
5 10 8 11
9 6 12 7
Solution: 7039
16 15 2 1
4 3 14 13
5 10 7 12
9 6 11 8
Solution: 7040
16 15 2 1
5 3 14 12
4 10 7 13
9 6 11 8