#include <stdio.h>

typedef enum {W, T, B, G} color;
/* W = White, T = Tan, B = Black, G = Gray */
typedef enum {F, R} direct;
/* F = Front, R = Rear */
typedef struct {
   color c[4];
   direct d[4];
} P_type; /* one piece */
P_type p[16]; /* 16 pieces */

typedef struct {
   int piece; /* 0 to 15 */
   int orient; /* 0 to 3 */
} B_type; /* piece and orientation */
B_type b[4][4]; /* the board */

int a[16]; /* remaining pieces */

void try (int, int[]);
int check(int, int, int);
void init_b(void);
void print_board(int);
void out24(int);

int count = 0;

void main() {
   int i;
   init_b();
   for(i = 0; i < 16; i++) a[i] = i;
   try(16,a);
}

/* keep trying to place pieces */
void try (int n, int a[16]) {
   int i;
   int at[16];
   int cp;
   int co;
   /* getchar();
   printf("Try. n:%2i,a:", n);
   for(i = 0; i < n; i++) printf("%2i,", a[i]);
   printf("\n"); */
   /* try each remaining piece */
   for(cp = 0; cp < n; cp++) { 
      if (n > 1) {
         for(i = 0; i < cp; i++) at[i] = a[i];
         for(i = cp+1; i < n; i++) at[i-1] = a[i];
      }
      for(i = n; i < 16; i++) at[i] = 1000000;
      /* try each orientation */
      for(co = 0; co < 4; co++) { 
         if (check(n, a[cp], co)) {
            /* count++;
            if (count < 20) print_board(n); */
            /* if (n == 1) print_board(n);
            else  */
            if (n <= 1) {
               print_board(n);
            }
            if (n >= 1) try(n-1, at);
         }
      }
   }
}

/* check that a new placement works */
int check(int n, int ap, int co) {
   int num = 16 - n;
   int i = (int) (num / 4);
   int j = num % 4;
   int apt, cot;
   /*      getchar();
      printf("Check. ap:%2i, co:%2i\n", ap, co); */
   b[i][j].piece = ap;
   b[i][j].orient = co;
   if (j > 0) {
      apt = b[i][j-1].piece;
      cot = b[i][j-1].orient;
      if (p[ap].c[(3+co)%4] != p[apt].c[(1+cot)%4])
         return 0;
      if (p[ap].d[(3+co)%4] == p[apt].d[(1+cot)%4])
         return 0;
   }
   if (i > 0) {
      apt = b[i-1][j].piece;
      cot = b[i-1][j].orient;
      if (p[ap].c[(0+co)%4] != p[apt].c[(2+cot)%4])
         return 0;
      if (p[ap].d[(0+co)%4] == p[apt].d[(2+cot)%4])
         return 0;
   }
   /*
   printf(" Check:Success! n:%2i, ap:%2i, co:%2i\n",
      n, ap, co);
   print_board(n); */
   return 1;
}

void print_board(int n) {
   int k, i, j;
   int c[4];
   int minc, minci;
   int num = 17 - n;
   c[0] = b[0][0].piece;
   c[1] = b[0][3].piece;
   c[2] = b[3][3].piece;
   c[3] = b[3][0].piece;
   for (i = 0; i < 4; i++)
      if (c[i] == 4) c[i] = 2;
   minc = c[0]; minci = 0;
   for (i = 1; i < 4; i++)
      if (c[i] < minc) {
         minc = c[i];
         minci = i;
      }
   if ((c[minci] == 2) && (c[(minci+2)%4] == 2))
      if ( c[(minci+1)%4] > c[(minci+3)%4] )
         minci = (minci+2)%4;
   for (i = 0; i < 4; i++)
      printf("%2i ", c[(minci+i)%4]);
   printf(";");
   switch (minci) {
   case 0: printf("(%2i)", b[0][0].orient);
      for(i = 0; i < 4; i++) {
         printf("| ");
         for(j = 0; j < 4; j++)
            out24(b[i][j].piece);
      }
      break;
   case 1: printf("(%2i)", (b[0][3].orient+3)%4);
      for(j = 3;j >= 0; j--) {
         printf("| ");
         for(i = 0; i < 4; i++)
            out24(b[i][j].piece);
      }
      break;
   case 2: printf("(%2i)", (b[3][3].orient+2)%4);
      for(i = 3;i >= 0; i--) {
         printf("| ");
         for(j = 3;j >= 0; j--)
            out24(b[i][j].piece);
      }
      break;
   case 3: printf("(%2i)", (b[3][0].orient+1)%4);
      for(j = 0; j < 4; j++) {
         printf("| ");
         for(i = 3;i >= 0; i--)
            out24(b[i][j].piece);
      }
      break;
   }
   printf("|\n");
}

void out24(int n) {
   if (n == 4) n = 2;
   printf("%2i ", n);
}

void init_b(void) {
   int i;
   for(i = 0; i < 16; i++) p[i].c[0] = W;
   for(i = 0; i < 8; i++) {
      p[i].d[0] = R; p[i].d[2] = F;
   }
   for(i = 8; i < 16; i++) {
      p[i].d[0] = F; p[i].d[2] = R;
   }
   for(i = 0; i < 2; i++) {
      p[i].d[1] = F; p[i].d[3] = R;
   }
   for(i = 10; i < 16; i++) {
      p[i].d[1] = F; p[i].d[3] = R;
   }
   for(i = 2; i < 10; i++) {
      p[i].d[1] = R; p[i].d[3] = F;
   }
   p[ 0].c[1] = B; p[ 0].c[2] = T; p[ 0].c[3] = G;
   p[ 1].c[1] = T; p[ 1].c[2] = G; p[ 1].c[3] = B;
   p[ 2].c[1] = T; p[ 2].c[2] = B; p[ 2].c[3] = G;
   p[ 3].c[1] = T; p[ 3].c[2] = G; p[ 3].c[3] = B;
   p[ 4].c[1] = T; p[ 4].c[2] = B; p[ 4].c[3] = G;
   p[ 5].c[1] = G; p[ 5].c[2] = B; p[ 5].c[3] = G;
   p[ 6].c[1] = B; p[ 6].c[2] = G; p[ 6].c[3] = T;
   p[ 7].c[1] = G; p[ 7].c[2] = B; p[ 7].c[3] = T;
   p[ 8].c[1] = G; p[ 8].c[2] = T; p[ 8].c[3] = B;
   p[ 9].c[1] = T; p[ 9].c[2] = B; p[ 9].c[3] = G;
   p[10].c[1] = T; p[10].c[2] = B; p[10].c[3] = G;
   p[11].c[1] = T; p[11].c[2] = B; p[11].c[3] = G;
   p[12].c[1] = G; p[12].c[2] = B; p[12].c[3] = T;
   p[13].c[1] = G; p[13].c[2] = T; p[13].c[3] = B;
   p[14].c[1] = B; p[14].c[2] = B; p[14].c[3] = G;
   p[15].c[1] = T; p[15].c[2] = B; p[15].c[3] = T;
}