codice:
#include <iostream>using namespace std;
const int UNASSIGNED=0;
class Sudoku{
private:
int **matrice;
int grado,rig,col,k,SettoreInizioRig,SettoreInizioCol;
bool Controlins(int **,int,int,int,int);
int controlriga(int **,int,int,int);
int controlcol(int **,int,int,int);
int controlcella(int **,int,int,int,int);
bool Trovavuota(int **,int&,int&,int);
public:
Sudoku(int n);//Costruttore con argomenti
void Inserisci();
bool Risolvi();
void StampaSudo();
~Sudoku(){};
};
Sudoku::Sudoku(int n){
grado=n;
matrice = new int* [grado*grado];//Allochiamo la matrice creando una array di puntatori.
for( int i=0; i<grado*grado; i++)
{ matrice[i] = new int [grado*grado];}
}
void Sudoku::Inserisci(){
int elem;
for(int i=0;i<grado*grado;i++){
cout<<"Riga "<<i+1<<endl;
for(int j=0;j<grado*grado;j++){
cin>>elem;
matrice[i][j]=elem;
}
}
}
void Sudoku::StampaSudo(){
for(int i=0;i<grado*grado;i++){
cout<<endl;
for(int j=0;j<grado*grado;j++){
cout<<"\t"<<matrice[i][j];
}
}
cout<<endl;
}
bool Sudoku::Risolvi(){
int rig,col;
if (!Trovavuota(matrice,rig,col,grado))//valore sicuro assegnato non ci ripasso più e restituisco true se è riempita la matrice
return true;
for(int k=1;k<=grado*grado;k++){
if (Controlins(matrice,rig, col, k,grado))
{
matrice[rig][col]=k;
if(Risolvi())
return true;
matrice[rig][col]= UNASSIGNED;}
}
return false;
}
bool Sudoku::Trovavuota(int **matrice,int &rig,int &col,int grado)
{
for (int rig=0;rig<grado*grado;rig++)
for (int col=0;col<grado*grado;col++)
if(matrice[rig][col]==UNASSIGNED)//quando trovo uno zero in una casella ritorno vero
return true;
return false;
}
bool Sudoku::Controlins(int **matrice,int rig, int col, int k,int grado)
{
return !controlriga(matrice,rig, k,grado) &&
!controlcol(matrice,col, k,grado) &&
!controlcella(matrice,rig, col, k,grado);
}
int Sudoku::controlriga(int **matrice,int rig,int k,int grado){
for(int j=0;j<grado*grado;j++){
if(k==matrice[rig][j])
return true;
}
return false;
}
int Sudoku::controlcol(int **matrice,int col,int k,int grado){
for(int i=0;i<grado*grado;i++){
if(k==matrice[i][col])
return true;
}
return false;
}
int Sudoku::controlcella(int **matrice,int SettoreInizioRig,int SettoreInizioCol,int k,int grado){
for (int rig = 0; rig < grado; rig++)
for (int col = 0; col < grado; col++)
if (matrice[rig+SettoreInizioRig][col+SettoreInizioCol] == k)
return true;
return false;
}
int main()
{
cout<<"Inserire il grado del Sudoku --> ";
int n;
cin>>n;
Sudoku s(n);
cout<<endl<<"----------------- POPOLAMENTO SUDOKU (inserire 0 dove non si desidera inserire un numero) -----------------"<<endl<<endl;
s.Inserisci();
cout<<endl<<"------------------- S U D O K U D A R I S O L V E R E ------------------- "<<endl;
s.StampaSudo();
if(s.Risolvi()==true){
cout<<endl<<"------------------- S U D O K U R I S O L T O ------------------- "<<endl;
s.StampaSudo();
}else
cout<<"non esistono soluzioni"<<endl;
s.~Sudoku();
return 0;
}