/*
   Risolutore di Sudoku, versione 1.1
   Autore: Francesco Bottacin
   Data: Maggio 2009
   Descrizione: risolve un Sudoku classico 9 x 9
   Puo' trovare tutte le soluzioni possibili e scriverle in un file.
   Dopo aver trovato una soluzione viene chiesto se si vuole continuare a cercarne altre.
   Uso: sudoku [-o outfile] [-t outfile] filedati
        il filedati e' un file di testo che contiene i dati iniziali nel seguente formato:

        i_1 j_1 val_1 \n
        i_2 j_2 val_2 \n
        .........

        dove val_h e' il numero da inserire nella casella di posto (i_h, j_h)
        [ i_h = numero di riga, con 1 <= i_h <= 9;
          j_h = numero di colonna, con 1 <= j_h <= 9;
          val_h e' intero, con 1 <= val_h <= 9.
          Naturalmente non si possono inserire piu' di 81 valori ]
        L'opzione -o outfile scrive le soluzioni trovate nel file outfile.
        L'opzione -t outfile scrive le soluzioni nel file outfile in Plain TeX
*/

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

struct {
   int num;
   int p;
   int v[9];
} a[9][9];

struct {
   int i;
   int j;
} stack[81];

int livelloAttuale = 0;
int numZeri = 81;
int iMin;
int jMin;

void panic( char s[] )
{
   fprintf(stderr, "Errore: %s\n", s);
   exit(1);
}

void init( void )
{
   int i,j;
   for ( i = 0, j = 0; i < 9 && j < 9; i++, j++ ) {
      a[i][j].num = 0;
      a[i][j].p = 0;
   }
}

void stampaMatrice( void )
{
   int i,j;
   for ( i = 0; i < 9; i++ ) {
      for ( j = 0; j < 9; j++) {
         if ( a[i][j].num == 0 )
            printf("%3s", "_");
         else
            printf("%3d", a[i][j].num);
      }
      printf("\n");
   }
}

void stampaMatriceSuFile( FILE *fp )
{
   int i,j;
   for ( i = 0; i < 9; i++ ) {
      for ( j = 0; j < 9; j++) {
         if ( a[i][j].num == 0 )
            fprintf( fp, "%3s", "_");
         else
            fprintf( fp, "%3d", a[i][j].num);
      }
      fprintf( fp, "\n");
   }
}

void stampaMatriceSuTeXFile( FILE *fp )
{
   int i,j;
   fprintf( fp, "{\\offinterlineskip\\tabskip=0pt\n");
   fprintf( fp, "\\halign{\\vrule height2.7ex depth1.1ex width 0.8pt\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule width 0.8pt\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule width 0.8pt\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule\n");
   fprintf( fp, "\\hskip6pt #\\hskip2pt&\\vrule width 0.8pt #\\cr\n");
   fprintf( fp, "\\noalign{\\hrule height 0.8pt}\n");
   for ( i = 0; i < 9; i++ ) {
      for ( j = 0; j < 9; j++) {
         if ( a[i][j].num == 0 )
            fprintf( fp, "%2s", " ");
         else 
            fprintf( fp, "%2d", a[i][j].num);
         fprintf( fp, " &");
      }
      fprintf( fp, "\\cr\n");
      if ( i == 2 || i == 5 || i == 8 )
         fprintf( fp, "\\noalign{\\hrule height 0.8pt}\n");
      else
         fprintf( fp, "\\noalign{\\hrule}\n");
   }
   fprintf( fp, "}}\n\n\\bigskip\n");
}

void leggiFile( char s[] )
{
   FILE *fp;
   int i,j,n;
   int numArg;
   if ((fp = fopen( s, "r" )) == NULL)
      panic("non riesco a aprire il file dei dati");
   while ( (numArg = fscanf( fp, "%d %d %d", &i, &j, &n )) != EOF ) {
      if ( numArg != 3 ) {
         fclose( fp );
         panic("numero di argomenti errato nel file dei dati");
      }
      if ( i<1 || i>9 || j<1 || j>9 ) {
         fclose( fp );
         panic("indici di riga o colonna fuori range");
      }
      if ( n<1 || n>9 ) {
         fclose( fp );
         panic("valore da inserire fuori range");
      }
      if ( a[i-1][j-1].num != 0 ) {
         fclose( fp );
         panic("si e' cercato di inserire un valore due volte nello stesso posto");
      }
      a[i-1][j-1].num = n;
      numZeri--;
   }
   fclose( fp );
}

