#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

//structure pour les candidats d'une case
typedef struct {
  int nbc;
  int *tab;
} Cand;

//structure avec
typedef struct {
  int x;
  int y;
} Case;


Cand C[9][9];
int G[9][9];
Case O[81];
int NBO;
Case temp;

//entetes des fonctions
void lireGrille(int grille[][9]);
void ecrireGrille(int grille[][9]);
int appartient(Case, int);
int estCand(int);
int memeRegion(int, int, int, int);
int estCandUnique(Case, int);
Case rechCaseUnique();
void initJeu();
void ecrireCand();
void fermerCase();
void fermerGrille();





int main() {
  lireGrille(G);
  ecrireGrille(G);
  initJeu();
  printf("\n\n\n\n");
  ecrireCand();
  fermerGrille();
  //fermerGrille();
  return 0;
}







void lireGrille(int grille[][9]) {
  char ligne[6];
  int i, j, n, a, b;
  //remplit G avec 0
  for (a = 0;a < 9;a++) {
    for (b = 0;b < 9;b++)
      G[a][b] = 0;
  }
  //ouvre le fichier grille
  FILE *f;
  f = fopen("grille.txt", "r");
  while(fgets(ligne,10,f)) { //lit le fichier et le stocke dans G
    sscanf(ligne, "%d %d %d", &i, &j, &n);
    grille[i][j] = n;
  }
  //ferme le fichier
  fclose(f);
}


void ecrireGrille(int grille[][9]) {
  printf("-------------------------------\n");//1ere ligne
  int a, b;
  for (a = 0;a < 9;a++) {
    printf("|");
    for (b = 0;b < 9;b++) {
      printf(" %d ", grille[a][b]); //affiche la valeur
      if (((b+1) % 3) == 0)
        printf("|");
    }
    printf("\n");
    if ((a == 2) || (a == 5))
      printf("|---------|---------|---------|\n");//lignes intermediaires
  }
  printf("-------------------------------\n");//derniere ligne
}


int appartient(Case cible, int n) {
  if (C[cible.x][cible.y].tab[n] == 1)//verifie si n est candidat de la case cible
    return 1;
  else
    return 0;
}

int estCand(int n) {
  int a, b;
  for (a = 0;a < 9;a++) {
    if (G[a][temp.y] == n) {
        return 0;
    }
  }
  for (a = 0;a < 9;a++) {
    if (G[temp.x][a] == n) {
        return 0;
    }
  }
  for (a = 0;a < 9;a++) {
    for (b = 0;b < 9;b++) {
      if (memeRegion(temp.x,temp.y,a,b)) {
        if (G[a][b] == n) {
          return 0;
        }
      }
    }
  }
  //printf("sapas\n");
  return 1;
}


int memeRegion(int oA, int aA, int oB, int aB) {
  int regA, regB;
  regA = 0;
  regB = 0;
  if (aA < 3) {
    regA = 1;
  } else if(aA < 6) {
    regA = 2;
  } else {
    regA = 3;
  }
  if (oA > 5) {
    regA += 6;
  } else if (oA > 3) {
    regA += 3;
  }

  if (aB < 3) {
    regB = 1;
  } else if(aB < 6) {
    regB = 2;
  } else {
    regB = 3;
  }
  if (oB > 5) {
    regB += 6;
  } else if (oB > 3) {
    regB += 3;
  }
  if (regA == regB)
    return 1;
  else
    return 0;
}


int estCandUnique(Case cible, int n) {
  int i, a, b, sl, ul, uc, ur;
  ul = 1;
  uc = 1;
  ur = 1;
  sl = 0;
  if ((C[cible.x][cible.y].nbc == 1) && (C[cible.x][cible.y].tab[n] == 1))
    sl = 1; //cas ou le candidat est le seul de sa case
  for (i = 0;i < 9;i++) {
    if ((C[cible.x][i].tab[n] == 1) && (cible.y != i))
      ul = 0; //cas ou le candidat n'est pas le seul de la ligne
  }

  for (i = 0;i < 9;i++) {
    if ((C[i][cible.y].tab[n] == 1) && (cible.x != i))
      uc = 0;//cas ou le candidat n'est pas le seul de la colonne
  }

  for (a = 0;a < 9;a++) {
    for (b = 0;b < 9;b++) {
      if (memeRegion(cible.x,cible.y,a,b))
        if (C[a][b].tab[n] == 1)
          ur = 0;//cas ou le candidat n'est pas le seul de la region
    }
  }
  if ((sl) || (!ul) || (!uc) || (!ur)) //1 seule des conditions est suffisante
    return 1;
  else
    return 0;
}


