Magic squares (inspired by problem P6.19 from Horstmann)
(You may find the file we looked at last Wednesday to be helpful as well.)
An n-by-n array filled with the numbers 1, 2, 3, ..., n2 is a magic square if the sum of the elements in each row, column, and the two diagonals is the same value. For example:
You can check that all row sums, column sums, and diagonal sums are equal to 34. Check your understanding: what is the "magic number" for an n-by-n magic square?
Write a program that reads in 16
int values from a file and tests whether they form a magic square when put into a 4-by-4 array (sample file provided, keep reading). You need to test two properties:
- Does each of the numbers 1, 2, 3, 4, ..., 16 occur in the list of values?
- When the numbers are put into a square, are the sums of the rows, columns, and diagonals all equal to one another?
This is easiest if you use a 2-dimensional table. Use a vector of vectors for this purpose: that is, store your values in a
vector< vector<int> >.
Use the provided code scaffold, and submit your code in a program called
magic_squares.cpp. Practice the technique of using functions to perform different parts of your procedure and calling those functions within the
Here are some hints to keep in mind while you work on this assignment.
- Remember our motto: "when in doubt,
cout". Use trace statements invoking
cout to help you debug. For example, you could put them in your loops to show what is happening during each iteration of a loop. Of course you will remove all these after your program works correctly.
- Use the algorithms described elsewhere in Chapter 6 (and in other parts of the book) to help you solve the subproblems. Have you reread Chapter 6? All of it? If you are stuck, now might be a good time to revisit it.
- You might need to think for a bit about how to check for the correct entries (that is, that the user enters each value from 1 through n2 exactly once). Use the techniques in Chapter 6.5 to help yourself think about it. There are a few different ways.
- Don't use "magic numbers": in particular, the size of the magic square. You should give it an ALL CAPS identifier and use that identifier exclusively in your code. Write all your functions to use this variable instead of the literal constant. Use the following rule: no integer literals allowed except 0, 1, and 2.
- Use the
main function as a "driver" program to test your code. As you write the function bodies provided in the scaffold, add code to
main that will make sure they are working properly. As you complete the program, you can update or replace the test code in
main with its final form.
You can download two files here: the first one contains four magic squares, and the second one contains a few non-magic squares. (The easiest way to use different squares is to edit these files and reorder the lines, since your program is going to be written just to use the first line of such a file.)