/*

Autor: trollkemada (trollkemada@gmail.com)

Comenzado: 27/04/2011
Terminado: 01/05/2011

Falta bastante por mejorar en eficiencia
*/

#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

struct sudoku
{
       int valor[9][9]; //Almacena el valor de esa casilla (cuando es definitivo)
       bool pvalor[9][9][10]; //Almacena si cada posible valor de una casilla es realmente posible o no (si otra casilla lo impide)
       //El pvalor[i][j][0] almacena si el valor es dado por el usuario
       bool calculado[9][9]; //almacena si el valor ha sido calculado
};

// Acciones basicas del struct sudoku
void iniciarSudoku(sudoku &s);
void escribir(sudoku s);
void escribirFichero(sudoku s, int n, char nombre[]);
void leer(sudoku &s);
void leerFichero(sudoku &s,char nombre[]);
bool igual(sudoku s,sudoku t);
bool irresoluble(sudoku s);
int soluciones(sudoku s);
void debug(sudoku s);

// Acciones para resolver un sudoku.
void actualizarEntradas(sudoku &s,int i,int j);
void rellenarEliminacion(sudoku &s);
void resolver(sudoku &s);

// Acciones para completar partes de un sudoku
void completarTodo(sudoku &s);
bool completarfila(sudoku &s, int fila, int valor);
bool completarcolumna(sudoku &s,int columna,int valor);
bool completarCuadrado(sudoku &s,int c, int valor);

// Acciones para encontrar recursivamente todas las solcuiones de un sudoku
bool encontrarPosible(sudoku s,int &i, int &j, int &k);
bool resolverVarios(sudoku &s, int &n);



int main()
{
    int n=0,sol;
    char nombre[63];
    sudoku s;
    iniciarSudoku(s);
    while (n!=1 && n!=2)
    {
          cout<<"1- Leer sudoku desde teclado"<<endl;
          cout<<"2- Leer sudoku desde archivo"<<endl;
          cout<<"Eliga opcion: ";
          cin>>n;
    }
    if (n==1) leer(s);
    else
    {
        cout<<endl<<"El fichero ha de tener el siguiente formato: ";
        cout<<endl<<"- Ha de estar en texto plano (.txt)";
        cout<<endl<<"- Ha de tener un 0 en las entradas desconocidas";
        cout<<endl<<"- Ha de tener una cifra en las entradas conocidas";
        cout<<endl<<"- Cada cifra debe estar separada de la anterior mediante un espacio o un salto de línea";
        cout<<endl<<endl;
        cout<<endl<<"Nombre del fichero (por defecto sudoku.txt) :";
        fflush(stdin);
        gets(nombre);
        if (nombre[0]=='\0') strcpy(nombre,"sudoku.txt");
        leerFichero(s,nombre);
    }
    sol=soluciones(s);
    if (sol==0)
    {
               cout<<endl<<"El sudoku no tiene solución";
               cout<<endl<<"Pulse una tecla para finalizar el programa";
               getchar();
               return 0;
    }
    else if (sol==1)
    {
         cout<<endl<<"Sudoku leido: ";
         escribir(s);
         cout<<endl<<"Solucion: ";
         resolver(s);
         escribir(s);
         cout<<endl<<"Pulse una tecla para finalizar el programa";
         getchar();
         return 0;
    }
    else
    {
          cout<<endl<<"Sudoku leido: ";
          escribir(s);
          cout<<endl<<endl<<"Calculando soluciones y escribiendolas a respuestas.txt ..."<<endl<<endl;
          resolverVarios(s,n);
          getchar();
    }
}


/*Inicializa un sudoku dejando todas sus entradas como posibles valores, y ningun valor como dado por el usuario
 y con valor 0 */
void iniciarSudoku(sudoku &s)
{
     int i,j,k;
     for(i=0;i<9;i++)
     {
                     for (j=0;j<9;j++)
                     {
                         s.valor[i][j]=0;
                         s.pvalor[i][j][0]=false;
                         for (k=1;k<10;k++) s.pvalor[i][j][k]=true;
                         s.calculado[i][j]=false;
                     }
     }
}

