From: rogers@rosencrantz.osf.org (Andrew Rogers)
Subject: Re: C solution to Magic Square
Organization: HICAM/OSD
Distribution: na
Date: Mon, 28 Sep 1992 14:47:12 GMT

In article <1992Sep25.204431.11470@newshub.ccs.yorku.ca> landolt@nexus.yorku.ca (Paul Landolt) writes:
>My question is: Is there a simple(r) mathematical method of solving the
>magic square for any size? Anyone? Any ideas? Has anyone seen C source that
>will do this?

The following code is a C version of an Algol program published about 30
years ago:

Andrew Rogers
HICAM/OSD

------------------------------------------------------------------------


/*
 * Magic square program - generates magic squares, even or odd, of orders 3 - 30
 *
 * Based on algorithms 117 and 118 from _Collected Algorithms from CACM_.  Even
 * square algorithm (117) is itself based on the method of Devedec as described
 * in _Mathematical Recreations_ by M. Kraitchik; odd square algorithm (118) is
 * basically the one everybody learned in junior high.  Translated from Algol to
 * C by A. W. Rogers, 1990; note that arrays are still 1-based as in the
 * original.
 *
 *  input:  order(s) of desired square(s), specified as command-line arguments
 *  output: magic square(s), to stdout
 *
 * Compiling with the symbol VERIFY #define'd includes code which checks the
 * generated squares for correctness.
 */

#define MIN	3			/* minimum, maximum orders */
#define MAX	30

typedef enum { FALSE, TRUE } BOOL;	/* pseudo-boolean type */

int n;					/* order of magic square */
int nn; 				/* order, squared */
int x[MAX+1][MAX+1];			/* array where squares generated */



/* alpha, beta, gamma are routines used by even_sq() */

alpha(min_row, max_row, col, flag)
	int min_row, max_row, col;
	BOOL flag;
{
	int row;

	for (row = min_row; row <= max_row; row++, flag = !flag)
		x[row][col] = flag ? (col - 1) * n + row :
				     nn - (col - 1) * n - row + 1;
}

beta(min_row, max_row, col, flag)
	int min_row, max_row, col;
	BOOL flag;
{
	int row;

	for (row = min_row; row <= max_row; row++, flag = !flag)
		x[row][col] = flag ? nn - col * n + row :
				     col * n - row + 1;
}

gamma(min_row, max_row, col, flag)
	int min_row, max_row, col;
	BOOL flag;
{
	int row;

	for (row = min_row; row <= max_row; row++, flag = !flag)
		x[row][col] = flag ? nn - (col - 1) * n - row + 1 :
				     col * n - row + 1;
}

/*
 * generate even magic square of order 'n'
 */
even_sq()
{
	int row, col, n2;
	BOOL divby4, flag1, flag2;

	n2 = n / 2;
	divby4 = n % 4 == 0;

	/* fill in left columns */

	for (flag1 = !divby4, flag2 = TRUE, col = 1;
	     col <= n2 - 1;
	     col++, flag1 = !flag1, flag2 = !flag2) {
		beta(1, col - 1, col, flag2);
		alpha(col, n2 - 1, col, TRUE);
		x[n2][col] = nn - col * n + n2 + (flag1 ? 0 : 1);
		alpha(n2 + 1, n, col, flag1);
	}

	/* fill in center two columns (except center two rows) */

	alpha(1, n2 - 1, n2, !divby4);
	alpha(n2 + 2, n, n2, FALSE);
	gamma(1, n2 - 1, n2 + 1, divby4);
	gamma(n2 + 2, n, n2 + 1, flag1);

	/* fill in right columns */

	for (flag1 = divby4, flag2 = FALSE, col = n2 + 2;
	     col <= n;
	     col++, flag1 = !flag1, flag2 = !flag2) {
		beta(1, n - col, col, flag1);
		x[n - col + 1][col] = (n - 1) * col + 1;
		beta(n - col + 2, n2 - 1, col, TRUE);

		x[n2][col] = flag2 ? nn - col * n + n2 :
				     nn - (col - 1) * n - n2 + 1;
		x[n2 + 1][col] = flag2 ? col * n - n2 + 1 :
					 nn - (col - 1) * n - n2;

		beta(n2 + 2, col - 1, col, flag2);
		alpha(col, n, col, TRUE);
	}

	/* fill in center four squares */

	for (row = n2; row <= n2 + 1; row++)
		for (col = n2; col <= n2 + 1; col++)
			alpha(row, row, col, divby4);

	/* additional housekeeping */

	if (!divby4) {
		for (col = n2; col <= n2 + 1; col++)
			x[n2 - 1][col] = col * n - n2 + 2;
		for (row = n2; row <= n2 + 1; row++)
			x[row][n2 + 2] = (n2 - 2) * n + row;
	}

}


/*
 * generate even magic square of order 'n'
 */
odd_sq()
{
	int row, col, num;

	row = 1;			/* start at top center */
	col = (n + 1) / 2;

	for (num = 1; num <= nn; num++) {	/* fill in numbers 1 .. n*n */
		x[row][col] = num;
		if (num % n == 0)
			row++;			/* drop down one row */
		else {
			/* move up/right (with wraparound) */
			row = row == 1 ? n : row - 1;
			col = col == n ? 1 : col + 1;
		}
	}

}

#ifdef VERIFY
verify()
{
	int i, j, sum1, sum2, expsum;
	int cnt[MAX*MAX+1];

	expsum = ((n * n * n) + n) / 2; 	/* expected sum */

	for (i = 1; i <= n; i++) {		/* check rows and columns */
		sum1 = sum2 = 0;
		for (j = 1; j <= n; j++) {
			sum1 += x[i][j];
			sum2 += x[j][i];
		}
		if (sum1 != expsum)
			printf("Bad sum, row %d = %d\n", i, sum1);
		if (sum2 != expsum)
			printf("Bad sum, col %d = %d\n", i, sum2);
	}

	sum1 = sum2 = 0;			/* check diagonals */
	for (i = 1; i <= n; i++) {
		sum1 += x[i][i];
		sum2 += x[i][n-i+1];
	}
	if (sum1 != expsum)
		printf("Bad sum, diag %d = %d\n", 1, sum1);
	if (sum2 != expsum)
		printf("Bad sum, diag %d = %d\n", 2, sum2);
}
#endif

/*
 * print magic square of order 'n', in array 'x'
 */
print_sq()
{
	int i, j;

#ifdef VERIFY
	verify();
#endif

	printf("\n");
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			printf("%4d%c", x[i][j], j == n ? '\n' : ' ');

	printf("\n    The sum of any row, column, or diagonal is %d\n\n",
		((n * n * n) + n) / 2);

}


main(argc, argv)
	int argc;
	char **argv;
{
	extern int atoi();

	while (*++argv) {		/* loop through command-line args */
		n = atoi(*argv);
		if (n >= MIN && n <= MAX) {
			nn = n * n;
			n % 2 ? odd_sq(n) : even_sq(n); /* call routine */
			print_sq(n);
		}
	}

}
Newsgroups: comp.lang.c