Case rechCaseUnique() {
  int i, j;
  for (i = 0;i < NBO;i++) { //parcourt les cases ouvertes
    //on copie O[i] dans temp
    temp.x = O[i].x;
    temp.y = O[i].y;
    printf("%d %d\n", temp.x, temp.y);
    for (j = 0;j < 9;j++) { //parcourt les candidats
      if (estCandUnique(temp, j)) //verifie si j est candidat unique de temp, donc de O[i]
        return temp;
    }
  }
  //valeurs de retour si aucune case ouverte n'admet de candidat unique
  temp.x = -1;
  temp.y = -1;
  return temp;
}


void initJeu() {
  NBO = 0;
  int a, b, c;
  for (a = 0;a < 9;a++) { //parcourt les lignes
    for (b = 0;b < 9;b++) { //parcourt les colonnes
      if (G[a][b] == 0) { //si la case est ouverte
        O[NBO].x = a;
        O[NBO].y = b;
        NBO ++;
        //on stocke ses coordonnees et on incremente NBO
      }
    }
  }
  //mise a zero de la table C
  for (a = 0;a < 9;a++) {
    for (b = 0;b < 9;b++) {
      C[a][b].nbc = 0;
      C[a][b].tab = malloc(9*sizeof(int));
      for (c = 0;c < 9;c++) {
        C[a][b].tab[c] = 0;
      }
    }
  }
  for (a = 0;a < NBO;a++) { //parcourt les cases ouvertes
    temp.x = O[a].x;
    temp.y = O[a].y;
    //stocke O[a] dans temp
    for (b = 1;b < 10;b++) { //parcourt les candidats
      if (estCand(b)) {
        C[O[a].x][O[a].y].tab[b] = 1;
        C[O[a].x][O[a].y].nbc += 1;
      }
    }
  }
}


void ecrireCand() {
  int a, b, n, i;
  for (i = 0;i < 64;i++) {
    printf("*");
  }
  printf("\n");
  for (a = 0;a < 9;a++) {
    printf("*");
    for (b = 0;b < 9;b++) {
      if (C[a][b].nbc != 0) {
        if (C[a][b].nbc < 6){
          for (i = 0;i < 6-C[a][b].nbc;i++) {
            printf(" ");
          }
        }
        for (n = 1;n < 10;n++) {
          if (C[a][b].tab[n]) {
            printf("%d", n);
          }
        }
      }
      else
        printf("      ");
      switch (b) {
        case 2: case 5: case 8: printf("*");
        break;
        default: printf("|");
        break;
      }
    }
    printf("\n");
    switch (a) {
      case 2: case 5: case 8: {
        for (i = 0;i < 64;i++) {
          printf("*");
        }
        printf("\n");
      }

      break;
      default: printf("*--------------------*--------------------*--------------------*\n");
    }
  }
}


void fermerGrille() {
  int a;
  while(NBO!=0){
      fermerCase();
      printf("Il reste %d case(s) ouverte(s)\n", NBO);
      ecrireGrille(G);
      ecrireCand();
  }

}


void fermerCase() {
  int i, j, a ,z,k,l,w;
  temp = rechCaseUnique();
  for (i = 1;i < 10;i++) {
    if (estCandUnique(temp, i)) {
      G[temp.x][temp.y] = i;
      break;
    }
  }
  for (j = 0;j <=81;j++) {
    if ((O[j].x == temp.x) && (O[j].y == temp.y)) {
      for (a = j;a < NBO;a++) {
        O[a].x = O[a+1].x;
        O[a].y = O[a+1].y;
      }
      --NBO;
    }
  }
  for (z=0 ;  z<=81 ; z++){
    if (appartient(O[z],i)==1)
    {
      for (w=0 ; w<9; w++){
        C[O[z].x][O[z].y].tab[w]=C[O[z].x][O[z].y].tab[w+1];
      }
    }
  }
}