/*
   Risolutore di Sudoku, versione 1 (unica)
   Autore: Francesco Bottacin
   Data: 24 Marzo 2006
   Descrizione: risolve un Sudoku classico 9 x 9
   Uso: sudoku <file>
        il <file> 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 ]
*/

#include <stdio.h>
#include <stdlib.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++)
         printf("%3d", a[i][j].num);
      printf("\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");
   while ( (numArg = fscanf( fp, "%d %d %d", &i, &j, &n )) != EOF ) {
      if ( numArg != 3 ) {
         fclose( fp );
         panic("numero di argomenti errato nel file");
      }
      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 numCicli = 0;
   if ( argc == 1 ) {
      printf("%s: risolutore di Sudoku\n", argv[0]);
      printf("Uso: %s <nome del file>\n", argv[0]);
      printf("il file deve essere di tipo testo e deve contenere i dati\n");
      printf("iniziali nel formato i j n (uno per ogni riga)\n");
      exit(0);
   }
   if ( argc != 2 )
      panic("numero errato di argomenti");

   init();
   leggiFile( argv[1] );
   
   printf("Il Sudoku proposto e':\n\n");
   stampaMatrice();
   printf("\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");
      return 0;
   }

   while ( numZeri > 0 ) {
      // numCicli++;
      while ( settaPossibilita() == 0 ) {
         if ( provaAltraStrada() == 0 ) {
            printf("Questo Sudoku non ha soluzione\n");
            return 0;
         };
         numTentativi++;
      }
      assegnaValore( iMin, jMin );
   }
   printf("Una soluzione e':\n\n");
   stampaMatrice();
   printf("\n");
   printf("(Numero di tentativi = %d)\n\n", numTentativi);
   // printf("Numero di cicli = %d\n", numCicli);
   return 0;
}