#include<stdio.h>
#define N 9

int grade[N][N][N] =   {
  {{ 0, 0, 0, 0, 3, 0, 0, 0,  0},
   { 0, 9, 0, 0, 4, 0, 0, 8, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 7, 3, 0, 0, 1, 0, 0, 5, 4},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 2, 0, 0, 7, 0, 0, 6, 0},
   { 0, 0, 0, 0, 5, 0, 0, 0, 0}},
  {{ 3, 0, 0, 0, 9, 0, 0, 0, 2},
   { 0, 0, 0, 0, 7, 0, 0, 0, 0},
   { 0, 0, 9, 2, 0, 4, 7, 0, 0},
   { 0, 0, 4, 7, 0, 8, 6, 0, 0},
   { 1, 9, 0, 0, 0, 0, 0, 8, 7},
   { 0, 0, 3, 9, 0, 1, 4, 0, 0},
   { 0, 0, 1, 4, 0, 5, 8, 0, 0},
   { 0, 0, 0, 0, 1, 0, 0, 0, 0},
   { 5, 0, 0, 0, 8, 0, 0, 0, 6}},
  {{ 0, 0, 0, 4, 0, 5, 0, 0, 0},
   { 0, 3, 0, 6, 0, 9, 0, 5, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},      
   { 3, 8, 0, 0, 0, 0, 0, 4, 2},
   { 0, 0, 0, 0, 7, 0, 0, 0, 0},
   { 6, 1, 0, 0, 0, 0, 0, 3, 8},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 9, 0, 5, 0, 2, 0, 8, 0},
   { 0, 0, 0, 9, 0, 1, 0, 0, 0}},
  {{ 0, 0, 6, 0, 0, 0, 3, 0,  0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 2, 0, 4, 0, 0, 0, 6, 0, 9},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 4, 0, 5, 0, 0, 0, 9, 0, 1},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 7, 0, 0, 0, 5, 0, 0}},
  {{ 4, 2, 0, 0, 7, 0, 0, 6, 1},
   { 6, 1, 0, 0, 0, 0, 0, 3, 8},
   { 0, 0, 0, 0, 9, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 8, 0, 3, 0, 6, 0, 4, 0, 5},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 1, 0, 0, 0, 0},
   { 5, 4, 0, 0, 0, 0, 0, 9, 6},
   { 9, 6, 0, 0, 2, 0, 0, 7, 3}},
  {{ 0, 0, 8, 0, 0, 0, 2, 0,  0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 9, 0, 1, 0, 0, 0, 8, 0, 3},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 1, 0, 6, 0, 0, 0, 3, 0, 7},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 4, 0, 0, 0, 6, 0, 0}},
  {{ 0, 0, 0, 9, 0, 1, 0, 0,  0},
   { 0, 5, 0, 7, 0, 8, 0, 1, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 5, 4, 0, 0, 0, 0, 0, 9, 6},
   { 0, 0, 0, 0, 2, 0, 0, 0, 0},
   { 7, 3, 0, 0, 0, 0, 0, 5, 4},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 8, 0, 1, 0, 6, 0, 4, 0},
   { 0, 0, 0, 8, 0, 3, 0, 0, 0}},
  {{ 6, 0, 0, 0, 5, 0, 0, 0, 8},
   { 0, 0, 0, 0, 9, 0, 0, 0, 0},
   { 0, 0, 5, 8, 0, 3, 9, 0, 0},
   { 0, 0, 3, 9, 0, 1, 4, 0, 0},
   { 2, 5, 0, 0, 0, 0, 0, 1, 9},
   { 0, 0, 6, 5, 0, 2, 3, 0, 0},
   { 0, 0, 2, 3, 0, 7, 1, 0, 0},
   { 0, 0, 0, 0, 2, 0, 0, 0, 0},
   { 7, 0, 0, 0, 1, 0, 0, 0, 4}},
  {{ 0, 0, 0, 0, 8, 0, 0, 0, 0},
   { 0, 6, 0, 0, 2, 0, 0, 7, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},   
   { 3, 8, 0, 0, 9, 0, 0, 4, 2},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 0, 0, 0, 0, 0, 0, 0, 0},
   { 0, 5, 0, 0, 3, 0, 0, 1, 0},
   { 0, 0, 0, 0, 4, 0, 0, 0, 0}}};

void desenha_grade() {
  int i,j,k;
  for (k= 0; k < N; k++) {
    printf("+---------+---------+---------+\n");
    for (i = 0; i < N; i++) {
      printf("|");
      for (j = 0; j < N; j++) {
	if (grade[i][j] != 0)
	  printf(" %d ", grade[k][i][j]);
	else
	printf("   ");
	if (j % 3 == 2) 
	  printf("|");
      }
      if (i % 3 == 2)
	printf("\n+---------+---------+---------+");
      printf("\n");
    }
  }
}

int tenta_colocar(int k, int i, int j, int v) {
  int a,b,c;
  for (a = 0; a < N; a++)
    if (grade[a][i][j] == v)
      return 0;
  for (b = 0; b < N; b++)
    if (grade[k][b][j] == v)
      return 0;
  for (c = 0; c < N; c++)
    if (grade[k][i][c] == v)
      return 0;

  for (a = i - i % 3; a < i - i % 3 +3; a++)
    for (b = j - j % 3; b < j - j % 3 + 3; b++)
      if (grade[k][a][b] == v)
	return 0;

  for (a = k - k % 3; a < k - k % 3 +3; a++)
    for (b = j - j % 3; b < j - j % 3 + 3; b++)
      if (grade[a][i][b] == v)
	return 0;

  for (a = k - k % 3; a < k - k % 3 +3; a++)
    for (b = i - i % 3; b < i - i % 3 + 3; b++)
      if (grade[a][b][j] == v)
	return 0;
  grade[k][i][j] = v;
  return 1;
}

int completa_grade(int k, int i, int j) {
  int v, ni, nj, nk;

  if (k == 9)  /* Grade completa */
    return 1;

  if (j < 8) {  /* Próxima posição */
    nk = k;
    ni = i;
    nj = j+1;
  } else if (i < 8) {
    nk = k;
    ni = i+1;
    nj = 0;
  } else {
    nk = k+1;
    ni = 0;
    nj = 0;
  }
 
  if (grade[k][i][j] !=  0)  /* Pré-definida */
    return completa_grade(nk, ni, nj);

  for (v = 1; v <= 9; v++) 
    if (tenta_colocar(k, i, j, v) &&
	completa_grade(nk, ni, nj))
      return 1;

  grade[k][i][j] = 0;
  return 0;
}

int main() {
  desenha_grade();
  if (completa_grade(0,0,0)) {
    printf("Resposta: \n");
    desenha_grade();
  } else
    printf("Resposta não encontrada.\n");
  return 0;
}