/*
 * 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 <stdio.h>
#include <stdlib.h>

/* 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<t2A, t1B<t2B, t1C<t2C) that means
 * it's guaranteed not to be a magic square.
 *
 * In generating the squares, we use 0 to represent an unfilled slot
 * and n to indicate that vn is in that slot.
 */

/*========================================================================*/

void printsquare(int pos[9])
{
    printf("There may be magic squares structured as follows:\n\n");
    printf("  %6d  %6d  %6d\n  %6d  %6d  %6d\n  %6d  %6d  %6d\n\n",
       pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7], pos[8]);
    printf("(Numbers indicate the ascending sequence of values)\n\n");
}


struct triple { int x,y,z; };

void print_triples (struct triple triples[8])
{
  int i;
  for (i=0; i<8; i++)
      printf("(%d,%d,%d) ", triples[i].x, triples[i].y, triples[i].z);
}

void print_positions (int pos[9])
{
    printf("[%d,%d,%d,%d,%d,%d,%d,%d,%d]", 
	   pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], 
	   pos[6], pos[7], pos[8]); 
}


#define BROKENTEST(i,j) ((triples[i].x <= triples[j].x) &&    \
                         (triples[i].y <= triples[j].y) &&    \
                         (triples[i].z <= triples[j].z))

#define BROKEN(i,j) ((BROKENTEST(i,j)) || (BROKENTEST(j,i)))

int validate_triples(struct triple triples[8])
{
   int i,j;

#ifdef DEBUG
   printf("Validating triples:\n");
   print_triples(triples);
   printf("\n");
#endif

   for (i=0; i<7; i++)
       for (j=i+1; j<8; j++)
	   if (BROKEN(i,j)) return 0;

   return 1;
}


#define SORTTRIPLE(i) if (triples[i].x > 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);
}