codice:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include<fstream>
#include<math.h>
#define UNASSIGNED 0
using std::cout;
using std::cin;
using std::endl;
using std::ifstream;
using std::ofstream;
using std::ios;
class sudoku{
private:
int row,col,num,boxStartRow,boxStartCol;
bool FindUnassignedLocation(int **g, int &row, int &col,int n);
bool isSafe(int **g, int row, int col, int num,int n);
bool UsedInRow(int **g, int row, int num,int n);
bool UsedInCol(int **g, int col, int num,int n);
bool UsedInBox(int **g, int boxStartRow, int boxStartCol, int num,int n);
public:
bool SolveSudoku(int **g,int n,int &cont);
void printG(int **g,int n,int &cont);
void Crea_matrice(int **&g,int &n);
};
bool sudoku::SolveSudoku(int **g,int n,int &cont)
{
++cont;
if(cont%5000==0){
ofstream fout ("cicli sudoku.txt", ios::app);
cout<<"\n\nSoluzione parziale sudoku al ciclo "<<cont<<":\n\n";
fout<<"\n\nSoluzione parziale sudoku al ciclo "<<cont<<":\n\n";
printG(g,n,cont);
//fout<<"\n\nSoluzione parziale sudoku al ciclo "<<cont<<":\n\n";
fout.close();
system("pause");
}
//else cout<<"Il numero di cicli di backtracking effettuati sono: "<<cont<<endl;
int row, col;
if (!FindUnassignedLocation(g, row, col,n))
return true;
for (int num = 1; num <= n; num++)
{
if (isSafe(g, row, col, num,n))
{
g[row][col] = num;
if (SolveSudoku(g,n,cont))
return true;
g[row][col] = UNASSIGNED;
}
}
return false;
}
/* Searches the grid to find an entry that is still unassigned. */
bool sudoku::FindUnassignedLocation(int **g, int &row, int &col,int n)
{
for (row = 0; row < n; row++)
for (col = 0; col < n; col++)
if (g[row][col] == UNASSIGNED)
return true;
return false;
}
/* Returns whether any assigned entry n the specified row matches
the given number. */
bool sudoku::UsedInRow(int **g, int row, int num,int n)
{
for (int col = 0; col < n; col++)
if (g[row][col] == num)
return true;
return false;
}
/* Returns whether any assigned entry in the specified column matches
the given number. */
bool sudoku::UsedInCol(int **g, int col, int num,int n)
{
for (int row = 0; row < n; row++)
if (g[row][col] == num)
return true;
return false;
}
/* Returns whether any assigned entry within the specified 3x3 box matches
the given number. */
bool sudoku::UsedInBox(int **g, int boxStartRow, int boxStartCol, int num,int n)
{
for (int row = 0; row < (int)sqrt(n); row++) //IN SUDOKU 9*9 ERA row<3
for (int col = 0; col < (int)sqrt(n); col++) //IN SUDOKU 9*9 ERA row<3
if (g[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
/* Returns whether it will be legal to assign num to the given row,col location.
*/
bool sudoku::isSafe(int **g, int row, int col, int num,int n)
{
return !UsedInRow(g, row, num,n) && !UsedInCol(g, col, num,n) &&
!UsedInBox(g, row - row % (int)sqrt(n) , col - col % (int)sqrt(n), num,n);
}
/* Stampa della griglia */
void sudoku::printG(int **g,int n,int &cont)
{
ofstream fout;
fout.open("cicli sudoku.txt", ios::app);
for (int row = 0; row < n; row++)
{
for (int col = 0; col < n; col++){
cout<<g[row][col]<<" ";
fout<<g[row][col]<<" ";}
cout<<endl;
fout<<endl;
}
fout<<"\n------------------------------------------------------------------------------------------\n";
}
void sudoku::Crea_matrice(int **&g,int &n) // devi passare entrambe le variabili per riferimento
{
char *nomefile=new char[10]; // 10 char sono troppo pochi,
// per i nomi dei file meglio usarne almeno 260
cout<<"Inserire il nome del file: ";
cin>>nomefile;
ifstream fin(nomefile);
if( ! fin.is_open() ) // controllo che il file sia aperto
return;
fin>>n;
// Quì ci vorrebbe un controllo sulla matrice **g, e se esiste già, cancellarla.
if (g) delete g;
g = new int* [n];
for( int i=0; i<n; i++)
g[i] = new int [n];
for( int i=0; i<n; i++)
{
for( int j=0; j<n; j++)
fin>>g[i][j];
}
fin.close();
delete [] nomefile;
// la memoria di una matrice non rilascia così, ma poi... Perché cancellare la matrice appena creata ?
}
int main()
{
int cont=0;
int n=0;
sudoku s;
int **g=0;
s.Crea_matrice(g,n);
if (s.SolveSudoku(g,n,cont) == true){
cout<<"\n\nLa soluzione del sudoku e': \n";
s.printG(g,n,cont);
cout<<"\n\nSoluzione Trovata dopo "<<cont<<" cicli\n\n";
}
else
cout<<"Non esistono soluzioni."<<endl;
delete g;
return 0;
}
Rispondi quotando