// Include lines.
#include<stdio.h>
#include<time.h>
#define SIZE_MATRIX 3
#define N ((SIZE_MATRIX * SIZE_MATRIX) + 1) 
// We need to use 1-indexing here.
#define TRUE 1
#define FALSE 0
#define S -1

// The final problem.
// static int nums[N]={S,10,12,13,21,34,38,40,47,50,53,57,64,65,78,89,98};

// This is the temporary, smaller problem.
static int nums[N]={S,12,13,14,56,57,58,103,114,129};

// The final problem.
// static int init_matrix[SIZE_MATRIX][SIZE_MATRIX] =
//   {{S,S,S,S},{S,S,S,S},{S,S,S,S},{S,S,S,S}};

// This is the temporary, smaller problem.
static int init_matrix[SIZE_MATRIX][SIZE_MATRIX] =
  {{S,S,S},{S,S,S},{S,S,S}};

// A few global variables. 
int a[N]; // The current permutation.
int c[N]; // Represents inversions.
int o[N]; // Governs the directions by which the c[i] entires change.

// Function prototypes.
void initialize_matrix(int matrix[SIZE_MATRIX][SIZE_MATRIX]);
int compute_matrix(int matrix[SIZE_MATRIX][SIZE_MATRIX]);
int check_numbers(int m, int n);
int check_matrix(int matrix[SIZE_MATRIX][SIZE_MATRIX]);
void print_matrix(int matrix[SIZE_MATRIX][SIZE_MATRIX]);
void assign_numbers_by_permutation(int matrix[SIZE_MATRIX][SIZE_MATRIX]);
void initialize_permutations(void);
int process_permutation(int matrix[SIZE_MATRIX][SIZE_MATRIX]);
int generate_permutations(int matrix[SIZE_MATRIX][SIZE_MATRIX]);

// Main function. Execution starts here.
int main(void)
{
  int matrix[SIZE_MATRIX][SIZE_MATRIX];
  int num_permutations;
  initialize_matrix(matrix);
  initialize_permutations();

  time_t start_time=time(NULL);
  num_permutations=generate_permutations(matrix);
  time_t stop_time=time(NULL);
  printf("Execution time is %f.\n",difftime(stop_time,start_time));
  printf("Found %d working combinations.\n",num_permutations);

  return 0;
}

// This function initializes the matrix that holds the numbers.
void initialize_matrix(int matrix[SIZE_MATRIX][SIZE_MATRIX])
{
  int col=0, row=0;

  for(; col<SIZE_MATRIX; col++)
    for(; row<SIZE_MATRIX; row++)
      matrix[row][col]=init_matrix[row][col];
}

// This function checks two two-digit numbers to see if they are ok.
int check_numbers(int m, int n)
{
  int is_good=1;
  int m_unit, m_tens, n_unit, n_tens;

  m_unit=m%10; // m's unit digit
  m_tens=m/10; // m's tens digit
  n_unit=n%10; // n's unit digit
  n_tens=n/10; // n's tens digit

  if((m>0) && (n>0)) // If either digit is <0, don't compare them.
  {
    // Check m's unit digit against all other digits.
    // is_good*=(m_unit!=m_tens); No need to check this. 
    // We can assume these will not clash!
    is_good*=(m_unit!=n_unit);
    is_good*=(m_unit!=n_tens);

    // Check m's tens digit against all digits except m's unit digit.
    is_good*=(m_tens!=n_unit);
    is_good*=(m_tens!=n_tens);

    // Check n's tens digit against its unit digit - other tests
    // have already been done, since the tests are symmetrical.
    // is_good*=(n_unit!=n_tens); Again, no need to check.
    // We will assume the problem starts out with no
    // duplications within a single two-digit number.
  }
  // In these tests, assume the numbers are good unless
  // proven otherwise. All digits must be different in order
  // to pass.

  return is_good;
}