int esisteInRiga( int i, int val )
{
   int j;
   for ( j = 0; j < 9; j++ )
      if ( a[i][j].num == val ) return 1;
   return 0;
}

int esisteInColonna( int j, int val )
{
   int i;
   for ( i = 0; i < 9; i++ )
      if ( a[i][j].num == val ) return 1;
   return 0;
}

int esisteInBlocco( int i, int j, int val )
{
   int h,k;
   int nb = (i/3)*3 + j/3;
   int ii = (nb/3)*3;
   int jj = (nb % 3)*3;
   for ( h = ii; h < ii+3; h++ )
      for ( k = jj; k < jj+3; k++ )
         if ( a[h][k].num == val ) return 1;
   return 0;
}

int datiNonAccettabili( void ) {
   int i,j,k;
   for ( i = 0; i < 9; i++ )
      for ( j = 0; j < 9; j++ )
         if ( (k = a[i][j].num) != 0 ) {
            a[i][j].num = 0;
            if ( esisteInRiga(i,k) || esisteInColonna(j,k) || esisteInBlocco(i,j,k) )
               return 1;
            a[i][j].num = k;
         }
   return 0;
}

int settaPossibilita( void )
{
   int i,j,k,l;
   int lMin = 10;
   for ( i = 0; i < 9; i++ )
      for ( j = 0; j < 9; j++ )
         if ( a[i][j].num == 0 ) {
            l = 0;
            for ( k = 1; k < 10; k++ )
               if (!esisteInRiga(i,k) && !esisteInColonna(j,k) && !esisteInBlocco(i,j,k))
                  a[i][j].v[l++] = k;
            a[i][j].p = l;
            if ( l > 0 && l < lMin )
               lMin = l, iMin = i, jMin = j;
         }
   if ( lMin == 10 )
      return 0;
   else
      return 1;
}

int assegnaValore( int i, int j )
{
   if ( a[i][j].p == 0 ) return 0;
   a[i][j].num = a[i][j].v[--a[i][j].p];
   stack[livelloAttuale].i = i;
   stack[livelloAttuale++].j = j;
   numZeri--;
   return 1;
}

int provaAltraStrada( void ) {
   int i,j;
   do {
      if ( livelloAttuale-- < 0 ) return 0;
      i = stack[livelloAttuale].i;
      j = stack[livelloAttuale].j;
      if ( a[i][j].p == 0 ) {
         a[i][j].num = 0;
         numZeri++;
      }
   } while ( a[i][j].p == 0 );
   a[i][j].num = a[i][j].v[--a[i][j].p];
   livelloAttuale++;
   return 1;
}

