//
//magicStarClever.c
//An algorithm to find all the solutions of the Order 8a Magic Star puzzle, quickly.
//Written by Heath Raftery, 2006
//Email: heath@hrsoftworks.net Web: http://heath.hrsoftworks.net
//
//This work is licensed under the Creative Commons Attribution 2.5 License.
//To view a copy of this license, visit http://creativecommons.org/licenses/by/2.5/
//or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
//San Francisco, California, 94105, USA.
//

#include <stdio.h>

#define SUM 34
#define N   16

int isUniqueArray(int a[], int size, int index);
int getNextPermutation(int array[], int size, int max);
void incrementDigitUntilUnique(int array[], int index);

int main(int argc, char *argv[])
{
  long long int iteration;
  int solution=0;
  int index, count;

//star looks like this:
//          e
//    a   b   c   d
//    f           p
// g                 o
//    h           n
//    i   j   l   m
//          k
//solutions are:
//0. abcd = 0 1 2 3
//1. ebfg = 4 1 5 6
//2. afhi = 0 5 7 8
//3. ghjk = 6 7 9 10
//4. ijlm = 8 9 11 12
//5. klno = 10 11 13 14
//6. mnpd = 12 13 15 3
//7. opce = redundant

  int *sol[7][4];  //these will point to values in the val array
  int val[N];  //these represent values in position a, b, c, d, ..., p
  sol[0][0] = &val[0]; sol[0][1] = &val[1]; sol[0][2] = &val[2]; sol[0][3] = &val[3];
  sol[1][0] = &val[4]; sol[1][1] = &val[1]; sol[1][2] = &val[5]; sol[1][3] = &val[6];
  sol[2][0] = &val[0]; sol[2][1] = &val[5]; sol[2][2] = &val[7]; sol[2][3] = &val[8];
  sol[3][0] = &val[6]; sol[3][1] = &val[7]; sol[3][2] = &val[9]; sol[3][3] = &val[10];
  sol[4][0] = &val[8]; sol[4][1] = &val[9]; sol[4][2] = &val[11]; sol[4][3] = &val[12];
  sol[5][0] = &val[10]; sol[5][1] = &val[11]; sol[5][2] = &val[13]; sol[5][3] = &val[14];
  sol[6][0] = &val[12]; sol[6][1] = &val[13]; sol[6][2] = &val[15]; sol[6][3] = &val[3];

  //Loop1 - searching for abcd
  for(val[0] = 1, val[1] = 2, val[2] = 3, val[3] = 4, iteration=1; val[0]<=N; getNextPermutation(&val[0], 4, N), iteration++)
  {
    int reachedEndOfLoop1 = 0;
    while(*sol[0][0]+*sol[0][1]+*sol[0][2]+*sol[0][3] != SUM)
      if(!getNextPermutation(&val[0], 4, N))
      {
	reachedEndOfLoop1 = 1;
	break;
      };
    if(reachedEndOfLoop1)
      break;
    
    //Loop2 - searching for efg
    for(val[4] = 1, val[5] = 2, val[6] = 3; val[4]<=N; getNextPermutation(&val[4], 3, N))
    {
      int reachedEndOfLoop2 = 0;
      while(!isUniqueArray(val, 3, 4) || *sol[1][0]+*sol[1][1]+*sol[1][2]+*sol[1][3] != SUM)
	if(!getNextPermutation(&val[4], 3, N))
	{
	  reachedEndOfLoop2 = 1;
	  break;
	};
      if(reachedEndOfLoop2)
	break;

      //Loop3 - searching for hi
      for(val[7] = 1, val[8] = 2; val[7]<=N; getNextPermutation(&val[7], 2, N))
      {
	int reachedEndOfLoop3 = 0;
	while(!isUniqueArray(val, 2, 7) || *sol[2][0]+*sol[2][1]+*sol[2][2]+*sol[2][3] != SUM)
	  if(!getNextPermutation(&val[7], 2, N))
	  {
	    reachedEndOfLoop3 = 1;
	    break;
	  };
	if(reachedEndOfLoop3)
	  break;
	
	//Loop4 - searching for jk
	for(val[9] = 1, val[10] = 2; val[9]<=N; getNextPermutation(&val[9], 2, N))
	{
	  int reachedEndOfLoop4 = 0;
	  while(!isUniqueArray(val, 2, 9) || *sol[3][0]+*sol[3][1]+*sol[3][2]+*sol[3][3] != SUM)
	    if(!getNextPermutation(&val[9], 2, N))
	    {
	      reachedEndOfLoop4 = 1;
	      break;
	    };
	  if(reachedEndOfLoop4)
	    break;

	  //Loop5 - searching for lm
	  for(val[11] = 1, val[12] = 2; val[11]<=N; getNextPermutation(&val[11], 2, N))
	  {
	    int reachedEndOfLoop5 = 0;
	    while(!isUniqueArray(val, 2, 11) || *sol[4][0]+*sol[4][1]+*sol[4][2]+*sol[4][3] != SUM)
	      if(!getNextPermutation(&val[11], 2, N))
	      {
		reachedEndOfLoop5 = 1;
		break;
	      };

	    if(reachedEndOfLoop5)
	      break;

	    //Loop6 - searching for no
	    for(val[13] = 1, val[14] = 2; val[13]<=N; getNextPermutation(&val[13], 2, N))
	    {
	      int reachedEndOfLoop6 = 0;
	      while(!isUniqueArray(val, 2, 13) || *sol[5][0]+*sol[5][1]+*sol[5][2]+*sol[5][3] != SUM)
		if(!getNextPermutation(&val[13], 2, N))
		{
		  reachedEndOfLoop6 = 1;
		  break;
		};
	      if(reachedEndOfLoop6)
		break;

	      //Loop7 - searching for p
	      for(val[15] = 1; val[15]<=N; getNextPermutation(&val[15], 1, N))
	      {
		int reachedEndOfLoop7 = 0;
		while(!isUniqueArray(val, 1, 15) || *sol[6][0]+*sol[6][1]+*sol[6][2]+*sol[6][3] != SUM)
		  if(!getNextPermutation(&val[15], 1, N))
		  {
		    reachedEndOfLoop7 = 1;
		    break;
		  };
		if(reachedEndOfLoop7)
		  break;

		printf("***\nSolution Found: %d\nAt iteration: %lld\n***\n", ++solution, iteration);
		printf("         %2d\n", val[4]);
		printf("   %2d %2d    %2d %2d\n", val[0], val[1], val[2], val[3]); 
		printf("   %2d          %2d\n", val[5], val[15]);
		printf("%2d                %2d\n", val[6], val[14]);
		printf("   %2d          %2d\n", val[7], val[13]);
		printf("   %2d %2d    %2d %2d\n", val[8], val[9], val[11], val[12]);
		printf("         %2d\n", val[10]);
		printf("***\n");

		solution++;
	      } //Loop7
	    } //Loop6
	  } //Loop5
	} //Loop4
      } //Loop3
    } //Loop2
  } //Loop1

  printf("Found %d solutions after %lld iterations.\n", solution, iteration);

  return 0;
}

int isUniqueArray(int a[], int size, int index)
{
  int i, j;
  for(i = index; i < index+size; i++)
  {
    for(j = 0; j < index; j++)
    {
      if(a[i] == a[j])
	return 0;
    }
  }
  return 1;
}

int getNextPermutation(int array[], int size, int max)
{
  int index = size-1;	//try incrementing the last digit
  incrementDigitUntilUnique(array, index);
  if(array[index] == max+1) //then we set it back to zero, and try incrementing the next digit
  {
    if(index==0)
      return 0;	//reached the end
    array[index] = 0;
    if(!getNextPermutation(array, size-1, max)) //work on the subarray without the last element
      return 0; //pass the result back up the recursion stack
    incrementDigitUntilUnique(array, index);
  }
  return 1;
}

void incrementDigitUntilUnique(int array[], int index)
{
  int i, unique;
  do
  {
    array[index]++;
    unique = 1;
    for(i=index-1; i>=0; i--)
      if(array[index]==array[i])
	unique = 0; //not unique
  } while(!unique);
}