UMBC CS 201,Fall 04
UMBC CMSC 201 Fall '04 CSEE | 201 | 201 F'04 | lectures | news | help

CMSC 201
Programming Project Four

Magic Squares

Out: Monday 11/15/04
Due Date: Monday 11/29/04, before midnight

The design document for this project, design4.txt, is due: Before Midnight, Sunday 11/21/04

The Objective

The purpose of this assignment is to give you practice with recursion, using command line arguments, using characters as menu responses, writing error messages to stderr and to do some more file handling and dynamic memory allocation. As always, you should continue to practice using top-down design and good implementation techniques.

The Background

According to The Math Forum @ Drexel University,

A Magic Square is an arrangement of the numbers 1 to n 2 in an n x n matrix with each number occuring exactly once, and such that the sum of the entries of any row, any column, or any main diagonal is the same. It is not hard to show that this sum is n(n2 + 1)/2

The simplest magic square is the 1 x 1 magic square whose only entry is the number 1.

 1 

The next simplest is the 3 x 3 magic square.

 8  1  6 
 3  5  7 
 4  9  2 

and those derived from it by symmetries of the square. This 3 x 3 square is definitely magic and satisfies the definition given above.

There are 8 different arrangements of entries in a 3 x 3 matrix that fit the definition of a magic square.

There are also magic squares of size 4 x 4, 5 x 5, etc.

There is a famous magic square known as the 4 x 4 Dürer Magic Square, which has all of the properties of a magic square and many other unique qualities. See the Math Forum website link above if you are interested.

For small n, say n <= 3, you could obviously sit down with pencil and paper and discover a magic square in a fairly short amount of time. Take a few minutes now and do that, remembering that each of the numbers, 1 through n2, appear only once in the square.

Now try it for n = 4 ...

Oh, there has to be a better way. :)

Of course, the computer doesn't have a patience problem. It can solve the problem for us by using the brute force method. This means that the computer will accomplish its task by trying every single possible arrangement of the numbers in a square and check each of the resulting squares to see if it's a magic square.

The Task

Your assignment will be to determine all of the magic squares for a specified n and either display them to the screen or write them to a file, whichever the user prefers.

It turns out that finding the magic squares for n >= 4 takes too long for us to run it on the shared machines (linux1, 2 & 3), so PLEASE restrict the user to n <= 3. Part of your assignment will be to estimate the running time for n = 4 based on the running time of your program when n = 3.

Your program must come up with every possible arrangement of numbers within the square. These are known as the permutations of that list of numbers. Each permutation needs to be checked to see if it has formed a magic square.

Program Requirements

Sample Run

Here is a link to the sample output of this program.

Please note that the sample output only shows what is expected from your program if the user is actually entering everything as instructed. This is not a test of the program at all, but just a sample for your clarification.

Submitting the Program

To submit your program, type the following command at the Unix prompt

submit cs201 Proj4 times.txt followed by the .c and .h files necessary for compilation

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj4


CSEE | 201 | 201 F'04 | lectures | news | help

Monday, 15-Nov-2004 13:36:16 EST