#include <stdio.h>

typedef struct peca {
  int N, S, L, O;
} Peca;


#define NLIN 3
#define NCOL 3

Peca tabuleiro[NLIN][NCOL] = 
  {{{-1,0,0,0}, {-1,0,0,0}, {-1,0,0,0}},
   {{-1,0,0,0}, {-1,0,0,0}, {-1,0,0,0}},
   {{-1,0,0,0}, {-1,0,0,0}, {-1,0,0,0}}};

Peca mesa[NLIN][NCOL] =
  {{{4,5,4,0}, {2,4,8,7}, {2,2,6,4}},
   {{6,2,0,0}, {5,2,4,6}, {0,4,7,4}},
   {{7,7,1,4}, {4,7,3,4}, {4,6,4,3}}};


/* Desenha uma linha de uma peça no formato:
   +-----+
   |  3  |
   |2   0|
   |  1  |
   +-----+
*/

#define LARG_PECA 7
#define ALT_PECA 5
#define BORDA_SUPERIOR 0
#define LINHA_NORTE 1
#define LINHA_LESTE_OESTE 2
#define LINHA_SUL 3
#define BORDA_INFERIOR 4

void desenha_linha_peca (Peca p, int linha) {
  if (p.N != -1)
    switch (linha) {
    case BORDA_INFERIOR:
    case BORDA_SUPERIOR:
      printf("+-----+");
      break;
    case LINHA_NORTE:
       printf("|  %d  |", p.N);
       break;
    case LINHA_LESTE_OESTE:
      printf("|%d   %d|", p.O, p.L);
      break;
    case LINHA_SUL:
      printf("|  %d  |", p.S);
      break;
    }
  else {
    int i;
    for (i = 0; i < LARG_PECA; i++)
      printf(" ");
  }
}


void desenha_tabuleiro_mesa() {
#define ESPACO "    "
  int i,j,k;

  printf("+");
  for (j = 0; j < NCOL * LARG_PECA; j++)
    printf("-");
  printf("+");
  printf("%s", ESPACO);
  printf("+");
  for (j = 0; j < NCOL * LARG_PECA; j++)
    printf("-");
  printf("+\n");

  for (k = 0; k < NLIN; k++) {
    for (j = 0; j < ALT_PECA; j++) {
      printf("|");
      for (i = 0; i < NCOL; i++) 
	desenha_linha_peca(tabuleiro[k][i], j);
      printf("|%s|", ESPACO);
      for (i = 0; i < NCOL; i++) 
	desenha_linha_peca(mesa[k][i], j);
      printf("|\n");
    }
  }

  printf("+");
  for (j = 0; j < NCOL * LARG_PECA; j++)
    printf("-");
  printf("+");
  printf("%s", ESPACO);
  printf("+");
  for (j = 0; j < NCOL * LARG_PECA; j++)
    printf("-");
  printf("+\n");

}

/* Retorna 1 se for possível colocar a peça p
   na posição (i, j) do tabuleiro.  Retorna 0,
   caso contrário.
*/  
int coloca_tabuleiro(int i, int j, Peca p) {
  return ((p.N != -1) &&
	  (i == 0 ||
	   tabuleiro[i-1][j].N == -1 || tabuleiro[i-1][j].S == p.N) &&
	  (i == NLIN-1 ||
	   tabuleiro[i+1][j].N == -1 || tabuleiro[i+1][j].N == p.S) &&
	  (j == 0 ||
	   tabuleiro[i][j-1].N == -1 || tabuleiro[i][j-1].L == p.O) &&
	  (j == NCOL-1 ||
	   tabuleiro[i][j+1].N == -1 || tabuleiro[i][j+1].O == p.L));
}

int completa_tabuleiro(int i, int j) {
  int im, jm;

  if (i == NLIN)  /* Tabuleiro completo */
    return 1;
  
  for (im = 0; im < NLIN; im++) 
    for (jm = 0; jm < NCOL; jm++) {
      if (coloca_tabuleiro(i,j,mesa[im][jm])) {
	tabuleiro[i][j] = mesa[im][jm];
	mesa[im][jm].N = -1;
	desenha_tabuleiro_mesa();
	if ((j < NCOL - 1  && completa_tabuleiro(i, j+1)) ||
	    (j == NCOL - 1 && completa_tabuleiro(i+1, 0)))
	  return 1;
	mesa[im][jm] = tabuleiro[i][j];
	tabuleiro[i][j].N = -1;
	desenha_tabuleiro_mesa();
      }
    }
  return 0;
}

int main() {
  desenha_tabuleiro_mesa();
  completa_tabuleiro(0,0);
  return 0;
}