/* Escribe con formato un sudoku por pantalla  */
void escribir(sudoku s)
{
     int i,j;
     cout<<endl<<endl;
     for (i=0;i<9;i++)
     {
         if(i%3==0) cout<<"-------------------------"<<endl;
         for(j=0;j<9;j++)
         {
                         if(j%3==0) cout<<"| ";
                         if(j==8) cout<<s.valor[i][j]<<" |";
                         else cout<<s.valor[i][j]<<" ";

         }
         cout<<endl;
     }
     cout<<"-------------------------";
}

/* Dado un sudoku con una unica solucion, un numero n y el nombre de un fichoer, escribe la soluciones enesima, s, en el fichero nombre */
void escribirFichero(sudoku s, int n, char nombre[])
{
     ofstream f;
     int i,j;
     resolver(s);
     f.open(nombre,ios::app);
     if (!f)
     {
            cout<<"Imposible escribir la solucion en un fichero de texto.";
            getchar();
     }
     else
     {

         f<<endl<<"Solucion "<<n<<endl;
         for (i=0;i<9;i++)
         {
             if(i%3==0) f<<"-------------------------"<<endl;
             for(j=0;j<9;j++)
             {
                         if(j%3==0) f<<"| ";
                         if(j==8) f<<s.valor[i][j]<<" |";
                         else f<<s.valor[i][j]<<" ";

             }
         f<<endl;
         }
         f<<"-------------------------";
         f.close();
     }
}

// Lee un sudoku entrada por entrada desde teclado.
void leer(sudoku &s)
{
     int i,j,k,v;
     cout<<endl<<"Leyendo sudoku:"<<endl;
     cout<<"Fila (introduce 0 para terminar) (Introducir rango 1-9): ";
     do { cin>>i;} while (i<1 || i>9);
     i--; //El usuario mete entradas 1-9 pero se almacenan 0-8
     while (i!=-1)
     {
           cout<<"Columna (1-9): ";
           do { cin>>j;} while (j<1 || j>9);
           j--;
           cout<<"Valor: (1-9)";
           do { cin>>v;} while (v<1 || v>9);
           if (s.pvalor[i][j][0]) cout<<"Ya se ha introducido ese valor !!";
           else if (!s.pvalor[i][j][v]) cout<<"Ese valor no puede ir en esa casilla !!";
           else
           {
           for(k=1;k<10;k++) if (k!=v) s.pvalor[i][j][k]=false; //Marcamos todos los posibles valores de la casilla como invalidos
           s.valor[i][j]=v; //Asignamos el valor introducido a la casilla que corresponde
           s.pvalor[i][j][v]=true; // Su valor sí es un posible valor de la casilla
           s.pvalor[i][j][0]=true; // Fijamos el valor

           // Actualizamos el sudoku, el resto de entradas del mismo cuadrado,fila y columna no podran tener ese numero
           actualizarEntradas(s,i,j);
           }
           cout<<endl<<endl;
           cout<<"Fila (introduce 0 para terminar): ";
           cin>>i;
           i--;
     }
}

//Lee un sudoku desde un fichero (que tenga el formato adecuado)
void leerFichero(sudoku &s,char nombre[])
{
     int i,j,k;
     char v;
     fstream f;
     f.open(nombre,ios::in);
     if (!f) cout<<"Error al abrir el archivo";
     else
     {
         f>>v;
         // Analogo a leer desde teclado, el valor es int(v) - int('0')
         for (i=0;i<9;i++) for (j=0;j<9;j++)
         {
           if (v!='0')
           {
              for(k=1;k<10;k++) if (k!=int(v)-int('0')) s.pvalor[i][j][k]=false;
              s.pvalor[i][j][int(v)-int('0')]=true;
              s.pvalor[i][j][0]=true;
              s.valor[i][j]=int(v) - int('0');
              actualizarEntradas(s,i,j);
           }
         f>>v;
         }
     }
     f.close();
}

