Magic square grid

The problem is to fill in a 3 by 3 grid with the numbers 1 through 9 such that the sum of each row, column, and diagonal is the same.

1 2 3 4 5 6 7 8 9

Note: This problem can be solved manually by trial and error or by clever use of mathematical deduction principles.

The approach used here is that of constraint logic permutation processing using a small computer program.

Warning: When working with permutations, one can generate a lot of output of one is not careful.

Use of debugging output and limit variables can help in getting the program started and working.

A simple way to model the logical 3 by 3 grid is with a physical 3 by 3 2D array.

#define ROWMAX 3
#define COLMAX 3
int square1[ROWMAX][COLMAX];

A change in "point of view" can often lead to a better and easier solution.

A change in perspective is worth 80 IQ points.
Perspective is worth 80 IQ points.
Point of view is worth 80 IQ points

Talk at Creative Think seminar, 20 July 1982. Alan Kay (originator/developer of object-oriented concepts)

Another way to model the logical 3 by 3 grid is with a physical 1D array of 9 elements. To use our permutation module, the permutation starts at position 1.

#define ROWMAX 3
#define COLMAX 3
#define DATAMAX ROWMAX*COLMAX
int square1[DATAMAX+1];
int squareCount1;
int permuteCount1;

Since digits from 1 to 9 are being permuted, we can use the array square1 as the permutation array.

There are times when a 2D array approach may be useful.

But in either case, when there is a wall to be avoided, sentinel data values can be added around the grid to make it easier to determine if the wall has been hit. The sentinel data values are added all round so that a ROWMAX by COLMAX 2D array becomes a ROWMAX+2 by COLMAX+2 array.

The simple brute force approach used here is that of generating every permutation of the numbers 1 to 9 in the 3 by 3 grid and checking to see if the constraints are met.

The following procedure showDo1 will show the grid.

void showDo1() {
	int pos1;
	pos1 = 0;
	for (int rpos1=0; rpos1 < ROWMAX; rpos1++) {
		printf("\t");
		for (int cpos1=0; cpos1 < COLMAX; cpos1++) {
			pos1++;
			printf("%2d",square1[pos1]);
			}
		printf("\n");
		}
	}

In many games, the positions and contents of the grid needs to be displayed on a regular basis.

A data driven approach is used to check that the sum of the rows, columns, and diagonals match.

#define MATCHMAX 8

int match1[MATCHMAX][COLMAX] = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },
	{ 0, 3, 6 },
	{ 1, 4, 7 },
	{ 2, 5, 8 },
	{ 0, 4, 8 },
	{ 2, 4, 6 }
	};

Note: The criteria here uses a zero-based numbering scheme. The square1 array uses a one-based numbering scheme (to fit the permutation code previously developed). This is not a problem as long as the programmer accounts for the differences.

Such issues, if not handled properly, result it the common "off by one" errors in programming.

The following function sumDo1 will sum three cells of the permutation and return the result.

int sumDo1(int *cells1) {
	int sum1 = 0;
	for (int pos1=0; pos1 < COLMAX; pos1++) {
		sum1 += square1[cells1[pos1]+1];
		}
	return sum1;
	}

Think of indirection array cells1 as being the diagonal in the match1 list (position 6) from upper left to center to lower right in the square1 grid (as a 1D array).

{ 0, 4, 8}

The action procedure actionDo1 checks if the permutation meets the match criteria. If so, the square is displayed using showDo1.

void actionDo1() {
	int sum1;
	int sum2;
	permuteCount1++;
	sum1 = sumDo1(match1[0]);
	for (int mpos1=1; mpos1 < MATCHMAX; mpos1++) {
		sum2 = sumDo1(match1[mpos1]);
		if (sum2 != sum1) {
			return;
			}
		}
	squareCount1++;
	printf("\n");
	printf("%d:\n",squareCount1);
	showDo1();
	}

Here then is the main function.

printf("Magic squares:\n");
permuteCount1 = 0;
squareCount1 = 0;
permute0(square1,DATAMAX,actionDo1);
printf("\n");
printf("Checked %d permutations.\n",permuteCount1);

The function actionDo1is passed to function permute0 as a "callback" function.

Here is the C code.

#include <stdio.h>
#include "rsPermute.h"

#define ROWMAX 3
#define COLMAX 3
#define DATAMAX ROWMAX*COLMAX
int square1[DATAMAX+1];
int squareCount1;
int permuteCount1;

#define MATCHMAX 8

int match1[MATCHMAX][COLMAX] = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },
	{ 0, 3, 6 },
	{ 1, 4, 7 },
	{ 2, 5, 8 },
	{ 0, 4, 8 },
	{ 2, 4, 6 }
	};

int sumDo1(int *cells1) {
	int sum1 = 0;
	for (int pos1=0; pos1 < COLMAX; pos1++) {
		sum1 += square1[cells1[pos1]+1];
		}
	return sum1;
	}

void showDo1() {
	int pos1;
	pos1 = 0;
	for (int rpos1=0; rpos1 < ROWMAX; rpos1++) {
		printf("\t");
		for (int cpos1=0; cpos1 < COLMAX; cpos1++) {
			pos1++;
			printf("%2d",square1[pos1]);
			}
		printf("\n");
		}
	}

void actionDo1() {
	int sum1;
	int sum2;
	permuteCount1++;
	sum1 = sumDo1(match1[0]);
	for (int mpos1=1; mpos1 < MATCHMAX; mpos1++) {
		sum2 = sumDo1(match1[mpos1]);
		if (sum2 != sum1) {
			return;
			}
		}
	squareCount1++;
	printf("\n");
	printf("%d:\n",squareCount1);
	showDo1();
	}

int main() {
	printf("Magic squares:\n");
	permuteCount1 = 0;
	squareCount1 = 0;
	permute0(square1,DATAMAX,actionDo1);
	printf("\n");
	printf("Checked %d permutations.\n",permuteCount1);
	return 0;
	}

Here is the output. Notice the symmetry of the solutions. There is only one unique solution after rotations, reflections, etc.

Here is the output of the C code.

Magic squares:

1:
	 2 7 6
	 9 5 1
	 4 3 8

2:
	 2 9 4
	 7 5 3
	 6 1 8

3:
	 4 3 8
	 9 5 1
	 2 7 6

4:
	 4 9 2
	 3 5 7
	 8 1 6

5:
	 6 1 8
	 7 5 3
	 2 9 4

6:
	 6 7 2
	 1 5 9
	 8 3 4

7:
	 8 3 4
	 1 5 9
	 6 7 2

8:
	 8 1 6
	 3 5 7
	 4 9 2

Checked 362880 permutations.

Here are some useful future additions to the above program, for development purposes.

A variable can be used to limit how many magic squares are output and then, if encountered, only output that message once. This is not an issue above, but in new problems, one wants to avoid the problem of having huge numbers of grids output.