#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
const int TAM = 9; // Maximo numero que puede haber en el sudoku, numeros más grandes o mas pequeños generan sudokus con cuadrados de 2x2,4x4,5x5... Por defecto lo dejamos en el clásico 3x3
bool resuelto(short Tablero[TAM][TAM]);
void generarSudoku(short Tablero[TAM][TAM]);
//funcion raiz natural, mas eficiente que sqrt y que uso para sacar el tamaño de cada cuadrado (raiz(TAM))
inline int raiz(int n)
{
for (int i = 2;i*i<=n;i++)
{
if (i*i == n) return i;
}
throw "Error no valido";
}
void mostrarTablero(short Tablero[TAM][TAM])
{
for (int i = 0; i<TAM; i++)
{
for (int j = 0; j<TAM; j++)
{
cout<<(int)Tablero[i][j]<<" | ";
}
cout<<endl;
}
cout<<endl<<endl;
}
int main()
{
short Tablero[TAM][TAM];
generarSudoku(Tablero);
mostrarTablero(Tablero);
cout<<resuelto(Tablero)<<endl;
return 0;
}
// Generamos un sodoku, no es necesario que tablero este inicializado
void generarSudoku(short Tablero[TAM][TAM])
{
#define SUBCUADRADO(i,j) (i/TAM_N+(j/TAM_N)*TAM_N)
const int TAM_N = raiz(TAM); // tamaño de cada cuadrado, corresponde a su raiz
bool Tabla[TAM][TAM][TAM]; // Tabla(x,y,valor) con los valores probados en una casilla, true si fue probado
bool Tabla_Fila[TAM][TAM]; // Tabla(y,valor) con los valores existen en la fila, true si existe
bool Tabla_Columna[TAM][TAM]; // Tabla(x,valor) con los valores probados en una columna, true si fue probado
bool Tabla_Cuadrado[TAM][TAM]; // Tabla(SUBCUADRADO,valor) con los valores probado en un cuadrado, true si fue probado
int cont;
// Inicializar las tablas
for (int i = 0; i<TAM; i++)
{
for (int j = 0; j<TAM; j++)
{
Tablero[i][j] = -1; // inicializo el sudoku
for (int k = 0; k<TAM; k++)
{
Tabla[i][j][k] = false;
Tabla_Fila[j][k] = false;
Tabla_Columna[i][k] = false;
}
}
}
for (int i = 0; i<TAM; i++)
{
for (int k = 0; k<TAM; k++)
{
Tabla_Cuadrado[i][k] = false;
}
}
// Bucle principal
for (int i = 0; i<TAM; i++)
{
for (int j = 0; j<TAM; j++)
{
int aux
= (rand()%TAM
); // Numero aleatorio bool fallo;
if (Tablero[i][j] >= 0) // Si ya contenía algo, quitamos sus valores de las tablas
{
const int valor = Tablero[i][j] - 1;
Tabla_Fila[j][valor] = false;
Tabla_Columna[i][valor] = false;
Tabla_Cuadrado[SUBCUADRADO(i,j)][valor] = false;
}
cont = 0; //variable control para el bucle, solo vamos a comprobar los 9 valores posibles
do
{
aux = ((aux+1)%TAM);//aumento en una unidad
fallo = (Tabla[i][j][aux] | // tabla de valores probados en esa casilla
Tabla_Fila[j][aux] | // tabla de valores probados en esa fila
Tabla_Columna[i][aux] | // tabla de valores probados en esa columna
Tabla_Cuadrado[SUBCUADRADO(i,j)][aux]); // tabla de valores probados en ese cuadrado
cont++; // una iteracion mas
}
while( fallo && cont < TAM); // mientras no encontremos un valor que no este en las tablas y no hayamos recorrido todos los valores...
if (!fallo) //añadimos
{
Tablero[i][j] = aux+1; // Tablero a devolver, los numeros son del 1-9
Tabla[i][j][aux] = true; // Marcamos en la tabla de casillas un nuevo valor
Tabla_Fila[j][aux] = true; // Marcamos un nuevo valor en la fila
Tabla_Columna[i][aux] = true; // Marcamos un nuevo valor en la columna
Tabla_Cuadrado[SUBCUADRADO(i,j)][aux] = true; // Marcamos un nuevo valor en el cuadrado
}
else //Si no encontramos ningun valor válido para añadir
{
for (int k = 0; k<TAM; k++)
{
Tabla[i][j][k] = false; // reseteamos la tabla de valores probados
}
Tablero[i][j] = -1; // borramos la casilla
j -= 2; // retrocedemos, son dos unidades porque luego el for me avanza una
if (j < -1) // si nos hemos pasado de la fila, retrocedemos una columna
{
j =TAM-2;
i--;
if(i < 0) // if de depuración, en principio no debería activarse nunca pues indica que nos hemos salido del sudoku
{
cerr<<"Error inesperado"<<endl;
throw "Error inesperado";
}
}
}
}
}
}
/* Funcion auxiliar para depuración, reciclado de otro proyecto por lo que ha sido necesario añadir algunas constantes
Se usa para comprobar que el sudoku está correctamente generado (no hay repeticiones en cada fila/columna/cuadrado)
*/
const int MAX = TAM;
const int MAX_N = 3;
const int Suma = 45;
bool resuelto(short Tablero[TAM][TAM])
{
// Macro para comprobar repeticiones
#define COMPROBAR_REPETICIONES if (i != 0) \
for (short k = i-1; k > -1;k--) \
if (Repeticiones[i] == Repeticiones[k]) \
return false;
// Lineas horizontales
short Repeticiones[MAX];
for (short i = 0; i < MAX; i++)
Repeticiones[i] = 0;
short Contador = 0;
for (short j = 0; j < MAX; j++)
{
for (short i = 0; i < MAX; i++)
{
Repeticiones[i] = Tablero[i][j];
COMPROBAR_REPETICIONES
}
}
// Lineas verticales
for (short j = 0; j < MAX; j++)
{
Contador = 0;
for (short i = 0; i < MAX; i++)
{
Repeticiones[i] = Tablero[j][i];
COMPROBAR_REPETICIONES
}
}
// Cuadrados
for (short l = 0; l < MAX_N; l++)
for (short k = 0; k < MAX_N; k++)
{
Contador = 0;
for (short j = k*MAX_N; j < (MAX_N*k)+MAX_N; j++)
for (short i = l*MAX_N; i < (l*MAX_N)+MAX_N; i++)
{
Contador += Tablero[i][j];
}
// Aquí no podemos usar la macro, asi que usamos otro método
if (Contador != Suma) // Suma es lo que da si se suma 1+2+3+4+5+6+7+8+9
{
cout<<l<<','<<k<<endl;
return false;
}
}
return true;
}