/* Devuelve true si dos sudokus son iguales completamente, y false en otro caso */
bool igual(sudoku s,sudoku t)
{
     int i,j,k;
     for(i=0;i<9;i++) for(j=0;j<9;j++)
     {
         if (s.valor[i][j]!=t.valor[i][j]) return false;
         for (k=0;k<10;k++) if (s.pvalor[i][j][k]!=t.pvalor[i][j][k]) return false;
         if (s.calculado[i][j]!=t.calculado[i][j]) return false;
     }
     return true;
}

/* Devuelve true si un sudoku no tiene soluciones y false en otro caso */
bool irresoluble(sudoku s)
{
     int i,j,k,c;
     resolver(s);
     // Buscamos alguna casilla sin valores posibles
     for (i=0;i<9;i++) for (j=0;j<9;j++)
     {
         c=0;
         for(k=1;k<10;k++) if(s.pvalor[i][j][k]) c++;
         if (c==0) return true;
     }
     return false;

}
/* Devuelve el numero de soluciones de un sudoku:
            - 0 si no tiene soluciones
            - 1 si tiene una solucion
            - 2 si tiene más de una soluciones
*/
int soluciones(sudoku s)
{
    int i,j,k,c;
    if (irresoluble(s)) return 0;
    resolver(s);
    // Buscamos alguna casilla que tenga más de un posible valor
    for (i=0;i<9;i++) for (j=0;j<9;j++)
    {
        c=0;
        for (k=1;k<10;k++) if (s.pvalor[i][j][k]) c++;
        if (c>1)
        {
                 return 2;
        }
    }
    return 1;
}

/* Escribe con formato el sudoku, y luego, con más detalle, toda su estructura, entrada por entrada. */
void debug(sudoku s)
{
     int i,j,k;
     cout<<endl<<endl<<endl;
     for(i=0;i<9;i++) for(j=0;j<9;j++)
     {
         cout<<"("<<i+1<<","<<j+1<<") --> ";
         if (s.pvalor[i][j][0]) cout<<"[E] ";
         else if (s.calculado[i][j]) cout<<"[C] ";
         else cout<<"    ";
         for(k=1;k<10;k++) if (s.pvalor[i][j][k]) cout<<"["<<k<<"] "; else cout<<"    ";
         cout<<endl;
     }
     escribir(s);
}


void actualizarEntradas(sudoku &s,int i,int j)
{
     int fila,columna,cuadrado,lim_fila,lim_columna;
     //Recorremos las filas: Si la casilla no es de entrada, marcamos el valor s.valor[i][j] como FALSE ya que comparten fila
     for(fila=0;fila<9;fila++) if (!s.pvalor[i][fila][0] && !s.calculado[i][fila]) s.pvalor[i][fila][s.valor[i][j]]=false;
     //analogo para columna
     for(columna=0;columna<9;columna++) if (!s.pvalor[columna][j][0] && !s.calculado[columna][j]) s.pvalor[columna][j][s.valor[i][j]]=false;

    // Calculamos a qué subcuadrado 3x3 pertenece (i,j). Numerados de arriba abajo, de izquierda a derecha
    // y del 0 al 8
    if (j<3) cuadrado=0;
    else if (j<6) cuadrado=1;
    else if (j<9) cuadrado=2;
    if (i<3) cuadrado=cuadrado;
    else if (i<6) cuadrado=cuadrado+3;
    else if(i<9) cuadrado=cuadrado+6;

     // Asignamos las coordenadas del vértice inferior derecho a los limites (que dependen de c, obviamente)
     lim_fila=3*(cuadrado/3)+3;
     lim_columna=3*(cuadrado%3)+3;
     //Con estos bucles recorremos el cuadrado c. Empezamos en el vértice superior izquierdo, y vamos sumando
     //filas y columnas hasta terminar en el vertice inferior derecho del cuadrado.
     //Si la casilla no es de entrada, marcamos el valor s.valor[i][j] como FALSE ya que comparten cuadrado
     for(fila=3*(cuadrado/3);fila<lim_fila;fila++) for(columna=3*(cuadrado%3);columna<lim_columna;columna++) if (!s.pvalor[fila][columna][0] && !s.calculado[fila][columna]) s.pvalor[fila][columna][s.valor[i][j]]=false;

}

