resolution de sudoku

#ifndef SUDOKU_H
#define SUDOKU_H

#define X 9
#define Y 9
#define Z 11

void initialise(int tab[X][Y][Z]);
void remplis(int tab[X][Y][Z]);
int charge(char* adresse,int tab[9][9][11]);
void affiche(int tab[X][Y][Z]);
void affiche3D(int tab[X][Y][Z]);
void afficheProfondeur(int tab [X][Y][Z]);
void elimine(int x, int y, int val, int tab[X][Y][Z]);
void first_road(int tab[X][Y][Z]);
int second_road(int tab[X][Y][Z]);
void place_en_profondeur(int tab [X][Y][Z],int x_min,int y_min,int x_max,int y_max);
void fait_hypothese(int tab[X][Y][Z]);
void fait_hypothese_case(int tab[X][Y][Z], int x, int y);
int hypothese_fausse(int tab[X][Y][Z]);
void retour_arriere(int tab[X][Y][Z]);
void Deep_road(int tab[X][Y][Z]);


#endif

/***************************************************************/
/*              Projet d'algo : Le SUDOKU                      */
/*-------------------------------------------------------------*/
/* Auteurs : PERRUCHON Romain, BESNARD Helena, CABE Benjamin  */
/***************************************************************/
#include <stdlib.h>
#include <stdio.h>

#include "sudoku.h"
#include "pile.h"


int tab[X][Y][Z];
int pas_termine = 81; // nombre de cases du sudoku (9 * 9)
int nb_passage = 1; // nombre de passage
int num_etape = 0; // numero de l'etape
int nb_pl = 0; // nombre de placement
int nb_hypo = 0; // nombre d'hypotheses

pile p; // pile utilisé afin de stocker les hypotheses effectuées et leurs coordonnées

/****************************************************************/
/*        Initialise notre tableau a 3 dimensions              */
/*--------------------------------------------------------------*/
/* met des 0 sur la 3em dimension si la valeur est placée      */
/* met un 1 sur l'index egal a la valeur dans la 3em dimension  */
/* met des 1 dans toute la 3em dimension si la valeur n'est    */
/*                    pas placée                              */
/****************************************************************/
void initialise(int tab[X][Y][Z]){
  int i,j,k;
  for (i = 0; i < X; i++){
    for (j = 0; j < Y; j++){
      for (k = 1; k < Z-1; k++){
   if(tab[i][j][0] != 0){
     tab[i][j][k] = 0;
   }
   else
     tab[i][j][k] = 1;
      }
      if(tab[i][j][0] != 0)
   tab[i][j][tab[i][j][0]] = 1;
    }
  }
}

/****************************************************************/
/*Remplis notre tableau a 3 dimensions avec un sudoku par defaut*/
/*            ( sudoku donnée sur la feuille )                */
/*--------------------------------------------------------------*/
/*        Place les valeurs du sudoku aux bons endroits        */
/****************************************************************/
void remplis(int tab[X][Y][Z]){
  int i,j;
  for (i = 0; i < X; i++){
    for (j = 0; j < Y; j++){
      tab[i][j][0] = 0;
    }
  }

  //placements des valeurs
  tab[1][0][0] = 5;
  tab[2][0][0] = 2;
  tab[5][0][0] = 3;
  tab[8][0][0] = 8;
  tab[3][1][0] = 2;
  tab[7][1][0] = 4;
  tab[0][2][0] = 7;
  tab[1][2][0] = 8;
  tab[3][2][0] = 9;
  tab[5][2][0] = 5;
  tab[6][2][0] = 2;
  tab[0][3][0] = 6;
  tab[1][3][0] = 1;
  tab[4][3][0] = 5;
  tab[5][3][0] = 2;
  tab[8][3][0] = 9;
  tab[1][4][0] = 7;
  tab[2][4][0] = 8;
  tab[4][4][0] = 3;
  tab[7][4][0] = 5;
  tab[8][4][0] = 6;
  tab[3][5][0] = 7;
  tab[6][5][0] = 1;
  tab[7][5][0] = 3;
  tab[1][6][0] = 9;
  tab[4][6][0] = 2;
  tab[6][6][0] = 5;
  tab[7][6][0] = 6;
  tab[1][7][0] = 6;
  tab[2][7][0] = 4;
  tab[4][7][0] = 9;
  tab[8][7][0] = 1;
  tab[0][8][0] = 3;
  tab[2][8][0] = 1;
  tab[4][8][0] = 6;
  tab[5][8][0] = 4;
  tab[6][8][0] = 8;
  pas_termine = 81 - 37; // 37 valeurs sont placés donc il reste 81 - 37 valeurs a placer
}

/****************************************************************/
/*          Charge un sudoku a partir d'un fichier              */
/*--------------------------------------------------------------*/
/*        Place les valeurs du sudoku aux bons endroits        */
/****************************************************************/
int charge(char* adresse,int tab[9][9][11]){
 
  int i=0,j=0,val;
 
  char ligne[3];
  FILE *ficmatrice;

  if ((ficmatrice = fopen(adresse,"r")) == NULL) { // test pour l'ouverture du fichier
    printf("Erreur dans l'ouverture du fichier à l'adresse %s \n",adresse);
    return 0;
  }
  else {
    // remplissage de la profondeur 0 avec des 0
    int k,l;
    for (k = 0; k < X; k++){
      for (l = 0; l < Y; l++){
   tab[k][l][0] = 0;
      }
    }

    //traitement du fichier
    while ( fgets(ligne,sizeof(ligne),ficmatrice) != NULL ){
      val = (int)ligne[0]-48;
      if(val < 0 || val > 9){
   printf("Sudoku non valide\n");
   return 0;
      }
      tab[i][j][0] = val;  //mettre le chiffre dans la grille
      if (val != 0)
   pas_termine--;
      //mise a jour des coordonnées
      i++;
      if (i >= 9) {
   i=0;
   j++;
      }
 
    }
    fclose(ficmatrice); //fermeture du fichier
    return 1;
  }
}

/****************************************************************/
/*      Transfère le résultat du sudoku dans un fichier        */
/*--------------------------------------------------------------*/
/*  créé un fichier en rentrant les valeurs du sodoku final    */
/****************************************************************/
int decharge(char* adresse,int tab[9][9][11]){
  int i=0, j=0, val;
  FILE *ficsortie;   
   
  if ((ficsortie = fopen(adresse,"w")) == NULL) { // test pour l'ouverture du fichier
    printf("Erreur dans la création du fichier à l'adresse %s \n",adresse);
    return 0;
  }
  else {
      for (i=0;i<X;i++){
          for (j=0;j<Y;j++){     
              val = tab[j][i][0];
              fputc(48+val, ficsortie);         
              if (j == 8) fputc('\n', ficsortie);
          }
      }
  }
 fclose(ficsortie);
 return 1;
}


/****************************************************************/
/*            Fonction d'affichage du sudoku                  */
/*--------------------------------------------------------------*/
/*        Affiche simplement et visuellement le sudoku          */
/****************************************************************/
void
affiche(int tab[X][Y][Z]){
  int i, j, k;
  printf ("\n");
  for (j = 0, k = 0; j < Y + 2; j++){
    if(j==3 || j ==7)
      printf(" ");
    else{
      for (i = 0; i < X; i++){
   if (tab[i][k][0] == 0)
     printf(". ");
   else
     printf("%d ", tab[i][k][0]);
   if(i%3 == 2 && i != X-1)
     printf(" ");
      } 
      k++;
    }
    printf ("\n");
  }
  printf ("\n");
}

/****************************************************************/
/*            Fonction d'affichage du sudoku                  */
/*--------------------------------------------------------------*/
/*        Affiche le sudoku jusqu'a sa 3em dimension            */
/* affichage pour verifier les possibilités restantes pour      */
/*    chaque case; Verifie aussi la bonne elimination des      */
/*                      possibiltés                            */
/****************************************************************/
void
affiche3D(int tab[X][Y][Z]){
  int i,j, k;
  for (j = 0; j < Y; j++){
    for (i = 0; i < X; i++){
      printf("%d:%d (val = %d) ", i, j, tab[i][j][0]);
      for (k = 1; k < Z-1; k++)
   printf("[%d] ", tab[i][j][k]);
      printf("  [%d]\n", tab[i][j][Z-1]);
    }
    printf("\n");
  }
}

/****************************************************************/
/*            Fonction d'affichage du sudoku                  */
/*--------------------------------------------------------------*/
/*            Affiche le sudoku en profondeur                  */
/* affichage utlisé pour les mêmes raisons que l'affichage 3D  */
/****************************************************************/
void
afficheProfondeur(int tab [X][Y][Z]){
  int i,j,k;
  for (k = 0; k < Z-1; k++) {
    for (j = 0; j < Y; j++){
      for (i = 0; i < X; i++){
   printf("%d ", tab[i][j][k]);
      } 
      printf ("\n");
    }
    printf ("\n");
  }
}

/****************************************************************/
/*                Placement en profondeur                      */
/*--------------------------------------------------------------*/
/* verifie et elimine le cas echeant si un element est possible */
/* une seule fois dans un carré, une ligne ou une colonne alors */
/*            qu'il a d'autres possibiltés                    */
/****************************************************************/
void
place_en_profondeur(int tab[X][Y][Z], int x_min, int y_min, int x_max, int y_max){
  int i,j,k,pos_x,pos_y;
  int compt;
 
  for(k = 1; k < Z-1; k++){ // profondeur
    compt = 0; // mise a zero du compteur pour chaque profondeur
    for (i = x_min; i <= x_max; i++) { // parcour sur la ligne
      for (j = y_min; j <= y_max; j++) { // parcour sur la colonne
   if (tab[i][j][0] == 0){ // si la valeur est déjà placée : pas besoin de traitement
     if (tab[i][j][k] == 1){ // valeur possible
       compt++; // incrementation du compteur
       pos_y = j; // on garde en memoire la position de j
        pos_x = i; // on garde en memoire la position de i
     }
   }
      }
    }
    if (compt == 1) { // si une seule valeur est possible
      tab[pos_x][pos_y][0] = k; //placement de la valeur
      tab[pos_x][pos_y][Z-1] = num_etape; // placement sur la derniere case du numero de l'etape afin de permettre un retour_arriere
      nb_pl++; // incrementation du nombre de placement
      pas_termine--; // decrementation de la variable de test de terminaison
      elimine(pos_x,pos_y,k,tab); // elimination de l'element placé sur la ligne, la colonne et le carré
    }
  }
}

/****************************************************************/
/*            elimination des possibilités                    */
/*--------------------------------------------------------------*/
/*Si une valeur est placée, alors on fait appel a cette fonction*/
/* qui va se charger d'eliminer ( mettre à num_etape l'index val*/
/* de la 3em dimension ) les possibilités dans le carré ou cette*/
/*      valeur a été placée, dans sa ligne et sa colonne      */
/****************************************************************/
void elimine(int x, int y, int val, int tab[X][Y][Z]){
  int i,j;
  int x_min,x_max,y_min,y_max;
  x_min = x - (x%3);
  y_min = y - (y%3);
  x_max = x + (2 - (x%3));
  y_max = y + (2 - (y%3));

  for (i = 0; i < X; i++){ // elimination de la valeur sur la ligne
    if (tab[i][y][0] == 0 && tab[i][y][val] == 1) // si il n'y a pas de valeur placée et que val est une possibilité pour la case
      tab[i][y][val] = num_etape;
  }
  for (i = 0; i < Y; i++){ // elimination de la valeur sur la colonne
    if (tab[x][i][0] == 0 && tab[x][i][val] == 1) // si il n'y a pas de valeur placée et que val est une possibilité pour la case
      tab[x][i][val] = num_etape;
  }
  for (i = x_min; i <= x_max; i++){ // elimination de la valeur sur le carre
    for (j = y_min; j <= y_max; j++){
      if (tab[i][j][0] == 0 && tab[i][j][val] == 1)
   tab[i][j][val] = num_etape;
    }
  }
}

/****************************************************************/
/*          Fonction first_road : Premier passage              */
/*--------------------------------------------------------------*/
/* Cette fonction effectue un premier passage sur le sudoku    */
/* afin d'eliminer les possibilités sur le carré, la ligne et  */
/*          la colonne des valeurs déjà presentes              */
/****************************************************************/
void first_road(int tab[X][Y][Z]){
  int i,j;
  for (i = 0; i < X; i++)
    for (j = 0; j < Y; j++){
      if (tab[i][j][0] != 0)
   elimine(i,j,tab[i][j][0],tab);
    }   
}

/****************************************************************/
/*        Fonction second_road : passage de placement          */
/*--------------------------------------------------------------*/
/* Cette fonction effectue un passage en profondeur du sudoku  */
/* afin de verifie si une possibilité est la seule pour une case*/
/*                et la placer le cas echeant                  */
/****************************************************************/
int second_road(int tab[X][Y][Z]){
  int i,j,k,comp,val;
  int nb_placement = 0;
  for (i = 0; i < X; i++){
    for (j = 0; j < Y; j++){
      comp = 0;
      if (tab[i][j][0] == 0){
   for (k = 1; k < Z-1; k++){
     if (tab[i][j][k] == 1){
       val = k;
       comp++;
       if (comp > 1)
         break;
     }
   }
      }
      if (comp == 1){
   nb_placement++;
   nb_pl++;
   tab[i][j][0] = val;
   tab[i][j][Z-1] = num_etape; //on retient à quelle etape on a placé l'element
   pas_termine--;
   elimine(i,j,val,tab);
      }
    }
  }
  nb_passage++;
  //printf("\npassage %d (à l'etape %d):\n",nb_passage++, num_etape);
  //printf("nombre de placement : %d\n",nb_placement);
  //printf("nombre d'elements restant a placer : %d\n", pas_termine);
  return nb_placement;
}

/****************************************************************/
/*            Fonction fait_hypothese                          */
/*--------------------------------------------------------------*/
/*  choisit la case où il existe le moins de possibilite sur  */
/*  le sudoku et y fait une hypothese. Si il trouve une case  */
/*  ou il n y a que 2 possibilites, il s'arrete et y fait une  */
/*                        hypothese                            */
/****************************************************************/
void fait_hypothese(int tab[X][Y][Z]){
  int i,j,k,nb_possibilites,min_possibilite;
  int mem_k,mem_i,mem_j,mem2_k;
  min_possibilite = 9;

  for (i = 0; i < X; i++){ // colonne
    for (j = 0; j < Y; j++){ // ligne
      if (tab[i][j][0] == 0) {
   //parcours des possibilités
   //calcul du nombre de chiffres disponibles
   nb_possibilites = 0;
   for (k = 1; k < Z-1; k++) { // profondeur
     if (tab[i][j][k] == 1) {
       nb_possibilites++;
       mem_k = k;
     }
       }
   if (nb_possibilites <= min_possibilite) {
     min_possibilite = nb_possibilites;
     mem_i = i;
     mem_j = j;
     mem2_k = mem_k;
   }
   //si il n'y a que deux possibilités on place la dernière trouvée
   if (nb_possibilites == 2) {
     empiler(&p,i); // empilement de x, y et val de l'hypothese faite
     empiler(&p,j);
     empiler(&p,mem_k);
     tab[i][j][0] = mem_k;
     nb_pl++;
     nb_hypo++;
     if (num_etape == 0) // on passe de l'etape 0 à l'etape 2 (pas d'etape 1)
       num_etape = 2;
     else
       num_etape++; // on incremente le numero de l'etape
     //printf("hypothese : placement en %d;%d du chiffre %d  (etape %d)\n",i,j,mem_k, num_etape);   
     tab[i][j][Z-1] = num_etape;
     pas_termine--;
     elimine(i,j,mem_k,tab); 
     return;
   }
      }
    }
  }
  if(nb_possibilites > 2){
    empiler(&p,mem_i); // empilement de x, y et val de l'hypothese faite
    empiler(&p,mem_j);
    empiler(&p,mem2_k);
    tab[mem_i][mem_j][0] = mem2_k;
    nb_pl++;
    nb_hypo++;
    if (num_etape == 0) // on passe de l'etape 0 à l'etape 2 (pas d'etape 1)
      num_etape = 2;
    else
      num_etape++; // on incremente le numero de l'etape
    //printf("hypothese : placement en %d;%d du chiffre %d  (etape %d)\n",mem_i,mem_j,mem2_k, num_etape);   
    tab[mem_i][mem_j][Z-1] = num_etape;
    pas_termine--;
    elimine(mem_i,mem_j,mem2_k,tab);
    return;
  }
}

/****************************************************************/
/*            Fonction fait_hypothese_case                    */
/*--------------------------------------------------------------*/
/*  Fonction qui effectue une hypothese sur une case precise    */
/*  Si toutes les valeurs possible de cette case ont déjà été  */
/*  une hypothese a une etape donnée, alors on remet a 1 dans  */
/*        ces cases et ont fait un retour_arriere.            */
/*    Dans le cas contraire, on fait une nouvelle hypothese    */
/****************************************************************/
void fait_hypothese_case(int tab[X][Y][Z], int x, int y){
  int k,memk,compt = 0;
  for (k = 1; k < Z-1; k++){
    if (tab[x][y][k] == 1){
      memk = k;
      compt++;
    }
  }
  if(compt == 0) {
    for (k = 1; k < Z-1; k++){
      if(tab[x][y][k] == -num_etape-1)
   tab[x][y][k] = 1;
    }
    retour_arriere(tab);
  }
  else {
    empiler(&p,x); // empilement de x, y et val de l'hypothese faite
    empiler(&p,y);
    empiler(&p,memk);
    tab[x][y][0] = memk;
    nb_pl++;
    nb_hypo++;
    if (num_etape == 0) // on passe de l'etape 0 à l'etape 2 (pas d'etape 1)
      num_etape = 2;
    else
      num_etape++; // on incremente le numero de l'etape
    //printf("hypothese : placement en %d;%d du chiffre %d  (etape %d)\n",x,y,memk, num_etape);   
    tab[x][y][10] = num_etape;
    pas_termine--;
    elimine(x,y,memk,tab); 
    return;
  }
}


/****************************************************************/
/*            Fonction hypothese_fausse                        */
/*--------------------------------------------------------------*/
/*    Fonction de verification de la veracité de l'hypothese    */
/*                  effectué auparavent                        */
/*                                                              */
/****************************************************************/
int hypothese_fausse(int tab[X][Y][Z]){
  int i,j,k,nb_possibilites;
 
  for (i = 0; i < X; i++){
    for (j = 0; j < Y; j++){
      if (tab[i][j][0] == 0) {
         //parcours des possibilités
   //calcul du nombre de chiffres disponibles
   nb_possibilites = 0;
   for (k = 1; k < Z-1; k++) {
     if (tab[i][j][k] == 1) {
       nb_possibilites++;
     }
   }
   if (nb_possibilites == 0) {
     //printf("hypothese fausse en %d / %d\n", i, j);
     return 1;                   
   }               
      }
    }
  }   
 
  return 0; 
}

/********************************************************************/
/*                  Fonction retour_arriere                        */
/********************************************************************/
/*parcourir toutes les profondeurs du tableau et remettre à 1 toutes*/
/*          les valeurs égales au numero de l'etape                */
/*  Si pour une case l'element à été placé au numero de l'etape    */
/*                  actuelle, l'enlever                            */
/* Si on est à l'etat de la toute premiere hypothese, on peut      */
/* supprimmer l'hypothese qu'on a fait de la liste des possibilités */
/*                        de cette case                            */
/*                Decrementer le numero de l'etape                  */
/********************************************************************/
void retour_arriere(int tab[X][Y][Z]){
  int i,j,k,val_hypo,x_hypo,y_hypo;
  for (i = 0; i < X; i++){
    for (j = 0; j < Y; j++){
      for (k = 1; k < Z-1; k++){
   if (tab[i][j][k] == num_etape){
     tab[i][j][k] = 1;
   }
      }
      if (tab[i][j][10] == num_etape){
   tab[i][j][0] = 0;
   tab[i][j][10] = 0;
   pas_termine++;
      }
    }
  }
  // on recupere l'hypothese precedente avec ses coordonnees
  val_hypo = depiler(&p);
  y_hypo = depiler(&p);
  x_hypo = depiler(&p);
 
  if (num_etape == 2) {//etape de base (1ere hypothese)
    num_etape = 0;
    tab[x_hypo][y_hypo][val_hypo] = 0; // on peut eliminer la valeur d'hypothese de la liste des possibilité de la case ou on a fait l'hypothese
  }
  else {
    tab[x_hypo][y_hypo][val_hypo] = -num_etape;
    num_etape--;
    // nouvelle hypo sur la case x_hypo/y_hypo
    fait_hypothese_case(tab,x_hypo,y_hypo);
  }
  //printf("retour en arriere effectué !\n");
}
/****************************************************************/
/*                  Fonction Deep_road                          */
/****************************************************************/
void
Deep_road(int tab[X][Y][Z]){
  int tmp,l,c;
  //printf("\nelimination en profondeur\n\n");
  do {  // on elimine en profondeur pour chaque carré, ligne et colonne
    tmp = pas_termine; // affectation afin de verifier si on doit continuer ou non a faire des placements on profondeur
   
    // carrés
    place_en_profondeur(tab,0,0,2,2);
    place_en_profondeur(tab,3,0,5,2);
    place_en_profondeur(tab,6,0,8,2);
    place_en_profondeur(tab,0,3,2,5);
    place_en_profondeur(tab,3,3,5,5);
    place_en_profondeur(tab,6,3,8,5);
    place_en_profondeur(tab,0,6,2,8);
    place_en_profondeur(tab,3,6,5,8);
    place_en_profondeur(tab,6,6,8,8);
   
    // lignes
    for (l = 0; l < X; l++){
      place_en_profondeur(tab,0,8,l,l);// une ligne
    }
   
    // colonnes
    for (c = 0; c < Y; c++){
      place_en_profondeur(tab,c,c,0,8);// une colonne
    }
   
    //affiche(tab);
    //printf("nombre de placement : %d\n",nb_pl);
    //printf("nombre d'elements restant a placer : %d\n", pas_termine);
   
  }while (tmp != pas_termine); // test de verification du prolongement benefique ou non du placement en profondeur
}

void stats(){
  printf("nombre de passages effectues : %d\n",nb_passage);
  printf("sudoku resolu a l'etape : %d\n", num_etape);
  printf("nombre de placement total effectué : %d\n", nb_pl);
  if(nb_hypo > 0){
    printf("Le programme a du passer par le cas indeterministe afin de resoudre le sudoku\n");
    printf("nombre d'hypotheses effectues : %d\n",nb_hypo);
    if(nb_hypo > 5){
      if(nb_hypo > 20)
   printf("Difficulte du sudoku : DIABOLIQUE\n");
      else
   printf("Difficulte du sudoku : DIFFICILE\n");
    }
    else
      printf("Difficulte du sudoku : MOYEN\n");
  }
  else {
    printf("Le sudoku a été resolu entierement avec le cas deterministe\n");
    printf("Difficulte du sudoku : FACILE\n");
  }
}

/****************************************************************/
/*                          main                                */
/****************************************************************/
int
main(int argc, char* argv[]){
  int bon_chargement,tmp2;
  if (argc > 2){ // verification du nombre d'arguments
    printf("Utilisation : ./sudoku [fichier]");
    return EXIT_FAILURE;
  }
  else {
    if (argc == 2){ // si il y a un argument => le nom d'un fichier a charger
      bon_chargement = charge(argv[1],tab);
      if (bon_chargement == 0) // le fichier est mal chargé
   return EXIT_FAILURE;
    }
    else{
      remplis(tab);
    }
    initialise(tab);
  }

  // premier passsage
  first_road(tab);
  printf("sudoku de depart : \n");
  affiche(tab);

  while (second_road(tab)){
  }

  if (pas_termine) {
    Deep_road(tab);
  }
  else {
    affiche(tab);
    printf("\nsudoku resolu !\n");
    decharge("ficsortie",tab);
    stats();
    return EXIT_SUCCESS;
  }

  if (pas_termine) {
    do {
      //passage au cas non deterministe
      tmp2 = pas_termine;
      fait_hypothese(tab);
      while (second_road(tab)){
      }
      if (hypothese_fausse(tab)){
   if(num_etape == 0){
     printf("sudoku non resolvable car faux au depart\n");
     return 0;
   }
   retour_arriere(tab);
   while (second_road(tab)){
   }
      }
      else {
   if(pas_termine) // verification afin d'eviter de passer dans la Deep_road pour rien
     Deep_road(tab);
      }
    }while (pas_termine);
  }
  else{
    affiche(tab);
    printf("\nsudoku resolu !\n");
    decharge("ficsortie",tab);
    stats();
    return EXIT_SUCCESS;
  }

  affiche(tab);
  printf("\nsudoku resolu !\n");
  decharge("ficsortie",tab);
  stats();
  return EXIT_SUCCESS;
}