codice:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include<fstream>
#include<math.h>
#define UNASSIGNED 0
//#define dim 25
//typedef int griglia[dim][dim];
/*using std::cout;
using std::cin;
using std::endl;
using std::ifstream;*/
using namespace std;
class sudoku{
private:
int row,col,num,boxStartRow,boxStartCol;
public:
bool FindUnassignedLocation(int **g, int &row, int &col,int n);
bool isSafe(int **g, int row, int col, int num,int n);
bool SolveSudoku(int **g,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);
void printG(int **g,int n);
void Crea_matrice(int **g,int &n);
};
bool sudoku::SolveSudoku(int **g,int n)
{
static int cont=1;
cout<<"Il numero dei 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))
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)
{
for (int row = 0; row < n; row++)
{
for (int col = 0; col < n; col++)
cout<<g[row][col]<<" ";
cout<<endl;
}
}
void sudoku::Crea_matrice(int **g,int &n){
char *nomefile=new char[10];
cout<<"Inserire il nome del file: ";
cin>>nomefile;
cout<<endl;
ifstream fin(nomefile);
fin>>n;
g = new( int * );
for(int i=0;i<n;i++)
g[i] = new int;
for (int i=0;i<n;i++){
for(int j=0;j<n;j++){
fin>>g[i][j];
}
}
fin.close();
delete [] nomefile;
delete g;
}
int main()
{
int n;
sudoku s;
int **g;
//griglia g;
//int n;
s.Crea_matrice(g,n);
cout<<"La soluzione del sudoku e': \n";
if (s.SolveSudoku(g,n) == true)
s.printG(g,n);
else
cout<<"Non esistono soluzioni."<<endl;
return 0;
}
Rispondi quotando