/* Rellenar por eliminacion todas las casillas del sudoku, es decir, comprueba si alguna casilla solo tiene un posible valor
 y de ser asi, se lo asigna */
void rellenarEliminacion(sudoku &s)
{
     int i,j,k,contador;
     for (i=0;i<9;i++) for (j=0;j<9;j++) if (!s.pvalor[i][j][0] && !s.calculado)
     {
          contador=0;
          for(k=1;k<10;k++) if (s.pvalor[i][j][k]) contador++;
          if (contador==1) for (k=1;k<10;k++) if (s.pvalor[i][j][k]) s.valor[i][j]=k;
     }
}

/* dado un sudoku, intenta resolverlo y lo devuelve con el maximo posible de valores calculados */
void resolver(sudoku &s)
{
     int i,j;
     sudoku s_copia;
     rellenarEliminacion(s);
     completarTodo(s);
     for (i=0;i<9;i++) for (j=0;j<9;j++) actualizarEntradas(s,i,j);
     while (!igual(s,s_copia))
     {
           s_copia=s;
           rellenarEliminacion(s);
           completarTodo(s);
           for (i=0;i<9;i++) for (j=0;j<9;j++) actualizarEntradas(s,i,j);
     }
}

/* Dado un sudoku s, completa todos los valores que puede llamando a las funciones completar fila, columan y cuadrado.*/
void completarTodo(sudoku &s)
{
     int i,valor;
     for(i=0;i<9;i++) for (valor=1;valor<10;valor++)
     {
                      completarfila(s,i,valor);
                      completarcolumna(s,i,valor);
                      completarCuadrado(s,i,valor);
     }
}

/* Dado un sudoku, un valor, y una fila, intenta encontrar la unica casilla (si la hay) de la fila en la que pueda
ir el valor, si la encuentra, le asigna el valor
Devuelve true si la encuentra y false en otro caso */
bool completarfila(sudoku &s, int fila, int valor)
{
     int columna,k,contador=0;
     for (columna=0;columna<9;columna++) if (s.pvalor[fila][columna][valor]) contador++;

     if (contador==1)
     {
                     for (columna=0;columna<9;columna++) if (s.pvalor[fila][columna][valor] && !s.pvalor[fila][columna][0] && s.valor[fila][columna]!=valor)
                     {
                         s.valor[fila][columna]=valor;
                         for (k=1;k<10;k++) s.pvalor[fila][columna][k]=false;
                         s.calculado[fila][columna]=true;
                         s.pvalor[fila][columna][valor]=true;
                         return true;

                     }

     }
     return false;
}

/* Analoga a la anterior */
bool completarcolumna(sudoku &s,int columna,int valor)
{
     int fila,k,contador=0;
     for (fila=0;fila<9;fila++) if (s.pvalor[fila][columna][valor]) contador++;
     if (contador==1)
     {
                     for (fila=0;fila<9;fila++)  if (s.pvalor[fila][columna][valor] && !s.pvalor[fila][columna][0] && s.valor[fila][columna]!=valor)
                     {
                         s.valor[fila][columna]=valor;
                         for (k=1;k<10;k++) s.pvalor[fila][columna][k]=false;
                         s.calculado[fila][columna]=true;
                         s.pvalor[fila][columna][valor]=true;
                         return true;

                     }
     }
     return false;
}

