SUDOKU (No se el numero de reto...)
Ya esta.
Ya esta.
Código (cpp) [Seleccionar]
/*
* Linea de comandos: Nombre programa fichero
*
* El fichero debe tener el siguiente formato:
* - 9 filas con 9 numeros separados por espacios
* - Los numeros que vengan dados en el sudoku se escribiran en la posicion que corresponde
* - Las casillas vacias del sudoku se indicaran con ceros
* - Todas las filas deben acabar en un salto de linea
* - Cuanquier linea que siga a las 9 primeras sera ignorada.
*
*
* Salida: Muestra como mucho 2 soluciones (las suficientes para que el contenido del fichero no sea un sudoku correcto)
* y sino indica que no hay solucion.
*
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
class Sudoku
{
public:
Sudoku();
bool cargar(char *nombrefichero);
bool solucionar();
bool solucion_unica();
inline bool esta_solucionado(){return solucionado;};
friend ostream& operator <<(ostream &out,Sudoku &s);
private:
bool correcto(int fila, int columna, int valor);
bool resolver(int fila, int columna);
bool multiples_soluciones(int fila, int columna);
int tabla[9][9];
bool solucionado;
};
Sudoku::Sudoku()
{
for(int i = 0 ; i < 81 ; i++)
tabla[i / 9][i % 9] = 0;
solucionado = false;
}
bool Sudoku::cargar(char *nombrefichero)
{
int i;
char fila[19]; //los 9 numeros + 8 espacios + 1 salto de linea + '\0';
FILE *f;
if(!(f = fopen(nombrefichero,"r")))
return false;
for(i = 0 ; i < 9 ; i++)
{
fgets(fila,19,f);
if(strlen(fila) < 18 || fila[strlen(fila) - 1] != '\n') //formato incorrecto
{
for(int j = 0 ; j < i ; i++) //anulamos la lectura que habia hasta el momento
memset(tabla[j] , 0 , 9 * sizeof(int));
fclose(f);
return false;
}
for(int j = 0 ; j < 9 ; j++)
{
if(fila[2 * i] < '0' || fila[2 * i] > '9')//Si las posiciones pares no son un numero
{
for(int k = 0 ; k < i ; k++) //anulamos la lectura que habia hasta el momento
memset(tabla[k],0,9*sizeof(int));
fclose(f);
return false;
}
if(fila[2 * i + 1] != ' ' && fila[2 * i + 1] != '\n')//Si las posiciones impares no son ni espacio ni \n
{
for(int k = 0 ; k < i ; k++) //anulamos la lectura que habia hasta el momento
memset(tabla[k],0,9*sizeof(int));
fclose(f);
return false;
}
}
//traducimos la fila para el algoritmo
for(int j = 0 ; j < 9 ; j++)
tabla[i][j] = fila[2 * j] - '0';
}
fclose(f);
return true;
}
bool Sudoku::solucionar()
{
return resolver(0,0);
}
bool Sudoku::solucion_unica()
{
return !multiples_soluciones(0,0);
}
bool Sudoku::correcto(int fila, int columna, int valor)
{
for(int i = 0 ; i < 9 ; i++)
{
if(tabla[i][columna] == valor)
return false;
if(tabla[fila][i] == valor)
return false;
if(tabla[3 * (fila / 3) + i / 3][3 * (columna / 3) + i % 3] == valor)
return false;
}
return true;
}
bool Sudoku::resolver(int fila, int columna)
{
if(fila == 9)
{
solucionado = true;
return true;
}
if(tabla[fila][columna] != 0) //Si tenemos un numero original
{
if(resolver((9 * fila + columna + 1) / 9, (9 * fila + columna + 1) % 9)) //pasamos a resolver la siguiente posicion
return true;
}
else
{
//probamos cada uno de los numeros
for(int i = 1 ; i <= 9 ; i++)
{
if(correcto(fila,columna,i)) //Si es corrector en la posicion dada
{
tabla[fila][columna] = i; //Marcamos la casilla con el numero
//Y pasamos a resolver la siguiente posicion
if(resolver((9 * fila + columna + 1) / 9, (9 * fila + columna + 1) % 9))
return true;
}
}
tabla[fila][columna] = 0; //Volvemos a dejar vacia la posicion actual
}
return false;
}
bool Sudoku::multiples_soluciones(int fila, int columna)
{
if(fila == 9)
{
if(!solucionado)
{
cout << *this << endl;
solucionado = true;
return false;
}
cout << *this << endl;
return true;
}
if(tabla[fila][columna] != 0) //Si tenemos un numero original
{
if(multiples_soluciones((9 * fila + columna + 1) / 9, (9 * fila + columna + 1) % 9)) //pasamos a resolver la siguiente posicion
return true;
}
else
{
//probamos cada uno de los numeros
for(int i = 1 ; i <= 9 ; i++)
{
if(correcto(fila,columna,i)) //Si es corrector en la posicion dada
{
tabla[fila][columna] = i; //Marcamos la casilla con el numero
//Y pasamos a resolver la siguiente posicion
if(multiples_soluciones((9 * fila + columna + 1) / 9, (9 * fila + columna + 1) % 9))
return true;
}
}
tabla[fila][columna] = 0; //Volvemos a dejar vacia la posicion actual
}
return false;
}
ostream& operator <<(ostream &out,Sudoku &s)
{
for(int i = 0 ; i < 9 ; i++)
{
if(!(i % 3))
out << endl;
for(int j = 0 ; j < 9 ; j++)
{
if(!(j % 3))
out << ' ';
out << s.tabla[i][j] << ' ';
}
out << endl;
}
return out;
}
int main(int argc, char *argv[])
{
Sudoku sudoku;
if(argc != 2)
{
cout << argv[0] << " fichero";
return -1;
}
if(!sudoku.cargar(argv[1]))
{
cout << "Error en carga de fichero." << endl;
return -1;
}
if(sudoku.solucion_unica() && sudoku.esta_solucionado())
{
cout << "El sudoku tiene una unica solucion:" << endl;
}
else if(sudoku.esta_solucionado())
cout << "El fichero no contiene un sudoku correcto. Tiene mas de una solucion." << endl;
else
cout << "El sudoku no tiene solucion." << endl;
return 0;
}