/* * Author: Dr Peter Dickman * Created: 2nd February 2001 * * This program was written to supplement my magic square * generator, it's purpose is to determine possible layouts * of numbers in a 3x3 grid that could potentially lead to * a magic square. * * (c) 2001 University of Glasgow * All Rights Reserved * */ #include #include /* A potential magic square is a 3x3 grid in which nine distinct * numbers are placed in such a way that, when considered simply * as an ascending sequence, there are no two triples in which it * is impossible for them to be equal. * i.e. I'm trying to eliminate grids in which, for example, one * triple contains the three least numbers and another the three * greatest (v1+v2+v3 < v7+v8+v9) */ /* Symmetry arguments are used to reduce the number of grids to * consider, in particular if the grid positions are: * * G1 G2 G3 * G4 G5 G6 * G7 G8 G9 * * then the greatest value, v9, must be in position G1, G2 or G5 (symmetry) * * with v9 in G5, v8 must go in G1 or G2 (symmetry) * but neither is possible as v8->G1 => G9+G8+G7 < G9+G5+G1 * and v8->G2 => G9+G8+G7 < G8+G5+G2 * * similar arguments lead us to: * v9 in G1 => v8 in G6 and v7 in one of G7 or G8 * v9 in G2 => either v8 in G4 and v7 in G9 * or v8 in G7 and v7 in one of G6 or G9 */ /* Basic approach: for each of the v9, v8, v7 allowed combinations, * generate all possible positions for v1..v6 and test for legality. * * To test for a valid square, find all eight allowed triples * (tA,tB,tC) in ascending order and check that we never get a * clean interleaving (where t1A triples[i].y) \ { \ tmp = triples[i].x; \ triples[i].x = triples[i].y; \ triples[i].y = tmp; \ } \ if (triples[i].y > triples[i].z) \ { \ tmp = triples[i].y; \ triples[i].y = triples[i].z; \ triples[i].z = tmp; \ if (triples[i].x > triples[i].y)\ { \ tmp = triples[i].x; \ triples[i].x = triples[i].y; \ triples[i].y = tmp; \ } \ } #define CONSTRUCTTRIPLE(i, a,b,c) triples[i].x = positions[a-1];\ triples[i].y = positions[b-1];\ triples[i].z = positions[c-1];\ SORTTRIPLE(i) int validate_potential_square(int positions[9]) { /* There are eight potential triples to consider */ /* (1,2,3) (4,5,6) (7,8,9) (1,4,7) (2,5,8) (3,6,9) (1,5,9) (3,5,7) */ /* We construct all eight triples and sort them (this isn't efficient) */ /* then do the comparisons afterwards....... */ int tmp; struct triple triples[8]; #ifdef DEBUG printf("Constructing triples from: "); print_positions(positions); printf("\n"); #endif CONSTRUCTTRIPLE(0, 1,2,3); CONSTRUCTTRIPLE(1, 4,5,6); CONSTRUCTTRIPLE(2, 7,8,9); CONSTRUCTTRIPLE(3, 1,4,7); CONSTRUCTTRIPLE(4, 2,5,8); CONSTRUCTTRIPLE(5, 3,6,9); CONSTRUCTTRIPLE(6, 1,5,9); CONSTRUCTTRIPLE(7, 3,5,7); return validate_triples(triples); } int generate_potential_squares_contd(int positions[9]) { /* We'll place the values in descending order..... */ /* NB: Inefficient, but it'll do for now.... */ int count = 0; int place1, place2, place3, place4, place5, place6; for (place6=0; place6<9; place6++) if (positions[place6]==0) { positions[place6]=6; for (place5=0; place5<9; place5++) if (positions[place5]==0) { positions[place5]=5; for (place4=0; place4<9; place4++) if (positions[place4]==0) { positions[place4]=4; for (place3=0; place3<9; place3++) if (positions[place3]==0) { positions[place3]=3; for (place2=0; place2<9; place2++) if (positions[place2]==0) { positions[place2]=2; for (place1=0; place1<9; place1++) if (positions[place1]==0) { positions[place1]=1; if (validate_potential_square(positions)) { count++; printsquare(positions); } positions[place1]=0; } positions[place2]=0; } positions[place3]=0; } positions[place4]=0; } positions[place5]=0; } positions[place6]=0; } return count; } int generate_magic_squares(void) { int i; int count = 0; int positions[9]; for (i=0; i<9; i++) positions[i]=0; positions[0]=9; positions[5]=8; positions[6]=7; count += generate_potential_squares_contd(positions); for (i=0; i<9; i++) positions[i]=0; positions[0]=9; positions[5]=8; positions[7]=7; count += generate_potential_squares_contd(positions); for (i=0; i<9; i++) positions[i]=0; positions[1]=9; positions[3]=8; positions[8]=7; count += generate_potential_squares_contd(positions); for (i=0; i<9; i++) positions[i]=0; positions[1]=9; positions[6]=8; positions[5]=7; count += generate_potential_squares_contd(positions); for (i=0; i<9; i++) positions[i]=0; positions[1]=9; positions[6]=8; positions[8]=7; count += generate_potential_squares_contd(positions); return count; } /*========================================================================*/ int main (int argc, char* argv[]) { int count; printf("\n\nThe Magic Square Layout Explorer\n"); printf("(c) 2001 Peter Dickman & University of Glasgow\n\n"); printf("Finds potential layouts for magic squares\n"); printf("\nGenerating magic square layouts...\n"); count = generate_magic_squares(); printf(" ...%d magic square layouts generated.\n\n", count); exit (EXIT_SUCCESS); }