#include <stdio.h>
#include <stdlib.h>
#include <mem.h>

#define MAX_PIECES   25
#define MAXLEN      255
#define SIDES         4

#define PASS          1
#define FAIL         -1

#define TRUE          1
#define FALSE         0

#define RIGHT         0
#define TOP           1
#define LEFT          2
#define BOTTOM        3

char piece[MAX_PIECES][SIDES];
int  used[MAX_PIECES];
int  solution[2][MAX_PIECES];

int  n_pieces;
int  ctr;
                        
int  complement(char,char);  
char edge_value(int,int,int);  
int  fits(int,int,int);
int  load_puzzle(char *);
void main(int,char **);    
int  next_unused(char *);
void show_solution(void);
void solve_puzzle(int);

/* --------------------------------------------------------------- */
int load_puzzle(char *filename)
{
   FILE *f1;
   char  s[MAXLEN + 1];
   int   count;
   int   i;
   int   j;

   // We will store puzzle descriptions in files so we can switch among them.
   f1 = fopen(filename,"rt");
   if (f1 == NULL)
      return(FAIL);

   if (fgets(s,MAXLEN,f1) == NULL)
      return(FAIL);

   // First line of a 'valid' file will list the number of pieces that follow.
   // In these puzzles, figures are identified with two letters, each
   // corresponding to part of the figure.  (In a puzzle featuring four types
   // of airplanes, for example, you would need 8 letters to represent the
   // front and back (or top and bottom) of all four planes.

   if (sscanf(s,"%d",&count) != 1)
      return(FAIL);

   // In the 'standard' puzzle, count = 9
   for (i = 0;i < count;i++)
   {
      if (fgets(s,MAXLEN,f1) == NULL)
         return(FAIL);

      // Like a Cartesian plane, we will describe the four sides of our puzzle
      // square starting with the East side, moving then to North, West, and
      // finally, South.

      for (j = 0;j < SIDES;j++)
      {
         if ((s[j] == '\0') || (s[j] == '\0') || (s[j] == '\0'))
            return(FAIL);
         else
            piece[i][j] = s[j];
      }
   }

   fclose(f1);

   return(count);
}                                                                    
/* --------------------------------------------------------------- */
int next_unused(char *considered)
{
   int i;

   i = 0;
   while ((i < MAX_PIECES) && ((used[i] == TRUE) || (considered[i] == 'x')))
      i++;

   if (i == MAX_PIECES)
      return(FAIL);
   else
      return(i);
}                                                                     
/* --------------------------------------------------------------- */
int complement(char c1,char c2)
{
   if (((c1 == 'A') && (c2 == 'B')) || 
       ((c1 == 'B') && (c2 == 'A')) ||
       ((c1 == 'C') && (c2 == 'D')) ||
       ((c1 == 'D') && (c2 == 'C')) ||
       ((c1 == 'E') && (c2 == 'F')) ||
       ((c1 == 'F') && (c2 == 'E')) ||
       ((c1 == 'G') && (c2 == 'H')) ||
       ((c1 == 'H') && (c2 == 'G')))
      return(TRUE);
   else
      return(FALSE);
}
/* --------------------------------------------------------------- */
char edge_value(int piece_num,int orientation,int edge)
{
   char side_values[SIDES];
   int  i;
   int  slot;

   // Each piece has four sides.  We originally number these 0 (Right Edge),
   // 1 (Top Edge), 2 (Left Edge), and 3 (Bottom Edge).  This is in
   // 'orientation' 0.  Since, in the puzzle, a piece can be rotated, we
   // also identify orientation 1 (one quarter-turn clockwise), orientation 2
   // (two quarter-turns clockwise) etc.
   //
   // This function returns the value of the edge of a particular piece
   // in a particular orientation.

   for (i = 0;i < SIDES;i++)
      side_values[i] = piece[piece_num][i];

   // Note: the following DEPENDS on the way we have assigned values to
   // RIGHT, TOP, LEFT, and BOTTOM, and the fact that we are working with
   // square pieces.

   slot = (orientation + edge) % SIDES;

   return(side_values[slot]);
}
/* --------------------------------------------------------------- */
int fits(int p,int orientation,int place)
{
   char edge1;
   char edge2;

   switch (n_pieces)
   {
      case 9:
         // Okay, it works like this:  Our puzzle is a 3x3 grid.  We start
         // at the center (position 0), and then attempt to add pieces
         // counter-clockwise, starting from the immediate right.  So, the
         // board looks like this:
         //
         // +---+---+---+
         // | 4 | 3 | 2 |
         // +---+---+---+
         // | 5 | 0 | 1 |
         // +---+---+---+
         // | 6 | 7 | 8 |
         // +---+---+---+
         //
         // So ... when we place square '1', we only need to see if the
         // edge between it and square '0' are complementary (after accounting
         // for the orientation of each, of course).  Squares 3, 5, 7,
         // and 8 will need to check 2 edges, and squares 1, 2, 4, and 6 will
         // only have one edge to check.

         switch (place)
         {
            case 0:
               return(TRUE); // Nothing to check!  Everything fits here.
            case 1:
               // Find the value of the center piece's right edge.
               edge1 = edge_value(solution[0][0],solution[1][0],RIGHT);
               // Find the value of piece 1's left edge.
               edge2 = edge_value(p,orientation,LEFT);

               return(complement(edge1,edge2));
            case 2:
               // Find the value of the piece 1's top edge.
               edge1 = edge_value(solution[0][1],solution[1][1],TOP);
               // Find the value of piece 2's bottom edge.
               edge2 = edge_value(p,orientation,BOTTOM);

               return(complement(edge1,edge2));
            case 3:
               // A two part test ... we need to check the border with the
               // piece in position 2, and the border with the piece in
               // position 0.

               // Find the value of the piece 2's left edge.
               edge1 = edge_value(solution[0][2],solution[1][2],LEFT);
               // Find the value of piece 3's right edge.
               edge2 = edge_value(p,orientation,RIGHT);

               if (complement(edge1,edge2))
               {
                  // Find the value of the piece 0's top edge.
                  edge1 = edge_value(solution[0][0],solution[1][0],TOP);
                  // Find the value of piece 3's bottom edge.
                  edge2 = edge_value(p,orientation,BOTTOM);

                  return(complement(edge1,edge2));
               }
               else
                  return(FALSE);
            case 4:
               // Find the value of the piece 3's left edge.
               edge1 = edge_value(solution[0][3],solution[1][3],LEFT);
               // Find the value of piece 4's right edge.
               edge2 = edge_value(p,orientation,RIGHT);

               return(complement(edge1,edge2));
            case 5:
               // A two part test ... we need to check the border with the
               // piece in position 4, and the border with the piece in
               // position 0.

               // Find the value of the piece 4's bottom edge.
               edge1 = edge_value(solution[0][4],solution[1][4],BOTTOM);
               // Find the value of piece 5's top edge.
               edge2 = edge_value(p,orientation,TOP);

               if (complement(edge1,edge2))
               {
                  // Find the value of the piece 0's left edge.
                  edge1 = edge_value(solution[0][0],solution[1][0],LEFT);
                  // Find the value of piece 5's right edge.
                  edge2 = edge_value(p,orientation,RIGHT);

                  return(complement(edge1,edge2));
               }
               else
                  return(FALSE);
            case 6:
               // Find the value of the piece 5's bottom edge.
               edge1 = edge_value(solution[0][5],solution[1][5],BOTTOM);
               // Find the value of piece 6's top edge.
               edge2 = edge_value(p,orientation,TOP);

               return(complement(edge1,edge2));
            case 7:
               // A two part test ... we need to check the border with the
               // piece in position 6, and the border with the piece in
               // position 0.

               // Find the value of the piece 6's right edge.
               edge1 = edge_value(solution[0][6],solution[1][6],RIGHT);
               // Find the value of piece 7's left edge.
               edge2 = edge_value(p,orientation,LEFT);

               if (complement(edge1,edge2))
               {
                  // Find the value of the piece 0's bottom edge.
                  edge1 = edge_value(solution[0][0],solution[1][0],BOTTOM);
                  // Find the value of piece 7's top edge.
                  edge2 = edge_value(p,orientation,TOP);

                  return(complement(edge1,edge2));
               }
               else
                  return(FALSE);    
            case 8:
               // A two part test ... we need to check the border with the
               // piece in position 7, and the border with the piece in
               // position 1.

               // Find the value of the piece 7's right edge.
               edge1 = edge_value(solution[0][7],solution[1][7],RIGHT);
               // Find the value of piece 8's left edge.
               edge2 = edge_value(p,orientation,LEFT);

               if (complement(edge1,edge2))
               {
                  // Find the value of the piece 1's bottom edge.
                  edge1 = edge_value(solution[0][1],solution[1][1],BOTTOM);
                  // Find the value of piece 8's top edge.
                  edge2 = edge_value(p,orientation,TOP);

                  return(complement(edge1,edge2));
               }
               else
                  return(FALSE);
         }
   }

   return(FALSE);
}                                                                  
/* --------------------------------------------------------------- */
void show_solution(void)
{

   printf("\t+------+------+------+\n");

   printf("\t+ %d, %d | %d, %d | %d, %d |\n",
      solution[0][4], solution[1][4],
      solution[0][3], solution[1][3],
      solution[0][2], solution[1][2]);

   printf("\t+------+------+------+\n");

   printf("\t+ %d, %d | %d, %d | %d, %d |\n",
      solution[0][5], solution[1][5],
      solution[0][0], solution[1][0],
      solution[0][1], solution[1][1]);

   printf("\t+------+------+------+\n");

   printf("\t+ %d, %d | %d, %d | %d, %d |\n",
      solution[0][6], solution[1][6],
      solution[0][7], solution[1][7],
      solution[0][8], solution[1][8]);

   printf("\t+------+------+------+\n\n\n");
}
/* --------------------------------------------------------------- */
void solve_puzzle(int k)
{
   int n;
   int orientation;
   char considered[MAX_PIECES + 1];

   // 'considered' tracks the puzzle pieces we have tried at this
   // level of the recursion. After a piece has been tried, we mark it
   // with an 'x';

   memset(considered,'\0',MAX_PIECES + 1);
   memset(considered,' ',MAX_PIECES);

   n = next_unused(considered);

   // printf("%5d, %d\n", ++ctr, k);
   
   if (k < n_pieces)
   {
      while (n < n_pieces) // Try each unused piece
      {
         orientation = 0;
         while (orientation < SIDES)
         {
            if (fits(n,orientation,k) == TRUE)
            {
               solution[0][k] = n;
               solution[1][k] = orientation;

               used[n] = TRUE;

               solve_puzzle(k + 1);

               used[n] = FALSE;
            }

            orientation++;
         }

         considered[n] = 'x';

         if ((n = next_unused(considered)) == FAIL)
            break;
      }
   }
   else
      show_solution();
}
/* --------------------------------------------------------------- */
void main(int argc,char **argv)
{
   int i;
   int j;

   if (argc < 2)
      exit(1);

   if ((n_pieces = load_puzzle(argv[1])) == FAIL)
      exit(1);

   ctr = 0;

   for (i = 0;i < n_pieces;i++)
   {
      // Initialize solution arrays
      for (j = 0;j < MAX_PIECES;j++)
      {
         used[j] = FALSE;

         solution[0][j] = 0;
         solution[1][j] = 0;
      }
      // Loop through each puzzle piece as the first (center) piece
      // played.

      used[i] = TRUE;

      solution[0][0] = i;
      solution[1][0] = 0;

      solve_puzzle(1);
   }
}
/* --------------------------------------------------------------- */