Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - [C] sudoku non funziona!
Forum - C/C++ - [C] sudoku non funziona!

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 22:26
Giovedì, 26/05/2011
ho scritto il codice per risolvere il sudoku (inizialmente ho fissato una configurazione, successivamente farò una funzione per immetterne altre)i l problema è che compila ma non funziona e non riesco a capire perchè.

ho riscritto il codice delle funzioni poi dando come argomento la matrice perchè credo che il problema sia quello e ho inserito la visualizzazione all'interno della funzione solve ma il risultato finale è uguale.
ora posto il primo codice, aiutatemi a capire cosa non va
Codice sorgente - presumibilmente C++
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3.  
  4. #define N 9
  5. int m[N][N]={0,0,0,0,0,0,0,0,0,  0,8,3,5,0,0,4,1,0, 0,7,0,6,0,0,0,2,0, 0,0,0,0,8,0,1,6,0, 0,0,0,2,0,6,0,0,0, 0,1,7,0,4,0,0,0,0, 0,5,0,0,0,9,0,4,0, 0,4,2,0,0,1,7,3,0, 0,0,0,0,0,0,0,0,0};
  6.  
  7. // visualizza griglia sudoku
  8. void visualizza()
  9. {
  10.         for (int i=0; i<N; i++) {
  11.                 for (int j=0; j<N; j++)
  12.                         printf("%3d",m[i][j]);
  13.                 printf("\n");
  14.         }
  15.         printf("\n");
  16.         return;
  17. }
  18.  
  19.  
  20.  
  21. //restituisce true se la configuarazione della griglia è valida
  22. bool config_valida ()
  23. {
  24.         //ELEMENTI RIGA DIFFERENTI:                     m[i,h] != m[i,k] per ogni h!=k
  25.         for (int i=0; i<N ; i++ )
  26.                 for ( int h=0; h<N; h++ )
  27.                         for ( int k=0; k<N ; k++ )
  28.                                 if ( h!=k) {
  29.                                         if ( m[i][h] == m[i][k] )
  30.                                         return false;           //se cè un conflitto la funzione ritorna falso
  31.                                 }
  32.                
  33.         //ELEMENTI COLONNA DIFFERENTI      m[h,j] != m[k][j] per ogni h!=k
  34.         for (int j=0; j<N ; j++ )
  35.                 for ( int h=0; h<N ; h++ )
  36.                         for ( int k=0; k<N ; k++ )
  37.                                 if ( h!=k ) {
  38.                                         if ( m[h][j] == m[k][j] )
  39.                                                 return false;
  40.                                 }
  41.        
  42.         //ELEMENTI PER QUADRANTE DIFFERENTI  m[i,j] != m[h,k] per ogni i,j <9 e h=i/3 +1..h/3+2...h/3+3
  43.         for (int i=0; i<N ; i++)
  44.                 for (int j=0; j<N ; j++)
  45.                         for (int s=1; s<4 ; s++)
  46.                                 for (int t=1; t<1 ; t++) {
  47.                                         int h=i/3+s;
  48.                                         int k=j/3+t;
  49.                                         if ( m[i][j]== m[h][k] )
  50.                                                 return false;
  51.                                 }
  52.        
  53.         return true;                   
  54.                
  55. }
  56.  
  57. //restituisce vero se ha risolto il sudoku
  58. bool solve()
  59. {
  60.         bool done = false;
  61.        
  62.         int i =-1; int j=-1;
  63.        
  64.         //cerca i e j indici minimi tali che  m[i,j]=0
  65.         for (int k=0; k<N; k++){
  66.                 for (int t=0; t<N; t++)
  67.                         if ( !m[k][t] )
  68.                         { i=k; j=t; break; }
  69.                 if (i!=-1 && j!=-1) break;
  70.         }
  71.                
  72.         //se è stata trovata una cella vuota inserisci un valore e richiama funzione se la config è valida
  73.         if (i!=-1 && j!=-1) {
  74.                 for ( int k=0; k<N; k++ ) {
  75.                         m[i][j] = k;
  76.                         if ( config_valida() && solve() ) //se inserendo il numero la configurazione e valida e si possono fare ulteriori inserimenti
  77.                                 done = true ;   //passo finale dell'iterazione
  78.                 }
  79.                 if ( !done ) m[i][j] = 0;       //se l'inserimento fatto è valido ma non porta alla soluzione riporta la cella a 0
  80.         }
  81.         else done = true;  
  82.        
  83.         return done;
  84. }
  85.  
  86.  
  87.  
  88. int main()
  89. {      
  90.         //configurazione();
  91.         printf("\nschema iniziale\n");
  92.         visualizza();
  93.        
  94.         if ( solve() ) {
  95.                 printf("\nsudoku risolto!\n");
  96.                 visualizza();
  97.         }       else printf("\nil sudoku non ammette soluzione");
  98.        
  99.         return 0;
  100. }

PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 22:27
Giovedì, 26/05/2011
come punto di riferimento per la scrittura del codice ho  usato questo articolo
http://www.aquilante.net/doc/sudoku.pdf

PM Quote
Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 17:33
Venerdì, 27/05/2011
Prova a vedere questo programma che ho fatto io:
http://www.pierotofy.it/pages/sorgenti/dettagli/18936-Sudo ...
è molto commentato dovresti capire come si risolve un sudoku senza tante difficoltà

PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 0:12
Sabato, 28/05/2011
Testo quotato
Postato originariamente da XBarboX:

Prova a vedere questo programma che ho fatto io:
http://www.pierotofy.it/pages/sorgenti/dettagli/18936-Sudo ...
è molto commentato dovresti capire come si risolve un sudoku senza tante difficoltà



grazie mille...hai realizzato davvero un codice molto semplice da leggere nonostante io non conosca il c++.

ho modificato il mio codice ispirandomi anche al tuo per la funzione solve e rendendo più modulare la funzione configurazione ma il programma non funziona ancora per la mia istanza....aiutami a capire cosa non va
Codice sorgente - presumibilmente C++
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3.  
  4. int m[9][9]= { {4,0,0,0,0,0,0,0,0}, {0,8,3,5,0,0,4,1,0}, {0,7,0,6,0,0,0,2,0} ,{0,0,0,0,8,0,1,6,0}, {0,0,0,2,0,6,0,0,0} ,{0,1,7,0,4,0,0,0,0}, {0,5,0,0,0,9,0,4,0} ,{0,4,2,0,0,1,7,3,0} ,{0,0,0,0,0,0,0,0,0}};
  5.  
  6.  // visualizza griglia sudoku
  7. void visualizza( void)
  8. {
  9.         for (int i=0; i<N; i++) {
  10.                 for (int j=0; j<N; j++)
  11.                         printf("%3d",m[i][j]);
  12.                 printf("\n");
  13.         }
  14.         printf("\n");
  15.         return;
  16. }
  17.  
  18.  
  19.  
  20. //restituisce true se la configuarazione della griglia è valida
  21.  
  22. bool presente_riga( int x, int riga)
  23. {
  24.         for (int i=0; i<9; i++){
  25.                 if( m[riga][i]== x)
  26.                         return true;
  27.         }
  28.         return false;
  29.  
  30. }
  31.  
  32. bool presente_colonna ( int x, int colonna )
  33. {
  34.         for (int i=0; i<9; i++){
  35.                 if ( m[i][colonna]==x )
  36.                         return true;
  37.         }
  38.         return false;
  39. }
  40.  
  41. bool presente_quadrante (int x, int riga, int colonna )
  42. {
  43.         for (int i=0; i<3; i++)
  44.                 for (int j=0; j<3; j++) {
  45.                         int s = (riga/3)*3 + i;
  46.                         int t = (colonna/3)*3 + j;
  47.                         if ( m[s][t] == x)
  48.                                 return true;
  49.         }
  50.         return false;
  51. }
  52.  
  53.  
  54. bool config_valida (int x, int riga, int colonna)
  55. {
  56.         if ( !presente_riga (x,colonna) && !presente_colonna (x, colonna) && !presente_quadrante(x, riga, colonna))
  57.                 return true;
  58.         return false;
  59. }
  60.  
  61. //restituisce vero se ha risolto il sudoku
  62. bool solve( void )
  63. {
  64.         int inserimenti = 0;
  65.         bool libero = false; // variabile per sapere se esiste una cella libera
  66.         int r =-1; int c=-1; // indici riga e colonna  libere
  67.        
  68.         //cerca r e c primi indici tali che  m[r,c]=0
  69.         do {
  70.                 r++;
  71.                 c = 0;
  72.                 do {
  73.                         c++;
  74.                         if (m[r][c]==0) libero=true;
  75.                 } while (libero==false && c<9);
  76.         } while (libero==false && r<9);
  77.        
  78.                
  79.         //se è stata trovata una cella vuota inserisci un valore e richiama funzione se la config è valida
  80.         if ( libero ) {
  81.                 for ( int x=0; x<9; x++ ) {     //prova a inserire nella cella ogni valore possibile poi controlla
  82.                         if ( config_valida ( x , r, c ) ) {
  83.                                 m[r][c] = c ;                   // se la config è valida inserisci l'elemento
  84.                                 inserimenti++;
  85.                                 if (solve()) return true;  //se la chiamata ricorsiva torna true, torna true alla main
  86.                                 else {
  87.                                         m[r][c] = 0; //se l'inserimento fatto non porta alla soluzione riporta la cella a 0
  88.                                         inserimenti--;
  89.                                 }
  90.                         }       //se la config non è valida prova con il prox x
  91.                 }
  92.                 if ( inserimenti == 0) return false;    //se non è stato possibile inserire alcun valore in una cella libera c'è un errore
  93.         }
  94.         else return true;   //non ci sono più celle vuote -> finito! questa è l'ultima chiamata di solve
  95. }
  96.  
  97.  
  98.  
  99.  
  100. int main()
  101. {      
  102.         //configurazione();
  103.         printf("\nschema iniziale\n");
  104.         visualizza();
  105.        
  106.         if ( solve() ) {
  107.                 printf("\nsudoku risolto!\n");
  108.                 visualizza();
  109.         }       else printf("\nil sudoku non ammette soluzione");
  110.        
  111.         return 0;
  112. }


