/************
SUDOKU
BACKTRACKING
Febbraio 2013
*************/

#include <stdio.h>
#include <string.h>
/* Dimensione del lato dei piccoli quadrati. */
#define MIN 3
/* Dimensione del lato del grande quadrato. */
#define MAS 9
/* Codice d'uscita delle funzioni. */
#define FALSO 0
#define VERO 1

char griglia[MAS][MAS]; /* la griglia */
long int g_conta_test; /* contatore dei test */
int g_flag_affissione; /* bandiera d'opzione di affissione dell'opzione -a */
/********/
int main(int argc, char *argv[]);
int parametro_affissione(char t[]);
/**** INSERIMENTI E CONTROLLI ****/
int inserimento_griglia(void);
int inserimento_una_linea(int linea);
int verif_inserimento_griglia(void);
int verif_inserimento_linee(void);
int verif_inserimento_una_linea(int linea);
int verif_inserimento_colonne(void);
int verif_inserimento_una_colonna(int col);
int verif_inserimento_quadrati(void);
int verif_inserimento_un_quadrato(int quadrato);
void trasferimento_quadrato(char tamp[], int quadrato);
/**** RISOLUZIONE ****/
void risolvere(void);
int casella_dispo_numero(int numero, int linea, int col);
void trasferimento_quadato_3_di_3(char tamp[], int linea, int col);
/**** DIVERSI ****/
void affissione_griglia_attesa(void);
void affissione_griglia(void);
void affissione_stringa(int lunghezza);
int griglia_finita(void);
void attesa(void);

/******/
int main(int argc, char *argv[])
/******/
{
.   /* Opzione di affissione nella funzione risolvere. */
.   g_flag_affissione = ((argc >= 2) && (parametro_affissione(argv[1])));
.   /**********/
.   printf("\n******* SUDOKU *******\n\n");
.   printf("l'opzione sudoku -a mostra la risoluzione casella per casella.\n\n");
.   printf("Inserite %d linee di %d cifre.\n", MAS, MAS);
.   printf("Le cifre possono essere separate da qualsiasi caratteri.\n");
.   printf("Inserite uno 0 per ogni casella vuota.\n");
.   printf("Per uscire dal programma, inserite la lettera U.\n\n");
.   while (inserimento_griglia()) {
.   .   g_conta_test = 0;
.   .   risolvere();
.   .   affissione_griglia();
.   .   if (! griglia_finita()) printf("Problema sudoku erroneo...\n");
.   .   printf("Test: %ld\n\n", g_conta_test);
.   }/* end while */
.   printf("\n");
.   return 0;
}

