/*
 * Não garante que o desafio gerado terá apenas uma solução.
 */
#include<stdio.h>
#include<stdlib.h>
#define N 9

int grade[N][N] =
  {{ 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},
   { 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},
   { 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}};

int desafio[N][N] =
  {{ 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},
   { 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},
   { 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}};

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

int tenta_colocar(int i, int j, int k) {
  int c,l;
  for (l = 0; l < N; l++)
    if (grade[l][j] == k)
      return 0;
  for (c = 0; c < N; c++)
    if (grade[i][c] == k)
      return 0;
  for (l = i - i % 3; l < i - i % 3 +3; l++)
    for (c = j - j % 3; c < j - j % 3 + 3; c++)
      if (grade[l][c] == k)
	return 0;
  grade[i][j] = k;
  return 1;
}

int completa_grade(int i, int j) {
  int k;

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

  if (grade[i][j] !=  0) { /* Pré-definida */
    if (j == 8)
      return completa_grade(i+1, 0);
    else
      return completa_grade(i, j+1);
  }


  for (k = 1; k <= 9; k++) 
    if (tenta_colocar(i, j, k)) {
      if (j == 8) {
	if (completa_grade(i+1, 0))
	  return 1;
      }
      else
	if (completa_grade(i, j+1))
	  return 1;
    }
  grade[i][j] = 0;
  return 0;
}

void inicio_aleatorio() {
  int i;
  for (i = 0; i < 9; i++) 
    tenta_colocar(i, random() % 9, random() % 9);
}

void monta_desafio() {
  int i,j,k;
  for (i = 0; i < 9; i++) 
    for (k = 0; k < 3; k++) {
      j = random() % 9;
      desafio[i][j] = grade[i][j];      
    }
  desenha_grade(desafio);
}

int main(int argc, char *argv[]) {
  if (argc == 2) { /* Semente para o gerador */
    int s;
    sscanf(argv[1], "%d", &s);
    srandom(s);
  }
  inicio_aleatorio();
  desenha_grade(grade);
  if (completa_grade(0,0)) {
    desenha_grade(grade);
    monta_desafio();
  }
  else
    printf("Tente outra semente.\n");
  return 0;
}