// This function checks matrix to see if it contains a valid combo.
int check_matrix(int matrix[SIZE_MATRIX][SIZE_MATRIX])
{
  int col=0, row=0, diag=0, marker=1, good=TRUE;
  // The "marker" variable is to move through the row
  // or column or diagonal in which we are interested.

  // First check uniqueness on rows.
  for(row=0; row<SIZE_MATRIX; row++)
    for(col=0; col<SIZE_MATRIX-1; col++)
      for(marker=col+1; marker<SIZE_MATRIX; marker++)
        good*= check_numbers(matrix[row][col],matrix[row][marker]);

  // Next check uniqueness on columns;
  for(col=0; col<SIZE_MATRIX; col++)
    for(row=0; row<SIZE_MATRIX-1; row++)
      for(marker=row+1; marker<SIZE_MATRIX; marker++)
        good*=check_numbers(matrix[row][col],matrix[marker][col]);

  // Finally, check uniqueness on main diagonals.
  for(diag=0; diag<SIZE_MATRIX-1; diag++)
    for(marker=diag+1; marker<SIZE_MATRIX; marker++)
    {
      good*=check_numbers(matrix[diag][diag],matrix[marker][marker]);
      good*=check_numbers(matrix[diag][SIZE_MATRIX-diag-1],
        matrix[marker][SIZE_MATRIX-marker-1]);
    }
  return good;
}

// This function prints the matrix.
void print_matrix(int matrix[SIZE_MATRIX][SIZE_MATRIX])
{
  int col=0, row=0;

  for(row=0; row<SIZE_MATRIX; row++)
  {
    for(col=0; col<SIZE_MATRIX; col++)
      printf("%3d ",matrix[row][col]);
    printf("\n");
  }
  printf("\n");
}

// This function assigns the numbers in the nums array into
// the matrix. 
void assign_numbers_by_permutation(int matrix[SIZE_MATRIX][SIZE_MATRIX])
{
  int row=0, col=0, counter=1; // We do 1-indexing in the permutation
                               // array.

  for(row=0; row<SIZE_MATRIX; row++)
    for(col=0; col<SIZE_MATRIX; col++)
      matrix[row][col]=nums[a[counter++]];
}

// This function processes a permutation. We do the following:
// 1. Assign nums to matrix based on the permutation a.
// 2. Call check_matrix(matrix) to see if the combo is ok.
// 3. If the combo checks out, return TRUE, print it, and return TRUE.
//    Else, return FALSE. 
int process_permutation(int matrix[SIZE_MATRIX][SIZE_MATRIX])
{
  int is_good=FALSE;

  assign_numbers_by_permutation(matrix);
  is_good=check_matrix(matrix);
  if(is_good)
    print_matrix(matrix);
  return is_good;
}

// Initialize the arrays used for generating permutations.
void initialize_permutations(void)
{
  int j=0;

  for(j=1; j<N; j++)
  {
    a[j]=j;
    c[j]=0;
    o[j]=1;
  }
}

// This code generates all permutations of the set {1,2,...,N}. 
// This algorithm is located in Donald Knuth's book
// The Art of Computer Programming, Pre-Fascicle 2B
// A Draft of Section 7.2.1.2:
// Generating All Permutations
// The Pn's referenced here correspond to the Plain Changes
// Algorithm P located on page 4. 
int generate_permutations(int matrix[SIZE_MATRIX][SIZE_MATRIX])
{
  int j=N-1, s=0, q=0, executeP2P3=TRUE, temp=0, continue_loop=TRUE;
  int num_good_combos=0;

  while(continue_loop)
  {
    if(executeP2P3)
    {
      // P2.
      num_good_combos+=process_permutation(matrix);

      // P3.
      j=N-1;
      s=0;
    }

    // P4.
    q=c[j]+o[j];
    if(q<0 || q==j)
    {
      if(q==j)
      {
        // P6
	if(j>1)
	{
	  s++;
	}
	else
	{
	  continue_loop=FALSE;
	  continue; // Terminate loop.
	}
      }

      // P7
      o[j]=-o[j];
      j--;
      executeP2P3=FALSE;
    }
    else
    {
      // P5
      temp=a[j-c[j]+s];
      a[j-c[j]+s]=a[j-q+s];
      a[j-q+s]=temp;
      c[j]=q;
      executeP2P3=TRUE;
    }
  }

  return num_good_combos;
}