Practice Assignment

(magic.c)

Information

  1. For this practice assignment you will write a program that creates a magic square. From Wikipedia:
    "... a magic square is an N x N square grid (where N is the number of cells on each side) filled with distinct positive integers in the range 1, 2, . . . , N2 such that each cell contains a different integer and the sum of the integers in each row, column and diagonal is equal."

    Here's an example of a 5 x 5 magic square: 

       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
    If you add up all of the values in each row, column, and diagonal, you'll see that they all add up to 65. This is the magic sum for the magic square.

    This practice is programming project 8.17 on page 181 in the textbook. A brief description of the algorithm is as follows:

    Start by placing the number 1 in the middle of row 0. Place each of the remaining numbers 2, 3, ..., N2 by moving up one row and over (to the right) one column. Any attempt to go outside the bounds of the array should "wrap around" to the opposite side of the array. If a particular array element is already occupied, put the number directly below the previously stored number.
    This algorithm is known as the Siamese method or the De la Loubère method. From Wikipedia:

    As an example, here is a 3 x 3 array showing each move and how conflicts are resolved. The magic sum is 15:

    Move 1Move 2Move 3
    .    1    .
.    .    .
.    .    .

    .    1    .
.    .    .
.    .    2

    .    1    .
3    .    .
.    .    2

    Move 4Move 5Move 6
    .    1    .
3    .    .
4    .    2

    .    1    .
3    5    .
4    .    2

    .    1    6
3    5    .
4    .    2

    Move 7Move 8Move 9
    .    1    6
3    5    7
4    .    2

    8    1    6
3    5    7
4    .    2

    8    1    6
3    5    7
4    9    2
    Notice Move 4: From 3, you move up one row and over one column. Since this spot is already occupied, you put the number 4 one row below the number 3. A similar thing happens when placing the number 7.

    This is the prototype of the function that the driver will call: 

    int magic_square(int size, int showall);
    The input, showall, is a flag that determines if you should print all of the moves, instead of just the final square. The return value is the magic sum for the square. Put this function in a file named magic.c and build it with this command line: 
    gcc -O -Werror -Wall -Wextra -ansi -pedantic main.c magic.c -o magic
    Here is a simple driver file: (main.c, HTML Text) The program requires 2 command line parameters:

    1. The first parameter is the size of the square. It must be a positive, odd integer.
    2. The second parameter is an integer, either 0 or non-zero. This controls whether or not you should print every square or just the final square. A zero means just print the final square and any other integer means print all squares.

    Examples: (The text from the semi-colon on is just for descriptive purposes) 

    magic 5 0   ; Size is 5, just show the final square
magic 7 1   ; Size is 7, show all of the squares
magic 9     ; Size is 9, just show the final square (default)
magic       ; Size is 5 (default), just show final square (default)
    See the driver to see how it works.

    Here are some sample outputs. The number in the filename is the size of the square. If there is a letter a following the number, it means the file contains all the squares (for debugging purposes).

Notes:
  1. The value of N must be odd. For even-sized boards, a different algorithm is used. (We're not worried about that.)

  2. When coded correctly, the algorithm above will always work for odd sized squares. This means that if you have a collision and have to move down one row, that spot will always be open.

  3. There are many different magic squares of each size. However, your solution must match the output posted here. This means you must follow the algorithm that is posted.

  4. To print the numbers, use "%5i" as the format specifier to printf.

  5. You must dynamically allocate the 2D array. The array should hold integers, to allow very large squares. The only limitation for the size of the square is the amount of memory in the computer. Your program should be able to easily handle a 1001 x 1001 square and run in a fraction of a second. Of course, trying to print out a square of that size will be difficult to format so it can be read on the screen.

  6. You should initialize all of the array elements to 0. When printing, if the element is 0, you should print a period instead of the 0.

  7. By now, it should go without saying that you need to make some helper functions. Don't try to do the entire thing in the magic_square function.