(TITLE IDENTIFYING MAGIC SQUARES)

INTRODUCTION

An nth-order magic square is an n x n array of the integers from 1 to n2 in which the sums of the rows, the columns, and the two diagonals are all the same. For example, the array on the left is a third-order magic square; in it, each row, column, and diagonal sums to 15. Similarly, the array on the right is a fourth-order magic square; each sum is 34.

2 7 6 9 5 1 4 3 8 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 In general, the sum of each row, column, and diagonal of an nth-order magic square is n(n2 + 1) / 2. (Can you prove this? Hint: Consider the sum of the first n2 integers.)

DESCRIPTION

Design, implement, document, and test a C++ program that reads a square matrix of integers from a data file and reports whether or not the matrix is a magic square. INPUT The program will read the name of a data file from the terminal and the dimension n of a square matrix and its elements from the named file. A data file might look like this: 4 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 You may assume that no input matrix is larger than 10 x 10.

OUTPUT

The program will prompt for the name of the input file and write to the terminal the matrix being tested and whether or not it is a magic square. The program will write all output to the terminal.

ERRORS

The program may assume the input is as described; it need not detect any errors.

EXAMPLE

Several runs of the program might look like this: csh> magic Enter input file name: sq4a.dat The matrix 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 IS an order-4 magic square. Each value appears once, and its rows, columns, and diagonals sum to 34. csh> magic Enter input file name: sq3d.dat The matrix 1 6 8 9 2 4 5 7 3 is NOT a magic square. csh> magic Enter input file name: sq5a.dat The matrix 22 3 9 15 16 14 20 21 2 8 1 7 13 19 25 18 24 5 6 12 10 11 17 23 4 IS an order-5 magic square. Each value appears once, and its rows, columns, and diagonals sum to 65.

OTHER REQUIREMENTS Represent the candidate matrix in a two-dimensional array. Use functions to: (1) open the input file; (2) read a matrix in; (3) test if a matrix contains each of the values from 1 to n2 exactly once; and (4) test if the rows, columns, and diagonals of a matrix sum to the appropriate value (several functions); (5) write out a matrix.

HINTS A square matrix must satisfy two conditions to be a magic square: Its rows, columns, and diagonals must sum to n(n2 + 1) / 2, and each integer from 1 to n2 must appear exactly once. To check if each value from 1 to n2 occurs exactly once in the matrix, use a one-dimensional array to keep track of how often each value occurs. Only if all the values are in the specified range and all the counts are 1 can the matrix be a magic square. Be sure to check for values out of the required range before using them as indexes into this array.