/**********************/
int parametro_affissione(char t[])
/**********************/
{
.   /* Rinvio VERO se l'utente ha inserito un opzione di affissione:
.   a, A, /a , /A , -a , -A ecc... Altrimenti rinvio FALSO */
.   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 parametro_affissione */

/*********************************/
/**** INSERIMENTI E CONTROLLI ****/
/*********************************/

/*********************/
int inserimento_griglia(void)
/*********************/
{/* L'utente inserisce 9 linee di 9 cifre. */
.   int linea;
.   printf("Inserite vostra griglia sudoku:\n");
.   while (VERO){
.   .   for (linea = 0; linea < MAS; linea++){
.   .   .   if (! inserimento_una_linea(linea)) return (FALSO);
.   .   }/* end for */
.   .   printf("\nIl vostro problema sudoku:\n");
.   .   affissione_griglia();
.   .   if (verif_inserimento_griglia()) return(VERO);
.   .   else printf("\n");
.   }/* end while */
}/* inserimento_griglia */

/***********************/
int inserimento_una_linea(int linea)
/***********************/
{
/* L'utente deve inserire una linea
di 9 cifre separati o no da caratteri.
Solo le prime 9 cifre saranno prese in considerazione.
Il più pratico: Utilizzate il tastierino numerico e
inserire un punto ogni 3 cifre. Esempio: 103.006.709
Evitare di utilizzare gets () a causa degli tamponi troppo pieno.
Altrimenti ricordarsi di svuotare interamente lo buffer. */
.   int c, i;
.   int col = 0;
.   int result = VERO;
.   /* Riduzione a zero delle caselle della linea. */
.   for (i = 0; i < MAS; i++) {
.   .   griglia[linea][i] = 0;
.   }/* for */
.   /*******/
.   printf("Linea %d: ", linea+1);
.   while(VERO){
.   .   c = fgetc(stdin);
.   .   if (c == feof(stdin) || c == 0x0A) return result;
.   .   else if ((c == 'U') || (c == 'u')) result = FALSO;
.   .   /* Trasferimento dell'inserimento nelle caselle della linea. */
.   .   else if ( (result) && (col < MAS) && (c >= '0') && (c <= '9')) {
.   .   .   griglia[linea][col++] = c-48;
.   .   }/*end if */
.   }/* end while */
}/*end inserimento_una_linea */

/***************************/
int verif_inserimento_griglia(void)
/***************************/
{/* Verifica se no di doppione nella griglia sudoku. */
.   int result = VERO;
.   if (! verif_inserimento_linee()) result = FALSO;
.   if (! verif_inserimento_colonne()) result = FALSO;
.   if (! verif_inserimento_quadrati()) result = FALSO;
.   return result;
}/* end verif_inserimento_griglia */

/*************************/
int verif_inserimento_linee(void)
/*************************/
{/* Verifica se no di doppione nelle linee. */
.   int linea;
.   int result = VERO;
.   for (linea = 0; linea < MAS; linea++) {
.   .   if (! verif_inserimento_una_linea(linea)) result = FALSO;
.   }/* end for */
.   return result;
}/* end verif_inserimento_linee */

/*****************************/
int verif_inserimento_una_linea(int linea)
/*****************************/
{/* Verifica se no di doppione nella linea. */
.   int i,j;
.   for (i = 0; i < MAS-1; i++) {
.   .   if ( griglia[linea][i] == 0 ) continue;
.   .   for (j = i+1; j < MAS; j++) {
.   .   .   if (griglia[linea][i] == griglia[linea][j]) {
.   .   .   .   printf("Errore linea %d: Cifre uguali.\n", linea+1);
.   .   .   .   return FALSO;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VERO;
}/* end verif_inserimento_una_linea */

/***************************/
int verif_inserimento_colonne(void)
/***************************/
{/* Verifica se no di doppione nelle colonne. */
.   int col;
.   int result = VERO;
.   for (col = 0; col < MAS; col++) {
.   .   if (! verif_inserimento_una_colonna(col)) result = FALSO;
.   }/* end for */
.   return result;
}/* end verif_inserimento_colonne */

/*******************************/
int verif_inserimento_una_colonna(int col)
/*******************************/
{/* Verifica se no di doppione nella colonna. */
.   int i, j;
.   for (i = 0; i < MAS-1; i++) {
.   .   if ( griglia[i][col] == 0 ) continue;
.   .   for (j = i+1; j < MAS; j++) {
.   .   .   if (griglia[i][col] == griglia[j][col]) {
.   .   .   .   printf("Errore colonna %d: Cifre uguali.\n", col+1);
.   .   .   .   return FALSO;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VERO;
}/* end verif_inserimento_una_colonna */

/****************************/
int verif_inserimento_quadrati(void)
/****************************/
{/* Verifica se no di doppione nei quadrati di 3 x 3. */
.   int quadrato;
.   int result = VERO;
.   for (quadrato = 0; quadrato < MAS; quadrato++) {
.   .   if (! verif_inserimento_un_quadrato(quadrato)) result = FALSO;
.   }/* end for */
.   return result;
}/* end verif_inserimento_quadrati */

/*******************************/
int verif_inserimento_un_quadrato(int quadrato)
/*******************************/
{/* Verifica se no di doppione nel quadrato di 3 x 3. */
.   char tamp[MAS+10];
.   int i, j;
.   trasferimento_quadrato(tamp, quadrato);
.   for (i = 0; i < MAS-1; i++) {
.   .   if (tamp[i] == 0 ) continue;
.   .   for (j = i+1; j < MAS; j++) {
.   .   .   if (tamp[i] == tamp[j]) {
.   .   .   .   printf("Errore quadrato %d: Cifre uguali.\n", quadrato+1);
.   .   .   .   return FALSO;
.   .   .   }/* end if */
.   .   }/* end for j */
.   }/* end for i */
.   return VERO;
}/* end verif_inserimento_un_quadrato */

/*************************/
void trasferimento_quadrato(char tamp[], int quadrato)
/*************************/
{/* Trasferimento il quadrato 3 x 3 in una matrice unidimensionale. */
.   int i,j, x,y,z;
.   x = (((quadrato) % MIN)*MIN);
.   y = (((quadrato+MIN) / MIN)*MIN)-MIN;
.   z = 0;
.   for (j = y; j < y+MIN; j++) {
.   .   for (i = x; i < x+MIN; i++) {
.   .   .   tamp[z++] = griglia[j][i];
.   .   }/* end for i */
.   }/* end for j */
}/* end trasferimento_quadrato */

/*********************/
/**** RISOLUZIONE ****/
/*********************/

/************/
void risolvere(void)
/************/
{/* Attenzione, funzione ricorsiva... */
.   int linea, col, numero, num_tamp;
.   for (linea = 0; linea < MAS; linea++) {
.   .   for (col = 0; col < MAS; col++) {
.   .   .   if (griglia[linea][col]) continue;
.   .   .   for (numero = 1; numero <= MAS; numero++) {
.   .   .   .   if (! casella_dispo_numero(numero, linea, col)) continue;
.   .   .   .   num_tamp = griglia[linea][col];
.   .   .   .   griglia[linea][col] = numero;
.   .   .   .   g_conta_test++;
.   .   .   .   if (g_flag_affissione) affissione_griglia_attesa();
.   .   .   .   risolvere();
.   .   .   .   if (griglia_finita()) return;
.   .   .   .   /* Per vedere tutte le soluzioni
.   .   .   .   delle griglie sudoku a soluzioni multiple
.   .   .   .   mettere in rem la linea della cima e
.   .   .   .   ritirare il rem della linea del sotto. */
.   .   .   .   /* if (griglia_finita()) affissione_griglia_attesa(); */
.   .   .   .   griglia[linea][col] = num_tamp;
.   .   .   }/* end for numero */
.   .   .   return;
.   .   }/* end for col */
.   }/* end for linea */
.   return;
}/* end risolvere */

/**********************/
int casella_dispo_numero(int numero, int linea, int col)
/**********************/
{
/* Prova se il numero è già messo
in la linea, o in la colonna, o in il quadrato di 3 X 3
afferente alla casella indicata da linea, col. */
.   char tamp[MAS+10];
.   int i;
.   /* Se il numero è utilizza nella linea, rinvio FALSO. */
.   for (i = 0; i < MAS; i++) if (griglia[linea][i] == numero) return(FALSO);
.   /* Se il numero è utilizza nella colonna, rinvio FALSO. */
.   for (i = 0; i < MAS; i++) if (griglia[i][col] == numero) return(FALSO);
.   /* Se il numero è utilizza nel quadrato, rinvio FALSO */
.   trasferimento_quadato_3_di_3(tamp, linea, col);
.   for (i = 0; i < MAS; i++) if (tamp[i] == numero) return (FALSO);
.   /* Dunque il numero è disponibile per la casella. */
.   return(VERO);
}/* end casella_dispo_numero */

/*******************************/
void trasferimento_quadato_3_di_3(char tamp[], int linea, int col)
/*******************************/
/* Trasferimento il quadrato di 3 X 3 afferente
ad una casella in una matrice unidimensionale. */
{
.   int i, j, k;
.   while ((linea % MIN) != 0) linea--;
.   while ((col % MIN) != 0) col--;
.   k = 0;
.   for (j = linea; j < linea+MIN; j++) {
.   .   for (i = col; i < col+MIN; i++) {
.   .   .   tamp[++k] = griglia[j][i];
.   .   }/* end for i */
.   }/* end for j */
}/* end trasferimento_quadato_3_di_3 */

/*****************/
/**** DIVERSO ****/
/*****************/

/****************************/
void affissione_griglia_attesa(void)
/****************************/
{/* Mostra la griglia di sudoku con messa in attesa del tasto entra. */
.   affissione_griglia();
.   printf("%ld, Tasto entra per il seguito...", g_conta_test);
.   attesa();
}/* end affissione_griglia_attesa */

/*********************/
void affissione_griglia(void)
/*********************/
{/* Mostra la griglia di sudoku */
.   int linea, col;
.   for (linea = 0; linea < MAS; linea++) {
.   .   for (col = 0; col < MAS; col++) {
.   .   .   printf(" %1d ", griglia[linea][col]);
.   .   .   if ( ((col % MIN) == MIN-1) && (col < MAS-1) ) {
.   .   .   .   printf(" | ");
.   .   .   }
.   .   }/* end for col */
.   .   printf("\n");
.   .   if ( ((linea % MIN) == MIN-1) && (linea < MAS-1) ) {
.   .   .   affissione_stringa(33);
.   .   }
.   }/* end for linea */
.   printf("\n");
}/* end affissione_griglia */

/*********************/
void affissione_stringa(int lunghezza)
/*********************/
{/* Affissione una stringa di carattere asterisco. */
.   int i;
.   for (i = 1; i <= lunghezza; i++) {
.   .   printf("*");
.   }
.   printf("\n");
}/* end affissione_stringa */

/****************/
int griglia_finita(void)
/****************/
/* Prova se la griglia sudoku è finita.
Rinvio VERO se la griglia è finita, altrimenti rinvio FALSO.
Comincia con la fine della griglia. */
{
.   int linea, col;
.   for (linea = MAS-1; linea >= 0; linea--) {
.   .   for (col = MAS-1; col >= 0; col--) {
.   .   .   if (griglia[linea][col] == 0 ) {
.   .   .   .   return FALSO;
.   .   .   }
.   .   }/* end for col */
.   }/* end for linea */
.   return VERO;
}/* end griglia_finita */

/*********/
void attesa(void)
/*********/
{/* Attesa del tasto entra alla tastiera. */
.   char c;
.   while(VERO){
.   .   c = fgetc(stdin);
.   .   if (c == feof(stdin) || c == 0x0A) return;
.   }/* end while */
}/* end attesa */