CS1101C Practical Exam

Session 4 (1600 - 1745 hours)

Magic Square

The deadline for this lab is Wednesday 15 November 2006, 17:45:59 hours. Strictly no submissions will be accepted after the deadline.

Background

8 1 6
3 5 7
4 9 2

Constructing a magic square of odd order

The following describes one method for constructing a magic square of odd order. We always start off with the cell at the central column of the top row with the number 1. The basic movement for filling each subsequent cell is to move diagonally UP and RIGHT, one step at a time. If a filled cell is encountered, then we move vertically DOWN, and continue as before. When a certain move leaves the grid, it is wrapped around to the other side. The following details each individual step for a magic square of order 3. A dot denotes a blank cell.

Place the number 1 at the central column of the first row.

. 1 .
. . .
. . .

Moving diagonally UP and RIGHT (denoted by X) would result in a movement outside the square.

    X
. 1 .
. . .
. . .

Since we wrap around the top and bottom of the square, the X is "wrapped" to the bottom right hand corner.

. 1 .
. . .
. . X

We fill this cell with the next number, i.e. 2.

. 1 .
. . .
. . 2

Again moving diagonally up and right results in X outside the grid.

. 1 .
. . . X
. . 2

Wrapping around X and filling in the number 3 results in

. 1 .
3 . .
. . 2

Now moving diagonally UP and RIGHT, we encounter a cell with the number 1. So we take the alternative route and move DOWN instead.

. 1 .
3 . .
X . 2

Since it is available, we fill it with 4.

. 1 .
3 . .
4 . 2

Using the diagonal moves UP and RIGHT, we can fill the next two numbers.

. 1 6
3 5 .
4 . 2

The next diagonal move is again outside the square.

      X
. 1 6
3 5 .
4 . 2

Wrapping around X we encounter a cell with the number 4. So we move vertically down instead, and fill with the number 7.

. 1 6
3 5 7
4 . 2

Continue with the two basic movements, wrapping around when necessary, and we get the eventual result.

8 1 6
3 5 7
4 9 2

Finally, here is the magic square of order 5 constructed using the above methodology.

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

The Task

1. Read a text file containing the magic square of a given order. An example of the text file is shown below.

   3
   0  0 -1
   0  0  0
   0  0  0
   

   The first number at the beginning of the file is the order of the magic square. This is followed by the magic square which will contain a value of -1 in one of the cells. This value signifies the last position to be filled.

2. Fill the magic square from the first number 1 to the last number (in this case 6).

   . 1 6
   3 5 .
   4 . 2
   

3. Sum up the rows, columns and the two diagonals based on the currently filled square.

4. Print out the square, including all the sums as follows.

                 15  // sum of the top-right to bottom-left (RL) diagonal
      .   1   6   7  // sum of the first row
      3   5   .   8  // sum of the second row
      4   .   2   6  // sum of the third row
      7   6   8   7  // sums of each column followed by the top-left to bottom-right (LR) diagonal
   

Assumptions

• The magic square is always of odd order and not exceeding 9.
• The text file is always magic.txt and it has been copied into your directory by the pesetup command.
• All data in a given text file are within the range of permissible values, so there is no need to perform any explicit range checking on them.

Program Specifications

#include <stdio.h>

#define MAX      9            // The largest magic square is of order 9.
#define FILENAME "magic.txt" // Filename to be read

int main(void)
{
   int square[MAX][MAX] = {{0}},
       rowSum[MAX] = {0},
       colSum[MAX] = {0};
   int sumLR = 0, sumRL = 0, order;

   order = ReadSquare(square);

   if (order)
   {
      FillSquare(square, order);
      SumSquare(square, rowSum, colSum, &sumLR, &sumRL, order);
      DisplaySquare(square, rowSum, colSum, sumLR, sumRL, order);
   }

   return 0;
}

Details of each function implementation are as follows:

ReadSquare(square)

Function ReadSquare will perform all file I/O within the function and initialize the 2D array square with the starting magic square as read from the given magic.txt file. The function returns the order of the magic square. In the case of an error encountered during file processing, it prints the message "Error opening file." and returns a value of 0.

FillSquare(square, order)

Function FillSquare fills in the magic square square of order order with numbers from 1 until the terminating position (the one with the -1 value) inclusive.

SumSquare(square, rowSum, colSum, &sumLR, &sumRL, order)

Function SumSquare produces the sum of rows, columns and diagonals of the given magic square. The row and column sums are stored in the arrays rowSum and colSum respectively (with rowSum[0] and colSum[0] assigned with the sums of the topmost row and leftmost column). sumLR denotes the sum of the top-left to bottom-right diagonal, while sumRL denotes the sum of the top-right to bottom-left diagonal.

DisplaySquare(square, rowSum, colSum, sumLR, sumRL, order)

Function DisplaySquare will perform all the necessary output.

In addition to the above functions, you are encouraged to write other functions, if necessary, to enhance the modularity of your program design.

When you submit your program, you are to ensure that the main function given above is in place. You are NOT allowed to modify the main function in any way. Therefore, it is important that you follow all function specifications exactly.

Sample Run

$ gcc -Wall magic.c
$ cat magic.txt
3
0  0 -1
0  0  0
0  0  0
$ a.out
              15
   .   1   6   7
   3   5   .   8
   4   .   2   6
   7   6   8   7

Another sample run with a different order 3 magic square.

$ cat magic.txt
3
 0  0  0
-1  0  0
 0  0  0
$ a.out
               0
   .   1   .   1
   3   .   .   3
   .   .   2   2
   3   1   2   2

A full magic square.

$ cat magic.txt
3
0  0  0
0  0  0
0 -1  0
$a.out
              15
   8   1   6  15
   3   5   7  15
   4   9   2  15
  15  15  15  15

A minimal magic square.

$ cat magic.txt
3
0 -1  0
0  0  0
0  0  0
$ a.out
               0
   .   1   .   1
   .   .   .   0
   .   .   .   0
   0   1   0   0

And our final sample run

$ cat magic.txt
9
0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  0 -1  0  0  0  0
$ a.out
                                     369
  47  58  69  80   1  12  23  34  45 369
  57  68  79   9  11  22  33  44  46 369
  67  78   8  10  21  32  43  54  56 369
  77   7  18  20  31  42  53  55  66 369
   6  17  19  30  41  52  63  65  76 369
  16  27  29  40  51  62  64  75   5 369
  26  28  39  50  61  72  74   4  15 369
  36  38  49  60  71  73   3  14  25 369
  37  48  59  70  81   2  13  24  35 369
 369 369 369 369 369 369 369 369 369 369

You are reminded to follow the sample output exactly; else marks will be deducted.

Do not use any structures in your program, else no credit will be given.

Remember to submit your program using the submit magic.c command, and check your submission using the check command.

All the best!

UNIX commands

1. “dir”: lists all the files in the directory.
2. “cp a.txt b.txt”: copies a.txt to b.txt.
3. “mv a.txt b.txt”: moves / renames a.txt to b.txt.
4. “cat a.txt”: shows the contents of a.txt.