Vai al contenuto

[C++] Sudoku

HeR

Da HeR
in Web design e sistemisti

Messaggi raccomandati

HeR

HeR

Inviato
Inviato

ho fatto un programma che testa se un sudoku è fatto bene o male.

ho suddiviso il compito in 3 predicati:uno controlla se nelle righe non ci sono ripetizioni, uno se non ci sono nelle colonne, un altro per testare se nelle sottomatrici 3x3 ci sono ripetizioni.

quest'ultimo l'ho suddiviso in due sotto predicati, ovvero ho creato una funzione semplice che mi testa se ci sono numeri uguali in matrici 3x3 generiche, con l'intenzione poi di usare questa funzione in un'altra...

vi scrivo il codice sperando di essere piu chiara..

//PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI IN GENERICHE MATRICI 3X3

bool controllo3x3 (int mat[3][3])
{
bool ripetuto=true;
int i,j=0,r=0,c=1;
for(i=0;i<=2 && ripetuto;i++)
{
	for(j=0;j<=2 && ripetuto;j++)
	{
		while(c<=2 && r<=2 && ripetuto)
		{
			if(mat[i][j]==mat[r][c])
				ripetuto=false;
			else
			{
				if(c<2)
					c++;
				else if(c==2)
				{r++;
				c=0;}
			}
		}
	}
}
return ripetuto;
}

il problema viene qui...

non riesco a trovare un modo per assegnare alla matrice 3x3 in questione le 9 sottomatrici 3x3 di un classico sudoku.

mi sono spiegata? (non credo...)

comunque vorrei precisare che non dovete assolutamente propinarmi la soluzione...vorrei solo avere suggerimenti..

ho provato a far assegnare alla matrice 3x3 i valori della 9x9 con un paio di for...ma gia al secondo ciclo non riesce piu a controllare il tutto...

immagino che sbaglio nel dare dei valori agli indici...

----->il mio negozio di magliette<-----
Link al commento
Condividi su altri siti
manang

manang

Inviato
Inviato

non puoi assegnare tutta la matrice e come parametri dai gli estremi della sottomatrice che ti interessa?

in questo modo puoi svincolarti dalla matrice 3x3 e fare il controllo su qualsiasi matrice che abbia la dimensione pari alla radice quadrata del lato della matrice generale.

al posto tuo userei un vettore di supporto e segnerei con 1 se il numero è selezionato.

se alla fine rimane un valore del vettore con 0 allora c'è un valore non usato.

Link al commento
Condividi su altri siti
nico96

nico96

Inviato
Inviato
bool control3x3(int **mat,int i,int j,int k)//k è la lunghezza del lato{

int vet[k];

int l,m;

for (l=0;l<k;l++)

vet[k]=0;

for(l=i;l<i+sqrt(k);l++){

for(m=j;,m<j+sqrt(k);m++){

if(vet[mat[l][m]])

return false;

vet[mat[l][m]]++;

}

}

return true;

}

c++:fiorellino:

When I’m Done, This Night Will Fear Me

Link al commento
Condividi su altri siti
sadamelik

sadamelik

Inviato
Inviato
Wow una programmatrice!!!!!

.....

ci sono molte più programmatrici della storia di quanto tu possa immainare ...

leggi qui

Ciao Her provo a darti una risposta spero di essere il più chiaro possibile!!

// alla funzione controllo3x3 passi per intero la struttura 
// di array bidimensionale 9x9 come immagino hai
// creato per contenere la griglia del sudoku
// ma passi anche da quale riga e da quale colonna devi fare il controllo


// facciamo un esempio
// aaa|bbb|ccc
// aaa|bbb|ccc
// aaa|bbb|ccc
// ---|---|--
// ddd|eee|fff
// ddd|eee|fff
// ddd|eee|fff
// ---|---|--
// ggg|hhh|iii
// ggg|hhh|iii
// ggg|hhh|iii

// immaginiamo che quella sopra sia una rappresentazione 
// dell'array bidimensionale
// se chiamo la funzione con controllo3x3(_mioArray, 0, 0)
// elaborerà solo i riquadro con le a
// se chiamo la funzione con controllo3x3(_mioArray, 3, 0)
// elaborerà solo i riquadro con le b
// se chiamo la funzione con controllo3x3(_mioArray, 3, 6)
// elaborerà solo i riquadro con le h
// ecc...

