Magic square

• Create a two dimensional array
• Process a two dimensional array
• Optimize program execution time by analyzing and improving the algorithm used

This assignment involves writing 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.

• 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 function 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 16⁹ 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, during office hours, or by email.

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

• (5 pts) Documentation comments and style conventions followed.
• (5 pts) The findSquares function follows specified requirements.
• (10 pts) The 2-D array is created and used properly.
• (20 pts) All solutions found with no incorrect solutions listed.
• (5 pts) The program is not only correct, but runs in less than five minutes on kermit.
• (5 pts) The program is not only correct, but runs in less than two minutes on kermit.