PM Quote
Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 8:30
Sabato, 28/05/2011
Il ragionamento dietro sembra corretto.
Dovresti dirmi l'errore che da il programma.
Comunque sei sicuro che la funzione presente_quadrante funzioni?

PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 18:14
Sabato, 28/05/2011
il problema è che il programma termina ma restituisce nessuna soluzione.
secondo te è un problem ail fatto che abbia dichiarato la matrice come variabile globale???

PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 18:56
Sabato, 28/05/2011
ho fatto un errore stupido nella funzione config_valida. ho passato l'argomento colonna alla funzione riga

inoltre ho assegnato m [r][c] = c. naturalmente deve essere m[r][c] = x

Ultima modifica effettuata da belledetta il 28/05/2011 alle 19:01
PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 19:04
Sabato, 28/05/2011
Testo quotato
Postato originariamente da belledetta:

ho fatto un errore stupido nella funzione config_valida. ho passato l'argomento colonna alla funzione riga

inoltre ho assegnato m [r][c] = c. naturalmente deve essere m[r][c] = x



nuovo errore: i valori possibili di x  da inserire vanno da 1 a 9 non da 0 a 8

PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 19:13
Sabato, 28/05/2011
Testo quotato
Postato originariamente da belledetta:

Testo quotato
Postato originariamente da belledetta:

ho fatto un errore stupido nella funzione config_valida. ho passato l'argomento colonna alla funzione riga

inoltre ho assegnato m [r][c] = c. naturalmente deve essere m[r][c] = x



nuovo errore: i valori possibili di x  da inserire vanno da 1 a 9 non da 0 a 8


ho notato che le celle libere  hanno riga che va da 0 9 il che è impossibile!

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo