/************
SUDOKU
BACKTRACKING
Fevrier 2008
*************/

#include <stdio.h>
#include <string.h>
/* dimension du cote des petits carres */
#define MIN 3
/* dimension du cote du grand carre */
#define MAX 9
/* code de sortie des fonctions */
#define FAUX 0
#define VRAI 1

char grille[MAX][MAX]; /* la grille */
long int g_comp_tests; /* compteur de tests */
int g_flag_affiche; /* Drapeau d'option d'affichage de l'option -a */
/********/
int main(int argc, char *argv[]);
int parametre_affichage(char t[]);
/**** SAISIES ET VERIFICATIONS ****/
int saisie_grille(void);
int saisie_une_ligne(int ligne);
int verif_saisie_grille(void);
int verif_saisie_lignes(void);
int verif_saisie_une_ligne(int ligne);
int verif_saisie_colonnes(void);
int verif_saisie_une_colonne(int col);
int verif_saisie_carres(void);
int verif_saisie_un_carre(int carre);
void trans_carre(char tamp[], int carre);
/**** RESOLUTION ****/
void resolve(void);
int case_dispo_nbre(int nbre, int ligne, int col);
void trans_carre_de_case(char tamp[], int ligne, int col);
/**** DIVERS ****/
void affiche_grille_attente(void);
void affiche_grille(void);
void affiche_chaine(int nbre);
int grille_finie(void);
void attente(void);

/******/
int main(int argc, char *argv[])
/******/
{
.   /* option d'affichage dans la fontion resolve */
.   g_flag_affiche = ((argc> = 2) && (parametre_affichage(argv[1])));
.   /**********/
.   printf("\n******* SUDOKU *******\n\n");
.   printf("l'option sudoku -a affiche la resolution case par case.\n\n");
.   printf("Saisissez %d lignes de %d chiffres,\n", MAX, MAX);
.   printf("les chiffres peuvent etre separes par n'importe quels caracteres\n");
.   printf("Rentrez un 0 pour chaque case vide.\n");
.   printf("Pour quitter le programme, valider la lettre Q.\n\n");
.   while (saisie_grille()) {
.   .   g_comp_tests = 0;
.   .   resolve();
.   .   affiche_grille();
.   .   if (! grille_finie()) printf("Enonce errone...\n");
.   .   printf("Tests : %ld\n\n", g_comp_tests);
.   }/* end while */
.   printf("\n");
.   return 0;
}

/**********************/
int parametre_affichage(char t[])
/**********************/
{
.   /* Renvoi VRAI si l'utilisateur a taper une demande d'option d'affichage
.   sous la forme : a, A, ou /a , /A , -a , -A ect... sinon renvoi FAUX */
.   char param;
.   if (strlen(t) == 1) param = t[0];
.   else if (strlen(t) == 2) param = t[1];
.   else param = 0;
.   return ((param == 'A') || (param == 'a'));
}/* end parametre_affichage */

/**********************************/
/**** SAISIES ET VERIFICATIONS ****/
/**********************************/

/***************/
int saisie_grille(void)
/***************/
{/* l'utilisateur saisie 9 lignes de 9 chiffres */
.   int ligne;
.   printf("Saisissez votre grille : \n");
.   while (VRAI){
.   .   for (ligne = 0; ligne < MAX; ligne++){
.   .   .   if (! saisie_une_ligne(ligne)) return (FAUX);
.   .   }/* end for */
.   .   printf("\nEnonce : \n");
.   .   affiche_grille();
.   .   if (verif_saisie_grille()) return(VRAI);
.   .   else printf("\n");
.   }/* end while */
}/* end saisie */

/******************/
int saisie_une_ligne(int ligne)
/******************/
{
/* l'utilisateur doit saisir une ligne de 0 a 9 chiffres
separes ou non par un ou plusieurs carateres.
Seuls les 9 premiers chiffres seront retenus.
Le + pratique : pave numerique et mettre un point
tous les 3 chiffres
Eviter d'utiliser gets() a cause des debordements.
Penser a vider entierement le buffer */
.   int c, i;
.   int col = 0;
.   int result = VRAI;
.   /* RAZ des cases de la ligne */
.   for (i = 0; i < MAX; i++) {
.   .   grille[ligne][i] = 0;
.   }/* for */
.   /*******/
.   printf("Ligne %d : ", ligne+1);
.   while(VRAI){
.   .   c = fgetc(stdin);
.   .   if (c == feof(stdin) || c == 0x0A) return result;
.   .   else if ((c == 'Q') || (c == 'q')) result = FAUX;
.   .   /* transfert de la saisie dans les cases de la ligne */
.   .   else if ( (result) && (col < MAX) && (c >= '0') && (c <= '9')) {
.   .   .   grille[ligne][col++] = c-48;
.   .   }/*end if */
.   }/* end while */
}/*end saisie_une_ligne */

/*********************/
int verif_saisie_grille(void)
/*********************/
{/* verifie si pas de doublon dans l'ensemble de la grille */
.   int result = VRAI;
.   if (! verif_saisie_lignes()) result = FAUX;
.   if (! verif_saisie_colonnes()) result = FAUX;
.   if (! verif_saisie_carres()) result = FAUX;
.   return result;
}/* end verif_saisie_grille */

/*********************/
int verif_saisie_lignes(void)
/*********************/
{/* verifie si pas de doublon dans les lignes */
.   int ligne;
.   int result = VRAI;
.   for (ligne = 0; ligne < MAX; ligne++) {
.   .   if (! verif_saisie_une_ligne(ligne)) result = FAUX;
.   }/* end for */
.   return result;
}/* end verif_saisie_lignes */

/************************/
int verif_saisie_une_ligne(int ligne)
/************************/
{/* verifie si pas de doublon dans la ligne */
.   int i,j;
.   for (i = 0; i < MAX-1; i++) {
.   .   if ( grille[ligne][i] == 0 ) continue;
.   .   for (j = i+1; j < MAX; j++) {
.   .   .   if (grille[ligne][i] == grille[ligne][j]) {
.   .   .   .   printf("Erreur ligne %d : chiffres egaux\n", ligne+1);
.   .   .   .   return FAUX;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VRAI;
}/* end verif_saisie_une_ligne */

/***********************/
int verif_saisie_colonnes(void)
/***********************/
{/* verifie si pas de doublon dans les colonnes */
.   int col;
.   int result = VRAI;
.   for (col = 0; col < MAX; col++) {
.   .   if (! verif_saisie_une_colonne(col)) result = FAUX;
.   }/* end for */
.   return result;
}/* end verif_saisie_colonnes */

/**************************/
int verif_saisie_une_colonne(int col)
/**************************/
{/* verifie si pas de doublon dans la colonne */
.   int i, j;
.   for (i = 0; i < MAX-1; i++) {
.   .   if ( grille[i][col] == 0 ) continue;
.   .   for (j = i+1; j < MAX; j++) {
.   .   .   if (grille[i][col] == grille[j][col]) {
.   .   .   .   printf("Erreur colonne %d : chiffres egaux\n", col+1);
.   .   .   .   return FAUX;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VRAI;
}/* end verif_saisie_une_colonne */

/*********************/
int verif_saisie_carres(void)
/*********************/
{/* verifie si pas de doublon dans les carres de 3 X 3 */
.   int carre;
.   int result = VRAI;
.   for (carre = 0; carre < MAX; carre++) {
.   .   if (! verif_saisie_un_carre(carre)) result = FAUX;
.   }/* end for */
.   return result;
}/* end verif_saisie_carres */

/***********************/
int verif_saisie_un_carre(int carre)
/***********************/
{/* verifie si pas de doublon dans le carre de 3 X 3 */
.   char tamp[MAX+10];
.   int i, j;
.   trans_carre(tamp, carre);
.   for (i = 0; i < MAX-1; i++) {
.   .   if (tamp[i] == 0 ) continue;
.   .   for (j = i+1; j < MAX; j++) {
.   .   .   if (tamp[i] == tamp[j]) {
.   .   .   .   printf("Erreur carre %d : chiffres egaux\n", carre+1);
.   .   .   .   return FAUX;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VRAI;
}/* end verif_saisie_un_carre */

/**************/
void trans_carre(char tamp[], int carre)
/**************/
{/* transfert le carre de 3 X 3 dans un tableau a une dimension */
.   int i,j, x,y,z;
.   x = (((carre) % MIN)*MIN);
.   y = (((carre+MIN) / MIN)*MIN)-MIN;
.   z = 0;
.   for (j = y; j < y+MIN; j++) {
.   .   for (i = x; i < x+MIN; i++) {
.   .   .   tamp[z++] = grille[j][i];
.   .   }/* end for i */
.   }/* end for j */
}/* end trans_carre */

/********************/
/**** RESOLUTION ****/
/********************/

/**********/
void resolve(void)
/**********/
{/* Attention, fonction recursive... */
.   int ligne, col, nbre, nbre_tamp;
.   for (ligne = 0; ligne < MAX; ligne++) {
.   .   for (col = 0; col < MAX; col++) {
.   .   .   if (grille[ligne][col]) continue;
.   .   .   for (nbre = 1; nbre <= MAX; nbre++) {
.   .   .   .   if (! case_dispo_nbre(nbre, ligne, col)) continue;
.   .   .   .   nbre_tamp = grille[ligne][col];
.   .   .   .   grille[ligne][col] = nbre;
.   .   .   .   g_comp_tests++;
.   .   .   .   if (g_flag_affiche) affiche_grille_attente();
.   .   .   .   resolve();
.   .   .   .   if (grille_finie()) return;
.   .   .   .   /* pour voir toutes les solutions des grilles
.   .   .   .   a solutions multiples
.   .   .   .   mettre en rem la ligne du dessus et
.   .   .   .   retirer le rem de la ligne du dessous */
.   .   .   .   /* if (grille_finie()) affiche_grille_attente(); */
.   .   .   .   grille[ligne][col] = nbre_tamp;
.   .   .   }/* end for nbre */
.   .   .   return;
.   .   }/* end for col */
.   }/* end for ligne */
.   return;
}/* end resolve */

/******************/
int case_dispo_nbre(int nbre, int ligne, int col)
/******************/
{
/* teste si le nbre est deja place dans
la ligne, ou la colonne, ou le carre de 3 X 3
afferent a la case pointee par ligne, col */
.   char tamp[MAX+10];
.   int i;
.   /*si nbre est utilise dans la ligne, renvoi FAUX */
.   for (i = 0; i < MAX; i++) if (grille[ligne][i] == nbre) return(FAUX);
.   /*si nbre est utilise dans la colonne, renvoi FAUX */
.   for (i = 0; i < MAX; i++) if (grille[i][col] == nbre) return(FAUX);
.   /*si nbre est utilise dans le mini carre, renvoi FAUX */
.   trans_carre_de_case(tamp, ligne, col);
.   for (i = 0; i < MAX; i++) if (tamp[i] == nbre) return (FAUX);
.   /*donc nbre est diponible pour la case */
.   return(VRAI);
}/* end case_dispo_nbre */

/**********************/
void trans_carre_de_case(char tamp[], int ligne, int col)
/**********************/
/* tranfert le carre de 3 X 3 d'une
case dans un tableau a une dimension */
{
.   int i, j, k;
.   while ((ligne % MIN) != 0) ligne--;
.   while ((col % MIN) != 0) col--;
.   k = 0;
.   for (j = ligne; j < ligne+MIN; j++) {
.   .   for (i = col; i < col+MIN; i++) {
.   .   .   tamp[++k] = grille[j][i];
.   .   }/* end for i */
.   }/* end for j */
}/* end trans_carre_de_case */

/****************/
/**** DIVERS ****/
/****************/

/*************************/
void affiche_grille_attente(void)
/*************************/
{/* affiche la grille avec mise en attente de la touche entree */
.   affiche_grille();
.   printf("%ld, Touche entree pour la suite...", g_comp_tests);
.   attente();
}/* end option_affiche */

/*****************/
void affiche_grille(void)
/*****************/
{/* affiche l'ensemble de la grille */
.   int ligne, col;
.   for (ligne = 0; ligne < MAX; ligne++) {
.   .   for (col = 0; col < MAX; col++) {
.   .   .   printf(" %1d ", grille[ligne][col]);
.   .   .   if ( ((col % MIN) == MIN-1) && (col < MAX-1) ) {
.   .   .   .   printf(" | ");
.   .   .   }
.   .   }/* end for col */
.   .   printf("\n");
.   .   if ( ((ligne % MIN) == MIN-1) && (ligne < MAX-1) ) {
.   .   .   affiche_chaine(33);
.   .   }
.   }/* end for ligne */
.   printf("\n");
}/* end affiche_grille */

/*****************/
void affiche_chaine(int nbre)
/*****************/
{/* Affiche une suite de caractere etoile */
.   int i;
.   for (i = 1; i <= nbre; i++) {
.   .   printf("*");
.   }
.   printf("\n");
}/* end affiche_chaine */

/**************/
int grille_finie(void)
/**************/
/* teste si la grille est finie.
Retourne VRAI si grille finie, sinon retourne FAUX.
Commence par la fin de la grille
celle ci ce completant par son debut */
{
.   int ligne, col;
.   for (ligne = MAX-1; ligne >= 0; ligne--) {
.   .   for (col = MAX-1; col >= 0; col--) {
.   .   .   if (grille[ligne][col] == 0 ) {
.   .   .   .   return FAUX;
.   .   .   }
.   .   }/* end for col */
.   }/* end for ligne */
.   return VRAI;
}/* end grille_finie */

/**********/
void attente(void)
/**********/
{/* attente de la touche entree au clavier */
.   char c;
.   while(VRAI){
.   .   c = fgetc(stdin);
.   .   if (c == feof(stdin) || c == 0x0A) return;
.   }/* end while */
}/* end attente */