// I vallori ammessi per _row e _column sono 0, 3, 6
// spero di essermi fatto capire


bool controllo3x3 (int mat[9][9], int _row, int _column)
{
   bool ripetuto = false;
   int _numeri[9];
   int i,j=0,r=0,c=1;
   // Elaborazione per rige
   for(i =_row ; i <= _row + 2 && !ripetuto; i++)
   {
     // Elaborazione per colonne
       for(j =_column; j<= _column + 2 && !ripetuto; j++)
       {
         // Utilizzo la struttura _numeri per verificare se un 
         // numero è già presente
         // nella porzione di matrice che si sta analizzando oppure 
         // non è ancora presente
         // La struttuta _numeri si comporta in questo modo
         // se nella posizione il valore è 1 il numero è già presente 
         // nella porzione della matrice altrimenti
         // il numero non è ancora presente nella porzione analizzata
         // alla fine di questo controllo modifico il valore a 1 in modo 
         // tale che nel ciclo successivo 
         // conosco già che in quella posizione ho trovato un numero
         if(mat[i][j] >= 1 || mat[i][j]<=9)
         {
           if(_numeri[mat[i][j] - 1] == 1) ripetuto = true;
           _numeri[mat[i][j]] = 1;          
         }


         // Uso un array di 9 elementi
         // devi stare attenta ai possibili valori 
         // se nella matrice hai valori come posso immaginare da 1 a 9 è 
         // fondamentale 
         // questa porzione di codice mat[i][j] - 1 cosi indicizzo 
         // l'arrai correttamente da 0 a 8 che sono i possibili
         // indice che l'array può avere

         // Questo codice è molto vulnerabile nel senso che se 
         // nella matrice ci sono numeri superiori a 9 o inferiori a 9 
         // il calcolo di _numeri[mat[i][j] - 1] può creare 
         // funzionamenti non previsti a priori
         // come controlli sbagliati o errori di sistema come quello
         // di segmentation fault
         // Ma se hai la certezza che i valori della matrice 
         // sono compresi tra 1 e 9 il codice è molto performante
         // perché eviti di fare un loop while che aggravia l'elaborazione 
       }
   }
   return ripetuto;
}

Se ci sono passaggi poco chiari li visualizziamo insieme

Mi sono permesso anche di modificare un pò anche l'algoritmo per renderlo più veloce e anche un pò più elegante

tecnologicamente dipendente

Link al commento
Condividi su altri siti
HeR

HeR

Inviato
  • Autore
Inviato

grazie sadamelik..la tua spiegazione è stata davvero molto chiara!

ho provato a testare il programma con vari input ma con una matrice-sudoku particolare mi sbaglia..e il problema è proprio nel controllo delle sottomatrici!

vi posto il codice completo...

#include <iostream>
using namespace std;

const int NRIGHE = 9;
const int NCOLONNE = 9;

int main (int argc, char * const argv[]) 
{
    //------>TEST FALLITO<-----
    int MAT[NRIGHE][NCOLONNE]={{1,2,3,4,5,6,7,8,9},{2,3,4,5,6,7,8,9,1},{3,4,5,6,7,8,9,1,2},{4,5,6,7,8,9,1,2,3},{5,6,7,8,9,1,2,3,4},{6,7,8,9,1,2,3,4,5},{7,8,9,1,2,3,4,5,6},{8,9,1,2,3,4,5,6,7},{9,1,2,3,4,5,6,7,8}};

if (controllo_righe(MAT) && controllo_colonne(MAT) && controllo_sottomatrici(MAT))
	cout << "Il sudoku è corretto!\n\n";
else
	cout << "Il sudoku è sbagliato!\n\n";
}

//PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE RIGHE
bool controllo_righe(int sudoku[NRIGHE][NCOLONNE])
{		
int i=0, j=0, indice=j+1;
bool ripetuto=true;
while(i<NRIGHE && ripetuto)
{
	while(j<NCOLONNE-1 && ripetuto)
	{
		while(indice<NCOLONNE && ripetuto)
		{
			if(sudoku[i][j]==sudoku[i][indice])
				ripetuto=false;
			else
				indice++;
		}
		j++;
		indice=j+1;			
	}
	i++;
	j=0;
	indice=j+1;
}
return ripetuto;
}

//PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE COLONNE
bool controllo_colonne(int sudoku[NRIGHE][NCOLONNE])
{
int i=0, j=0, indice=1;
bool ripetuto=true;
while(j<NCOLONNE && ripetuto)
{
	while(i<NRIGHE-1 && ripetuto)
	{
		while(indice<NRIGHE && ripetuto)
		{
			if(sudoku[i][j]==sudoku[indice][j])
				ripetuto=false;
			else
				indice++;
		}
		i++;
		indice=i+1;
	}
	j++;
	i=0;
	indice=i+1;
}
return ripetuto;
}

//PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE SOTTOMATRICI 3X3
bool controllo3x3 (int mat[NRIGHE][NCOLONNE], int riga, int colonna)
{
   bool ripetuto = false;
   int numeri[9];
   int i,j;

for(i =riga ; i <= riga + 2 && !ripetuto; i++)
{
for(j =colonna; j<=colonna + 2 && !ripetuto; j++)
{
	if(mat[i][j] >= 1 || mat[i][j]<=9)
	{
           if(numeri[mat[i][j] - 1] == 1)
			ripetuto = true;
		numeri[mat[i][j]] = 1;          
	}
}
}
return ripetuto;
}



bool controllo_sottomatrici(int mat[NRIGHE][NCOLONNE])
{
bool cond1 = controllo3x3(mat,0,0);
bool cond2 = controllo3x3(mat,3,0);
bool cond3 = controllo3x3(mat,6,0);
bool cond4 = controllo3x3(mat,0,3);
bool cond5 = controllo3x3(mat,3,3);
bool cond6 = controllo3x3(mat,6,3);
bool cond7 = controllo3x3(mat,0,6);
bool cond8 = controllo3x3(mat,3,6);
bool cond9 = controllo3x3(mat,6,6);

return cond1 && cond2 && cond3 && cond4 && cond5 && cond6 && cond7 && cond8 && cond9;
}

cosa ho sbagliato??

perdonate l'ultimo predicato controllo_sottomatrici, l'ho scritto al volo con compia+incolla per scrivere questo messaggio! :fiorellino:

----->il mio negozio di magliette<-----
Link al commento
Condividi su altri siti
sadamelik

sadamelik

Inviato
Inviato

Ciao ...

errore mio scusa, ho scritto il codice ieri velocemente e non ho fatto nemmeno un test prima di passartelo.

scusa!! :ghghgh:

Ho fatto la modifica che corregge il mio BUG :shock:

oggi ho installato gcc e ho provato a far girare il tuo codice e ho verificato e corretto il mio errore. Lo trovi segnato in rosso nel codice!

spero che ti risulti tutto giusto ora

ti passo anche la matrice del sudoku su cui ho fatto i test

int MAT[9][9] = {{5,3,4,6,7,8,9,1,2},{6,7,2,1,9,5,3,4,8},{1,9,8,3,4,2,5,6,7},{8,5,9,7,6,1,4,2,3},{4,2,6,8,5,3,7,9,1},{7,1,3,9,2,4,8,5,6},{9,6,1,5,3,7,2,8,4},{2,8,7,4,1,9,6,3,5},{3,4,5,2,8,6,1,7,9}};

Buon coding

:shock:

#include <iostream>
using namespace std;

const int NRIGHE = 9;
const int NCOLONNE = 9;

int main (int argc, char * const argv[]) 
{
    //------>TEST FALLITO<-----
    int MAT[NRIGHE][NCOLONNE]={{1,2,3,4,5,6,7,8,9},{2,3,4,5,6,7,8,9,1},{3,4,5,6,7,8,9,1,2},{4,5,6,7,8,9,1,2,3},{5,6,7,8,9,1,2,3,4},{6,7,8,9,1,2,3,4,5},{7,8,9,1,2,3,4,5,6},{8,9,1,2,3,4,5,6,7},{9,1,2,3,4,5,6,7,8}};

   if (controllo_righe(MAT) && controllo_colonne(MAT) && controllo_sottomatrici(MAT))
       cout << "Il sudoku è corretto!\n\n";
   else
       cout << "Il sudoku è sbagliato!\n\n";
}

//PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE RIGHE
bool controllo_righe(int sudoku[NRIGHE][NCOLONNE])
{        
   int i=0, j=0, indice=j+1;
   bool ripetuto=true;
   while(i<NRIGHE && ripetuto)
   {
       while(j<NCOLONNE-1 && ripetuto)
       {
           while(indice<NCOLONNE && ripetuto)
           {
               if(sudoku[i][j]==sudoku[i][indice])
                   ripetuto=false;
               else
                   indice++;
           }
           j++;
           indice=j+1;            
       }
       i++;
       j=0;
       indice=j+1;
   }
   return ripetuto;
}

//PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE COLONNE
bool controllo_colonne(int sudoku[NRIGHE][NCOLONNE])
{
   int i=0, j=0, indice=1;
   bool ripetuto=true;
   while(j<NCOLONNE && ripetuto)
   {
       while(i<NRIGHE-1 && ripetuto)
       {
           while(indice<NRIGHE && ripetuto)
           {
               if(sudoku[i][j]==sudoku[indice][j])
                   ripetuto=false;
               else
                   indice++;
           }
           i++;
           indice=i+1;
       }
       j++;
       i=0;
       indice=i+1;
   }
   return ripetuto;
}

//PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE SOTTOMATRICI 3X3
bool controllo3x3 (int mat[NRIGHE][NCOLONNE], int riga, int colonna)
{
   bool ripetuto = false;
   int numeri[9];
   int i,j;

for(i =riga ; i <= riga + 2 && !ripetuto; i++)
{
   for(j =colonna; j<=colonna + 2 && !ripetuto; j++)
   {
       if(mat[i][j] >= 1 || mat[i][j]<=9)
       {
           if(numeri[mat[i][j] - 1] == 1)
               ripetuto = true;
           [color=Red]numeri[mat[i][j] - 1] = 1[/color];          
       }
   }
}
return ripetuto;
}



bool controllo_sottomatrici(int mat[NRIGHE][NCOLONNE])
{
   bool cond1 = controllo3x3(mat,0,0);
   bool cond2 = controllo3x3(mat,3,0);
   bool cond3 = controllo3x3(mat,6,0);
   bool cond4 = controllo3x3(mat,0,3);
   bool cond5 = controllo3x3(mat,3,3);
   bool cond6 = controllo3x3(mat,6,3);
   bool cond7 = controllo3x3(mat,0,6);
   bool cond8 = controllo3x3(mat,3,6);
   bool cond9 = controllo3x3(mat,6,6);

   return cond1 && cond2 && cond3 && cond4 && cond5 && cond6 && cond7 && cond8 && cond9;
}

tecnologicamente dipendente

Link al commento
Condividi su altri siti
chitebbeiv

chitebbeiv

Inviato
Inviato

sto programmino mi ha incuriosito e mi ci sono voluto cimentare pure io.

l'ho stravolto un pò ma solo per adattarlo al mio stile, alla fine la logica è la stessa e funziona!

posto il mio codice, ho anche preparato una matrice test che va a buon fine, devi solo giocare un pò con i nomi delle variabili nel main:

#include <iostream>
using namespace std;

//#define dbg_row
//#define dbg_col
//#define dbg_mat

const int NRIGHE = 9;
const int NCOLONNE = 9;


// PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE RIGHE
bool controllo_righe(int sudoku[NRIGHE][NCOLONNE]) {        
   unsigned int check[9];
   for (int i = 0; i < NRIGHE; i++) {
       for (int n = 0; n < NCOLONNE; n++)
           check[n] = 0;    // inizializza il vettore
       for (int j = 0; j < NCOLONNE; j++) {
           #ifdef dbg_row
           cout << "[" << i << "][" << j << "]: " << check[sudoku[i][j]-1] << "   ->   ";
           #endif
           check[sudoku[i][j]-1] = (check[sudoku[i][j]-1] + 1) % 2;
           #ifdef dbg_row
           cout << check[sudoku[i][j]-1] << endl;
           #endif
           if (check[sudoku[i][j]-1] == 0) {
               for (int i = 0; i < 9; i++)
                   cout << check[i] << " ";
               cout << "\n";
               return false;
           }
       }    
   }
   return true;
}


// PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE COLONNE
bool controllo_colonne(int sudoku[NRIGHE][NCOLONNE]) {
   unsigned int check[9];
   for (int j = 0; j < NCOLONNE; j++) {
       for (int n = 0; n < NRIGHE; n++)
           check[n] = 0;    // inizializza il vettore
       for (int i = 0; i < NRIGHE; i++) {
           #ifdef dbg_col
           cout << "[" << i << "][" << j << "]: " << check[sudoku[i][j]-1] << "   ->   ";
           #endif
           check[sudoku[i][j]-1] = (check[sudoku[i][j]-1] + 1) % 2;
           #ifdef dbg_col
           cout << check[sudoku[i][j]-1] << endl;
           #endif
           if (check[sudoku[i][j]-1] == 0) {
               for (int i = 0; i < 9; i++)
                   cout << check[i] << " ";
               cout << "\n";
               return false;
           }
       }    
   }
   return true;
}

// PREDICATO CHE CONTROLLA SE CI SONO RIPETIZIONI NELLE SOTTOMATRICI MxN
bool controllo_matrici(int sudoku[NRIGHE][NCOLONNE]) {
   unsigned int check[9];
   for (int n = 0; n < 9; n += 3) {
       for (int k = 0; k < 9; k++)
           check[k] = 0;    // inizializza il vettore
       for (int i = n; i <= n+2; i++) {
           for (int j = n; j <= n+2; j++) {
               #ifdef dbg_mat
               cout << "[" << i << "][" << j << "]: " << check[sudoku[i][j]-1] << "   ->   ";
               #endif
               check[sudoku[i][j]-1] = (check[sudoku[i][j]-1] + 1) % 2;
               #ifdef dbg_mat
               cout << check[sudoku[i][j]-1] << endl;
               #endif
               if (check[sudoku[i][j]-1] == 0) {
                   for (int i = 0; i < 9; i++) {
                       if (i != 0 && i % 3 == 0) 
                           cout << endl;
                       cout << check[i] << " ";
                   }
                   cout << endl;
                   return false;
               }
           }
       }
   }
   return true;
}


int main (int argc, char* argv[]) {
   //------>TEST FALLITO<-----
   int MAT1[NRIGHE][NCOLONNE] = {    {1,2,3,4,5,6,7,8,9}, 
                                   {2,3,4,5,6,7,8,9,1}, 
                                   {3,4,5,6,7,8,9,1,2}, 
                                   {4,5,6,7,8,9,1,2,3}, 
                                   {5,6,7,8,9,1,2,3,4}, 
                                   {6,7,8,9,1,2,3,4,5}, 
                                   {7,8,9,1,2,3,4,5,6}, 
                                   {8,9,1,2,3,4,5,6,7}, 
                                   {9,1,2,3,4,5,6,7,8}    };

   //------>TEST CORRETTO<-----
   int MAT[NRIGHE][NCOLONNE] = {     {1,2,3,4,5,6,7,8,9}, 
                                   {4,5,6,7,8,9,1,2,3}, 
                                   {7,8,9,1,2,3,4,5,6}, 
                                   {2,3,4,5,6,7,8,9,1}, 
                                   {5,6,7,8,9,1,2,3,4}, 
                                   {8,9,1,2,3,4,5,6,7}, 
                                   {3,4,5,6,7,8,9,1,2}, 
                                   {6,7,8,9,1,2,3,4,5}, 
                                   {9,1,2,3,4,5,6,7,8}    };

   if (controllo_righe(MAT) && controllo_colonne(MAT) && controllo_matrici(MAT))
       cout << "Il sudoku è corretto!\n\n";
   else
       cout << "Il sudoku è sbagliato!\n\n";
}

Buon divertimento!

 MacBook Pro 2011 13" i5 2.4GHz 4GB 

I'm a mac user

Link al commento
Condividi su altri siti

Archiviato

Questa discussione è archiviata e chiusa a future risposte.

Vai alla lista discussioni
×
×
  • Crea Nuovo...