/* Analoga a la anterior */
bool completarCuadrado(sudoku &s,int c, int valor)
{
     int i,j,li,lj,k,contador=0;
     // Asignamos las coordenadas del vértice inferior derecho a los limites (que dependen de c, obviamente)
     li=3*(c/3)+3;
     lj=3*(c%3)+3;
     //Con estos bucles recorremos el cuadrado c. Empezamos en el vértice superior izquierdo, y vamos sumando
     //filas y columnas hasta terminar en el vertice inferior derecho del cuadrado.
     for(i=3*(c/3);i<li;i++) for(j=3*(c%3);j<lj;j++) if (s.pvalor[i][j][valor]) contador++;
     if (contador==1) for(i=3*(c/3);i<li;i++) for(j=3*(c%3);j<lj;j++) if (s.pvalor[i][j][valor] && !s.pvalor[i][j][0] && s.valor[i][j]!=valor)
     {
           s.valor[i][j]=valor;
           for (k=1;k<10;k++) if (!s.pvalor[i][j][0] && !s.calculado[i][j]) s.pvalor[i][j][k]=false;
           s.calculado[i][j]=true;
           s.pvalor[i][j][valor]=true;
           return true;

     }
     return false;
}


/* Dado un sudoku, devuelve true si puede encontrar un valor k para la casilla (i,j) del sudoku, y false en otro caso.
En caso de que lo encuentre, también devuelve i,j, y k */
bool encontrarPosible(sudoku s,int &i, int &j, int &k)
{
     int fila,columna,valor;
     // Recorremos todas las casillas y todos los valores, hasta encontrar alguno.
     for (fila=0;fila<9;fila++) for (columna=0;columna<9;columna++) if (!s.pvalor[fila][columna][0]) for (valor=1;valor<10;valor++) if (s.pvalor[fila][columna][valor])
     {
            i=fila;
            j=columna;
            k=valor;
            return true;
     }
     return false;
}

/* Dado un sudoku con más de una solucion, escribe (resolviendo recursivamente) todas sus soluciones en "respuestas.txt" */
bool resolverVarios(sudoku &s, int &n)
{
     sudoku copia;
     int i,j,k,valor;

     // Aunque esta funcion no deberia ser llamada con sudokus que solo tengan una solucion, prevenimos errores.
     // Sólo la primera llamada podria entrar en este if, ya que el resto de llamadas recursivas solo se llaman
     // con sudokus de al menos 2 soluciónes.
     if (soluciones(s)==1) escribirFichero(s,n,"respuestas.txt");

     // El sudoku tiene más de una solucion (ver llamada recursiva)
     else
     {
          copia=s;
          // Mientras se pueda suponer un valor por valido...
          while (encontrarPosible(s,i,j,k))
              {
                 // ... suponemos dicho valor
                 for(valor=1;valor<10;valor++) s.pvalor[i][j][valor]=false;
                 s.valor[i][j]=k;
                 s.pvalor[i][j][k]=true;
                 s.pvalor[i][j][0]=true;
                 actualizarEntradas(s,i,j);
                 // Y vemos qué pasa con el sudoku:

                 // si tiene una solucion, la escribimos
                 if (soluciones(s)==1)
                 {
                          n++;
                          if (n-10000==0) cout<<endl<<"Calculadas las 10.000 primeras soluciones, se ira mostrando el progreso..."<<endl<<endl;
                          if (n%10000==0) cout<<endl<<n;
                          escribirFichero(s,n,"respuestas.txt");
                          resolver(s);
                          s=copia;
                          s.pvalor[i][j][k]=false;
                          copia=s;
                          return false;
                 }

                 // Si no tiene ninguna solucion, hemos descubierto que ese valor no es una posibilidad
                 else if (irresoluble(s))
                 {
                                 s=copia;
                                 s.pvalor[i][j][k]=false;
                                 copia=s;
                                 return false;
                 }
                 // Y si tiene más de una solucion, llamamos recursivamente a la funcion.
                  resolverVarios(s,n);
              }
     }

}