int main( int argc, char *argv[] )
{
   int numTentativi = 1;
   int continua = 1;      // se e' 0 non cerca altre soluzioni
   int trovaTutteSol = 0; // se e' 1 non chiede piu' nulla e cerca tutte le soluzioni
   int numSol = 0;        // numero soluzioni trovate
   int ch;                // risposta a "Continua?"
   int opt;               // opzioni
   int optPresenti = 0;   // se e' 1 sono state specificate delle opzioni
   int outSuFile = 0;     // se e' 1 si scrivono le soluzioni sul file outFp
   int texOut = 0;        // se e' 1 si scrivono le soluzioni in Plain TeX sul file outFp
   FILE *outFp;           // file di output, di tipo testo
   
   while ( --argc > 0 && (*++argv)[0] == '-' ) {
      optPresenti = 1;
      while ( opt = *++argv[0] )
         switch (opt) {
         case 'o':
            outSuFile = 1;
            break;
         case 't':
            outSuFile = 1;
            texOut = 1;
            break;
         default:
            printf("Opzione illegale %c\n", opt);
            argc = 0;
            break;
         }
   }
   
   if ( !((optPresenti == 0 && argc == 1) || (optPresenti == 1 && argc == 2)) ) {
      printf("Risolutore di Sudoku\n");
      printf("Uso: sudoku [-o outfile] [-t outfile] filedati\n");
      printf("il filedati deve essere di tipo testo e deve contenere i dati\n");
      printf("iniziali nel formato i j n (uno per ogni riga)\n");
      printf("L'opzione -o outfile scrive le soluzioni nel file outfile\n");
      printf("L'opzione -t outfile scrive le soluzioni nel\n");
      printf("file outfile nel formato Plain TeX\n");
      exit(0);
   }
   
   if ( outSuFile == 1 ) {
      // controllo che il file di output e il file di dati non abbiano lo stesso nome
      if ( strcmp( argv[0], argv[1] ) == 0 )
         panic("Il file di output ha lo stesso nome del file dei dati");
      printf("Le soluzioni verranno scritte nel file %s\n", *argv);
      if ( (outFp = fopen(*argv,"r")) == NULL ) {  // il file non esiste, OK
         if ( (outFp = fopen(*argv,"w")) == NULL ) {  // non riesco a creare il file
            panic("Non riesco a creare il file di output");
         }
      } else {  // il file esiste gia', KO
         fclose(outFp);
         panic("Il file di output esiste gia', scegliere un nome diverso.");
      }
      argv++;
   }
   
   init();
   leggiFile( *argv );
   printf("Il Sudoku proposto e':\n\n");
   stampaMatrice();
   printf("\n");
   if ( outSuFile && !texOut ) {
      if ( outFp == NULL )
         panic("Errore interno: questo non dovrebbe succedere!");
      fprintf(outFp, "Il Sudoku proposto e':\n\n");
      stampaMatriceSuFile( outFp );
      fprintf(outFp, "\n");
   }
   if ( outSuFile && texOut ) {
      if ( outFp == NULL )
         panic("Errore interno: questo non dovrebbe succedere!");
      fprintf(outFp, "%s", "%Plain TeX\n\\parindent=0pt\n\n");
      fprintf(outFp, "Il Sudoku proposto \\`e:\n\n");
      fprintf(outFp, "\\bigskip\n\n");
      stampaMatriceSuTeXFile( outFp );
      fprintf(outFp, "\\bigskip\n\n");
   }

   if ( datiNonAccettabili() ) {
      printf("Il Sudoku proposto non e' coerente con le regole del gioco.\n");
      printf("Controllare i dati introdotti (altrimenti la soluzione non esiste)\n");
      if ( outSuFile && !texOut ) {
         if ( outFp == NULL )
            panic("Errore interno: questo non dovrebbe succedere!");
         fprintf(outFp, "Il Sudoku proposto non e' coerente con le regole del gioco.\n");
         fprintf(outFp, "Controllare i dati introdotti (altrimenti la soluzione non esiste)\n");
         fclose(outFp);
      }
      if ( outSuFile && texOut ) {
         if ( outFp == NULL )
            panic("Errore interno: questo non dovrebbe succedere!");
         fprintf(outFp, "\n\\bigskip\n\n");
         fprintf(outFp, "Il Sudoku proposto non \\`e coerente con le regole del gioco.\n");
         fprintf(outFp, "Controllare i dati introdotti (altrimenti la soluzione non esiste)\n");
         fprintf(outFp, "\n\\bye\n");
         fclose(outFp);
      }
      return 0;
   }

   while ( continua ) {
      while ( settaPossibilita() == 0 ) {
         if ( provaAltraStrada() == 0 ) {
            if ( numSol == 0 ) {
               printf("Questo Sudoku non ha soluzione\n");
               if ( outSuFile && !texOut ) {
                  if ( outFp == NULL )
                     panic("Errore interno: questo non dovrebbe succedere!");
                  fprintf(outFp, "Questo Sudoku non ha soluzione\n");
               }
               if ( outSuFile && texOut ) {
                  if ( outFp == NULL )
                     panic("Errore interno: questo non dovrebbe succedere!");
                  fprintf(outFp, "\n\\bigskip\n\n");
                  fprintf(outFp, "Questo Sudoku non ha soluzione\n");
               }
		    }
            else {
               printf("Non ci sono altre soluzioni\n");
               if ( outSuFile && !texOut ) {
                  if ( outFp == NULL )
                     panic("Errore interno: questo non dovrebbe succedere!");
                  fprintf(outFp, "Non ci sono altre soluzioni\n\n");
               }
               if ( outSuFile && texOut ) {
                  if ( outFp == NULL )
                     panic("Errore interno: questo non dovrebbe succedere!");
                  fprintf(outFp, "\n\\bigskip\n\n");
                  fprintf(outFp, "Non ci sono altre soluzioni\n\n");
               }
	       	}
            printf("(Numero di tentativi = %d)\n\n", numTentativi);
            if ( outSuFile && !texOut ) {
               if ( outFp == NULL )
                  panic("Errore interno: questo non dovrebbe succedere!");
               fprintf(outFp, "(Numero di tentativi = %d)\n\n", numTentativi);
               fclose(outFp);
            }
            if ( outSuFile && texOut ) { // da sistemare
               if ( outFp == NULL )
                  panic("Errore interno: questo non dovrebbe succedere!");
               fprintf(outFp, "(Numero di tentativi = %d)\n\n", numTentativi);
               fprintf(outFp, "\n\\bye\n");
               fclose(outFp);
            }
            return 0;
         }
         numTentativi++;
      }
      assegnaValore( iMin, jMin );
      if ( numZeri == 0 ) { // ho trovato una soluzione
         numSol++;
         printf("Soluzione n. %d\n\n", numSol);
         stampaMatrice();
         printf("\n");
		 printf("(Numero di tentativi = %d)\n\n", numTentativi);
         if ( outSuFile && !texOut ) {
            if ( outFp == NULL )
               panic("Errore interno: questo non dovrebbe succedere!");
            fprintf(outFp, "Soluzione n. %d\n\n", numSol);
            stampaMatriceSuFile( outFp );
            fprintf(outFp, "\n");
            fprintf(outFp, "(Numero di tentativi = %d)\n\n", numTentativi);
         }
         if ( outSuFile && texOut ) {
            if ( outFp == NULL )
               panic("Errore interno: questo non dovrebbe succedere!");
            fprintf(outFp, "Soluzione n.~%d\n\n", numSol);
            fprintf(outFp, "\\bigskip\n\n", numSol);
            stampaMatriceSuTeXFile( outFp );
            fprintf(outFp, "\n(Numero di tentativi = %d)\n\n", numTentativi);
            fprintf(outFp, "\\bigskip\n\n");
         }
         if ( trovaTutteSol == 0 ) {
             printf("Continuare? [S = si', N = no, T = trova tutte le soluzioni senza chiedere]: ");
             ch = getchar();
             while ( getchar() != '\n' ) {}; // salta tutti gli altri caratteri
             printf("\n");
             switch ( ch ) {
             case 's':
             case 'S':
                 continua = 1;
                 break;
             case 'n':
             case 'N':
                 continua = 0;
                 printf("Ricerca interrotta\n");
                 if ( outSuFile && !texOut ) {
                   if ( outFp == NULL )
                     panic("Errore interno: questo non dovrebbe succedere!");
                   fprintf(outFp, "Ricerca interrotta\n");
                 }
                 if ( outSuFile && texOut ) {
                   if ( outFp == NULL )
                     panic("Errore interno: questo non dovrebbe succedere!");
                   fprintf(outFp, "\n\\bigskip\n\n");
                   fprintf(outFp, "Ricerca interrotta\n");
                 }
                 break;
            case 't':
            case 'T':
                continua = 1;
                trovaTutteSol = 1;
                break;
            default:
                continua = 0;
                printf("Carattere non valido\n");
                break;
            }
         }
      }
   }
   if ( outSuFile ) {
      if ( outFp == NULL )
         panic("Errore interno: questo non dovrebbe succedere!");
      if ( texOut )
         fprintf(outFp, "\n\\bye\n");
      fclose(outFp);
   }
   return 0;
}